← Back to the red black trees page
Splay Tree
No stored balance data at all: every access rotates the touched node to the root, so hot items become cheap automatically.
What to know
- Zig, zig-zig, zig-zag rotation patterns move accessed nodes up.
- Amortized O(log n) even though a single operation can be O(n).
- Naturally cache-like: recently used keys sit near the root.
In the wild: Caches with skewed access, rope data structures in editors, network flow libraries.
Algorithms to reach for
Splaying
O(log n) amortizedSelf-optimizing access; hot keys float to top
Split / join
O(log n) amortizedCut and merge ordered sets by splaying a boundary