# 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
- 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
| |

Implementation: | `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