Splay Tree
A self-adjusting BST that moves every accessed node to the root via a sequence of rotations ("splaying") — no explicit balance invariant, but frequently-accessed nodes stay cheap to reach.
Every search, insert, or delete ends with the target node "splayed" to the root through a series of rotations, applied two levels at a time (zig-zig or zig-zag), not one at a time — this two-level pattern is what gives splay trees their good amortised bounds instead of just being "move to front".
There is no explicit height or colour invariant — a splay tree can be arbitrarily unbalanced at any instant. What is guaranteed is amortised O(log n) per operation over any sequence of operations, proven via a potential-function argument, not a worst-case-per-operation guarantee.
The practical payoff is adaptivity: a working set of frequently-accessed keys migrates near the root and stays cheap, similar in spirit to an LRU cache — repeated access patterns get faster over time, something a strictly balanced tree cannot do.
Operations
| Operation | Complexity |
|---|---|
| access/search (+ splay) | O(log n) amortised |
| insert (+ splay) | O(log n) amortised |
| delete (+ splay) | O(log n) amortised |
| worst single operation | O(n) (rare, self-correcting) |
Where it's used
Caches and working-set-sensitive lookups, garbage collector implementations, network routers (recently-used routes stay fast).