Thursday, April 2, 2009

Splay Trees in C++

I was looking for a generic implementation of Splay Tree in C++. Splay Tree is a self-balancing binary search tree with the additional property that recently accessed elements are quick to access again. This is useful for competitive analysis and online algorithms. Splay Trees operations such as insertion, look-up and removal are performed in O(log(n)) amortized time.

I found no generic implementation, but the original C implementation of Daniel Sleator and Robert Tarjan. Therefore, I decided to transform this implementation into generic C++ with templates.

Here you have the C++ code for Splay Trees (adapted by the original C version)

1 comment:

  1. Someone pointed out that http://www.boost.org/doc/libs/1_38_0/doc/html/intrusive/splay_set_multiset.html

    is a Boost implementation of SplayTree. Thanks for pointing out

    ReplyDelete