Adapting to access
A splay tree is a binary search tree that reorganizes itself on every access. Whenever you search, insert, or delete a key, the tree splays that key, a sequence of rotations that carries it all the way up to the root. Recently used keys end up near the top, so workloads with locality run fast.
The three splay steps
Splaying repeatedly applies one of three moves until the node reaches the root:
- Zig: the node's parent is the root, so one rotation finishes the job.
- Zig zig: node and parent are both left children, or both right children. Rotate the grandparent first, then the parent.
- Zig zag: node and parent turn opposite directions. Rotate the parent, then the grandparent.
The zig zig versus zig zag distinction is what gives splay trees their amortized guarantee, distinguishing them from naive move to root.
Cost in the long run
Any single operation may be slow, but amortized over a sequence the average cost is logarithmic. Splay trees need no balance factors or color bits, just rotations, which keeps the code small.
Key idea
Splaying each accessed key to the root makes hot data cheap to reach and gives logarithmic amortized cost with no stored balance data.