Implementing Splay Trees In C++

摘要

Splay trees are self-adjusting binary search trees. If the set of frequently accessed elements is a small subset of the elements in the tree, splay trees perform better than other search trees. Splay trees are typically used in the implementation of caches, memory allocators, routers, garbage collectors, data compression, and ropes (replacement of string used for long text strings). Additionally, I've used splay trees as the internal representation of associative container classes with the same interface as the associative containers in the C++ Standard Library. The implementation I present in this article is a plug-in replacement for the standard associative containers, the only difference being performance characteristics.