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.