Splay tree

Invented by Sleator, Tarjan (1985)
Idea:
  • 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!
Advantages:
  • relatively easy implementation (once the splaying operation is implemented, all other operations are trivial)
  • \(O(\log n)\) amortized time for all dictionary operations
  • adapts to the input (see theorems such as static optimality, static/dynamic finger, working set and dynamic optimality conjecture)
  • base for linking and cutting trees which are used in a fast (\(O(nm\log n)\) time) algorithm for maximum flow
Disadvantages:
  • the \(O(\log n)\) time is only amortized; individual operations may take \(\Omega(n)\) time
  • many rotations which slow down the tree in practice
Implementation: splay_set, splay_multiset, and splaytree classes in Boost.Intrusive library
[You can download the application for offline viewing.]

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]