Splay tree

A splay tree is a self-balancing binary search tree. It performs basic operations such as insertion, look-up and removal in O(log(n)) average (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 combined with 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. One way to do this is to first perform a standard binary tree search for the element in question, and then use tree rotations in a specific fashion to bring the element to the top. Alternatively, a bottom-up algorithm can combine the search and the tree reorganization.

Good performance for a splay tree depends on the fact that it is self-balancing and that frequently accessed nodes will move nearer to the root where they can be accessed more quickly. This is an advantage 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 a simple (but necessarily somewhat balanced) binary search tree.

Splay trees also have the advantage of being considerably simpler to implement than other self-balancing binary search trees, such as red-black trees or AVL trees, while their average-case performance is just as efficient. They also don't need to store any bookkeeping data, thus minimizing memory requirements. However, these other data structures provide worst-case time guarantees, and can be more efficient in practice for uniform access.

It is possible to create a persistent version of splay trees which allows access to both the previous and new versions after an update. This requires amortized O(log n) space per update.

The splay operation

To do a splay, we carry out a sequence of rotations, each of which moves the target node N closer to the root. Each particular step depends on only two factors:

• Whether N is the left or right child of its parent node, P,
• Whether P is the left or right child of its parent, G (for grandparent node).

Thus, there are four cases:

Case 1: N is the left child of P and P is the left child of G. In this case we perform a double right rotation, so that P becomes N's right child, and G becomes P's right child.

Case 2: N is the right child of P and P is the right child of G. In this case we perform a double left rotation, so that P becomes N's left child, and G becomes P's left child.

Case 3: N is the left child of P and P is the right child of G. In this case we perform a rotation so that G becomes N's left child, and P becomes N's right child.

Case 4: N is the right child of P and P is the left child of G. In this case we perform a rotation so that P becomes N's left child, and G becomes N's right child.

Finally, if N doesn't have a grandparent node, we simply perform a left or right rotation to move it to the root. By performing a splay on the node of interest after every operation, we keep recently accessed nodes near the root and keep the tree roughly balanced, so that we achieve the desired amortized time bounds.

References