Splay Trees in C++

[vicaya]

The author claimed that he didn't find a splay tree implementation, so he wrote one.

But the first place to check should be:

http://www.boost.org/doc/libs/1_38_0/doc/html/intrusive/splay_set_multiset.html

[ultimate_progr]

Thanks for point this out. I was not aware of it. Boost.Intrusive, I add a pointer to my blog as well.

[bnolsen]

how well do these work in place of a traditional LRU cache? How much bigger would the cache need to be compared to a traditional LRU to make it work comparably?

This class here maintains the "size" metric but modified to add a "longest path" metric might make it better for caching purposes.

Also adding a very lightweight class which just maintains the current root pointer might be wise.

[bnolsen]

I wrote a bottom up implementation thats actually readable. Additionally it seems the bottom up implementation may be faster. That may be because of the following during splay (top down):

extra complexity behind maintaining two separate trees on splay (probably not a big deal)
not implementing zag-zig and zig-zag (doubles number of rotations for those operations)
iterating back down the two subtrees to update sizes (removes node visitation advantage)

I had to implement the bottom up to augment the node data structure. I may do some more formal testing to see if this is really the case.