# Splay tree

Invented by Sleator, Tarjan (1985) inspired by the move-to-front heuristic for linked lists: each time we access an element, we move it to the front; this way the more frequently used items tend to stay near the beginning and can be found easily in a splay tree, each time we access an element, we “splay” it to the root the splay operation is tricky; note that just moving or “bubbling” the node up by simple rotations doesn’t work! relatively easy implementation (once the splaying operation is implemented, all other operations are trivial) $O(\log n)$ amortized time for all dictionary operations base for linking and cutting trees which are used in a fast ($O(nm\log n)$ time) algorithm for maximum flow the $O(\log n)$ time is only amortized; individual operations may take $\Omega(n)$ time many rotations splay_set, splay_multiset, and splaytree classes in Boost.Intrusive library

## Splaying $x$

The fundamental operation of splay trees is splaying. Operation splay(x) finds node with value $x$ in the tree and using rotations, bubbles it up to the root. If $x$ is not in the tree, we splay the last node we visit while searching for $x$, which is either the next higher or lower value.

When bubbling $x$ up, there are three cases depending on the relationship of $x$ to its parent $y$ and grandparent $z$:

Zig-zag case: When $x$$y$$z$ is a zig-zag path, i.e., $x$ is right child of $y$ but $y$ is left child of $z$, or symmetrically, if $x$ is left child and $y$ is right child, we rotate $x$ twice:

Zig-zig case: When $x$ and it’s parent $y$ are both left or both right children of their parents, we first rotate $y$, then $x$:

Zig case: If $y$ is already root (there is no grandparent), we just do a simple rotation:

## Implementation

The good news is that if we implement splay, implementing all the other operations is easy:

• find minimum: we just splay($-\infty$) – this will bring minimum into the root
• find maximum: splay($\infty$)
• find x: splay(x), then either $x$ is in the root, or is not in the tree
• split by x: if $r$ is the root of the tree, the left subtree consists of all the values less than $r$ and the right subtree of all the values more than $r$; splaying $x$ will rearrange the tree so that $x$ (or its successor or its predecessor) gets to the root so the whole left subtree will be less than $x$ and right subtree more than $x$ (we just check whether the root itself is lower or higher than $x$)
• insert x: first split the tree by $x$ into $T_1, T_2$, then make $x$ the root with left subtree $T_1$ and right subtree $T_2$
• merge $T_1$, $T_2$: if we have two trees, $T_1,T_2$, and all values of $T_1$ are less than any value of $T_2$, we can easily merge them: just splay($\infty$) in $T_1$ – this will move maximum into the root so the root will have no right child; then just link root of $T_2$ as the right child of $T_2$
• delete x: splay($x$) – this brings $x$ into the root; cut it and merge its left and right subtree

## References

• D.D. Sleator and R.E. Tarjan. Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652-686, 1985. [bib] [pdf]