A feature-flag service holds ten thousand keys. Twenty of them are checked on every request. A balanced tree treats every key as equally likely: each lookup pays a full log n, then puts the node back where it was. You keep asking for the same twenty names. The tree never learns.
A splay tree is a BST that rotates the accessed node to the root. The next lookup of that key is a comparison at the top. Recently used keys cluster near the root. There is no height field and no color bit. The restructuring is the balance strategy. Cost is amortized O(log n) over a sequence — not a promise on the next call.
Height, Big-O, and amortized vs worst-case live on the Data Structures Roadmap. This post stays on one idea: splay the node you touched.
It is still a BST
Left subtree smaller, right subtree larger. Search still compares and walks one path. Insert still hangs a node in the hole. The extra rule is what happens after the walk: the node you landed on (or the last node on an unsuccessful path) is rotated all the way to the root.
A node is the usual two children. Parent pointers make the three splay cases obvious; they are not extra payload the JDK would store for you — there is no JDK type here anyway.
final class Node {
int key;
Node left;
Node right;
Node parent;
Node(int key) {
this.key = key;
}
}Without the splay, this is an unbalanced BST: sorted inserts become a spine, and search is O(height). Splaying is the repair. It does not store a balance factor. It moves mass toward the keys you actually use.
Splay: three local cases
A rotation promotes a child and demotes its parent. The BST invariant survives; only the shape changes. Right-rotate when the interesting node is a left child:
Node rotateRight(Node p) {
Node x = p.left;
p.left = x.right;
if (x.right != null) {
x.right.parent = p;
}
x.right = p;
x.parent = p.parent; // also relink that parent from p to x
p.parent = x;
return x;
}rotateLeft is the mirror. One rotation is a zig. Splay is a loop of those rotations until the node is the root — but not “rotate this node up, blindly, one step at a time.” The pairing of steps is the whole invention.
While the node x still has a parent, look at the parent p and the grandparent g:
Zig. p is already the root. One rotation. x becomes the root and you stop.
p x
/ zig / \
x --> A p
/ \ /
A B BZig-zig. x and p lean the same way (both left children, or both right). Rotate p first, then x. Two rotations in the same direction. This is not two independent zigs of x. Pairing them is what makes the amortized bound hold.
g x
/ / \
p zig-zig A p
/ --> / \
x B g
/ \ /
A B CZig-zag. x leans the opposite way from p (left of a right child, or right of a left child). Rotate x twice: first over p, then over the former grandparent. x cuts the corner instead of walking the dog-leg twice.
g x
/ / \
p zig-zag p g
\ -->
xThe dispatcher is a loop, not a recursive “fixup” that stores heights:
void splay(Node x) {
while (x.parent != null) {
Node p = x.parent;
Node g = p.parent;
if (g == null) {
rotate(x); // zig
} else if (sameSide(x, p)) {
rotate(p); // zig-zig: parent first
rotate(x);
} else {
rotate(x); // zig-zag
rotate(x);
}
}
}rotate(x) picks left or right from which child x is. sameSide is true when x and p are both left children or both right. After splay, x is the tree. Search, insert, and delete all end by calling it.
Note: Naive “rotate x toward the root until it arrives” is easier to write and does not give amortized O(log n). Zig-zig exists because two same-direction rotations, ordered parent-then-node, flatten a spine instead of just bubbling one key up a still-tall chain.
Why locality pays
Once a key sits at the root, the next contains of that key is one comparison. Keys you touched recently tend to remain in a small neighborhood of the root — the working set. A request that keeps asking for the same session, the same twenty flags, the same hot product IDs, is walking a short tree even if the cold majority of keys is large.
The methods sit on a tree that holds root. After a splay, that field is the node you just touched:
Node root;
boolean contains(int key) {
Node node = root;
Node last = null;
while (node != null) {
last = node;
if (key == node.key) {
splay(node);
root = node;
return true;
}
node = key < node.key ? node.left : node.right;
}
if (last != null) {
splay(last); // miss: last node on the path becomes root
root = last;
}
return false;
}A miss still splays. The “near miss” is cheap on the next try — useful when lookups cluster around a region of the key space, not only when they repeat one key. Insert is BST-insert then splay the new node. Delete is typically: splay the target to the root, then join the left and right subtrees (splay the maximum of the left, hang the right off it).
The layout is betting that the next operation looks like the last one. When that bet is true, you beat a uniformly balanced tree on the hot keys without storing extra balance state. When the bet is false, you still pay for a rotation after every access.
Amortized is the sequence, not the next call
One splay of a deep leaf walks and rotates a long path. That single operation is O(n) in the worst case. After it, the path is flatter: the nodes you rotated are closer to the root, so later operations on that region are cheaper. Averaged over a long sequence, each operation is O(log n). That is the same kind of promise the roadmap gives ArrayList.add: cheap on average, not a cap on the next call.
m operations on n keys: O((m + n) log n) total
one find of a deep leaf: O(n) that time, then the tree is reshapedThere is no height field to consult, so there is no per-call “I am still balanced” certificate. If the next lookup is the other end of a leftover spine, you pay linear now. Real-time loops and adversarial key sequences care about that now. Caches with temporal locality usually do not.
Java has no SplayTree
The JDK does not ship a splay tree. TreeMap and TreeSet are red-black: worst-case Θ(log n) per mutate, no splay on read. If production Java needs ordered keys, that is the type. Rolling Node plus splay is for learning the move, for a layout where the working set is the product, or for an interview whiteboard. It is not a drop-in NavigableMap.
NavigableMap<Integer, String> flags = new TreeMap<>();
flags.put(20, "checkout");
flags.put(7, "search");
// every get is log n; the tree does not migrate 20 to the rootA hash table is still the default when you do not need order. Splay does not change that. It only competes with other trees, and only when recently used keys matter more than a strict per-call cap.
When not to use a splay tree
Skip splay when:
- You need a guaranteed log n on the next call — real-time, SLAs, adversarial keys. Use a height-balanced tree (AVL) or a red-black tree (
TreeMap/TreeSetin the JDK). Splay’s O(n) single op is not a rarity you can schedule away. - Access is uniform random. Every key is equally likely. Splaying after each lookup is extra rotations for no working-set win. A balanced BST or a hash table matches the job.
- Reads must not mutate. Every successful
containsrotates. Concurrent readers need a lock (or a copy) for what looks like a read. A red-black tree can search without rewriting parent pointers. nis tiny, or you do not need order. A list or aHashMapwill beat a tree of twenty objects. Match the hot operation, as the roadmap asks.
Use a splay tree when the hot path repeats a small working set inside a larger ordered key space and you can live with amortized bounds: a cache of recently touched keys, a buffer of “the files we just opened,” a dictionary whose popular words dwarf the long tail. If the sentence does not mention locality, you probably wanted a balanced tree or a hash table.
How to read the bill
Same shopping-list reading as the roadmap: pick the structure for the operation on the hot path.
Structure: splay tree
search amortized O(log n) — one op can be O(n)
insert amortized O(log n) — BST insert, then splay
delete amortized O(log n) — splay, then join
next same O(1) after a hit — that key is the root
space O(n) — no height / color fields required
JDK none — TreeMap is red-black, not splayAmortized is the row that people erase when they write O(log n) on the slide. For this layout, keep both numbers: the sequence, and the next call.
Cheat sheet
Invariant: still a BST (left < node < right)
Move: after access, rotate that node to the root
Zig: child of root → one rotation
Zig-zig: same lean as parent → rotate parent, then node
Zig-zag: opposite lean → rotate the node twice
Locality: working set stays near the root; repeat hits are cheap
Bound: amortized O(log n); a single op can be O(n)
JDK: no SplayTree; TreeMap / TreeSet are red-black
Skip: need worst-case log n; uniform random access; read-only sharingDo:
- Name a working set (repeated or clustered keys) before you name splay.
- Treat the bound as amortized over a sequence, not as a cap on the next lookup.
- Use
TreeMapwhen production Java needs ordered keys and a per-call log n.
Don’t:
- Quote O(log n) on the next splay of a deep leaf.
- Implement “rotate toward the root” and call it a splay tree — zig-zig is not optional decoration.
- Splay on every lookup when keys are uniform or when readers must not mutate.
Wrap-up
A splay tree keeps the BST law and spends its cleverness on where the last key sits. Zig, zig-zig, and zig-zag are the local moves that put that key at the root without a balance factor. Locality makes the next hit cheap. A long sequence is amortized O(log n). One unlucky op is O(n).
Java does not ship this layout. Ordered keys with a worst-case cap are TreeMap. Lookup without order is a hash table. Splay is the specialized bet: the keys you just touched are the keys you will touch again, and you are willing to pay rotations on reads to keep them close.
For the glossary behind amortized, height, and “what operation is hot,” stay on the Data Structures Roadmap.