Splay tree

A splay tree is a binary search tree. It performs basic operations such as insertion, look-up and removal in O(log(n)) average time. For many non-uniform sequences of operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown. The splay tree was invented by Daniel Sleator and Robert Tarjan.

All normal operations on a splay tree are based on one basic operation, called splaying. Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree. To do this, the element is first found with a standard tree search, then tree rotations are performed in a specific fashion to bring the element to the top.

Good performance for a splay tree depends on the fact that certain elements in the tree will be accessed more often than others. This is true for nearly all practical applications, and is particularly useful for implementing caches; however it is important to note that for uniform access, a splay tree's performance will be considerably (but not asymptotically) worse than the corresponding simple binary search tree.

External Links

• NIST's Dictionary of Algorithms and Data Structures: Splay Tree
• The ACM Digital Library: the original publication describing splay trees NB full access requires an ACM Web Account