Most balanced trees treat every key equally. A splay tree plays favourites — cleverly. Every time you search, insert, or delete a node, it splays that node to the root through a sequence of rotations. The payoff: keys you use often, or used recently, drift toward the top and become cheap to reach again — a tree that adapts its shape to your access pattern with no stored balance factors, colors, or extra fields at all. Operations are O(log n)amortized. Access a few keys and watch each one get yanked up to the root.
O(log n) amortized · every access splays the node to the root · no balance metadata
splay
Rotate a node up to the root through zig / zig-zig / zig-zag steps.
self-adjusting
The tree restructures on every access — hot keys migrate toward the top.
amortized
Any single op may be slow, but any sequence averages O(log n) per op.
no metadata
Unlike AVL/red-black, nodes store no balance factor or color — just splaying.
splay.js — the root is whatever you touched last
Ready
A binary search tree. Every time you access a key, the tree splays it — rotating it all the way to the root. Recently used keys stay near the top. Access a key and watch it rise.
–
root now
–
accessed
0
height
How it works
Splaying moves a node to the root using three cases, applied repeatedly until it arrives. A zig is a single rotation used when the node’s parent is the root. A zig-zig handles the case where node and parent are both left children (or both right): you rotate the grandparent first, then the parent — this is the key case that keeps long paths from re-forming. A zig-zag handles the node being a left child of a right child (or vice versa): rotate the parent, then the grandparent. Each access does O(depth) work but also roughly halves the depth of everything along the path, which is why a whole sequence of operations averages to O(log n) each — the amortized guarantee.
1
Find the key as usual
Descend the BST by comparisons to locate the key (or where it would go, for insertion).
2
Splay it to the root
Rotate the node upward using zig, zig-zig, and zig-zag steps until it becomes the root. BST order is preserved throughout.
3
Reap the locality
The just-accessed key is now the root, and everything along its old path got shallower. Accessing it again — or nearby keys — is now cheap.
✓
Amortized O(log n)
A single splay can cost O(n) on a bad tree, but the restructuring pays for itself: any sequence of m operations runs in O(m log n) total. No balance metadata is ever stored.
Operations
O(log n) amort.
Worst single op
O(n)
Metadata
none
Great for
skewed access
The code
# after finding a node, splay it to the root (bottom-up sketch)def splay(node):
while node.parent:
p, g = node.parent, node.parent.parent
if g isNone:
rotate(node) # zig: p is rootelif (node is p.left) == (p is g.left):
rotate(p); rotate(node) # zig-zig: same sideelse:
rotate(node); rotate(node) # zig-zag: opposite sides# every access ends with the touched node at the root
Quick check
1. What does a splay tree do on every access?
Every search, insert, or delete ends by splaying the touched node to the root through rotations. This makes recently and frequently used keys cheap to reach again.
2. What does “O(log n) amortized” mean for a splay tree?
Amortized means the guarantee is over a sequence: one splay can be O(n) on a bad shape, but the restructuring it does makes later operations cheaper, so any sequence averages O(log n) per operation.
3. What extra per-node metadata does a splay tree store versus AVL or red-black trees?
Splay trees keep no balancing metadata. AVL trees store heights/balance factors and red-black trees store colors; a splay tree just splays on access, which is part of its appeal.
FAQ
What is a splay tree?
A self-adjusting BST that moves every accessed node to the root via rotations ("splaying"), keeping recently/frequently used keys near the top for fast repeat access. It stores no balancing metadata and achieves O(log n) amortized search, insert, and delete.
What are zig, zig-zig, and zig-zag?
The three splay cases. Zig: a single rotation when the parent is the root. Zig-zig: node and parent on the same side (both left or both right) — rotate grandparent then parent. Zig-zag: opposite sides — rotate parent then grandparent. Repeating them lifts the node to the root.
When are splay trees a good choice?
When access is skewed or has temporal locality — splay trees exploit it automatically, often beating balanced trees on cache-like workloads, and they’re simple with easy split/merge. Downsides: no worst-case per-op bound, and every access mutates the tree (bad for concurrent reads).
How do splay trees compare to AVL and red-black trees?
AVL/red-black guarantee worst-case O(log n) per op via stored balance data. Splay trees give O(log n) amortized only (a single op can be O(n)), store no balance data, adapt to access patterns, and are simpler. Balanced trees for worst-case bounds or concurrent reads; splay trees for locality and simplicity.