Splay tree

A splay tree is a self-adjusting binary search tree. It performs basic operations such as insertion, look-up and removal in O(log(n)) [amortized 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 preformed to bring the element to the top.

do a psuedocode? example implementation of splay here...

Reference: [The ACM Digital Library] has the original publication describing splay trees.