Splay Trees

From

A Splay tree is not actually a data structure, rather it is a set of rules for improving the performance of a BST, and they were first introduced by D. D. Sleator and R. E. Tarjan in 1985.

Splay Tree behavior

The principle behind a Splay tree is that of locality of reference, the same principle that is behind cache memory. Whenever a node S is accessed, inserted or searched, it is moved by a series of rotations to the root of the tree. This movement is called splaying. If a node is deleted, its former parent is splayed. No single operation on a splay tree is guaranteed to be efficient, rather a series of operations over time become efficient, so that the average cost per operation is low.

Experimental studies claim that a random sequence of dictionary operation are actually faster with a Splay tree than with either an AVL tree or a Red-Black tree. And, a Spay tree has the added advantage that it is easier to code than either an AVL or a Red-Black tree.