Splay Tree

Why splay matters

• Cache patterns. Hot keys migrate to the root. With a Zipf access distribution (typical for web traffic, file access, database keys), the top 20% of keys absorb 80% of accesses. A splay tree puts those keys near the root, giving O(log(working-set-size)) per access — often much better than O(log n).
• Kernel memory. Linux's vm_area_struct used a splay tree for many years to track virtual memory regions per process, exploiting locality of mmap/brk calls. (Replaced by red-black for worst-case predictability and concurrency, but the rationale for the original splay choice still applies to single-threaded data.)
• Theorem-rich. Splay trees prove static optimality, the working-set bound, the sequential-access bound (n consecutive accesses cost O(n) total — equivalent to inorder traversal), and the dynamic-finger property. No other dynamic BST proves this many adaptivity bounds.
• No node metadata. Unlike AVL (balance factor) or red-black (color bit), splay trees store only key, left, right, and optionally parent. Memory footprint matches a plain BST.
• Persistent and concurrent variants. Persistent splay (e.g., for functional programming) requires care because every read mutates. Concurrent splay trees are an active research area.
• Used in glibc, sed, gcc. Libstdc++ uses splay-like structures internally; sed's pattern-space buffer is splay-based; some allocators splay-track free lists.

Zig, zig-zig, zig-zag — the three splay steps

• Zig (terminal step). When x's parent p is the root, perform a single rotation of x around p. Used at most once per splay, when x is one level from the root.
• Zig-zig (same-side). When x and p are both left children (or both right children) of their respective parents, rotate the grandparent g first, then rotate p. The reverse order — rotate p first — gives a structurally different result and breaks the amortized bound. Lift x by 2 depth levels per zig-zig.
• Zig-zag (opposite-side). When x is a left child of p but p is a right child of g (or symmetric), rotate at p, then at g. After zig-zag, x has g and p as its two children, both balanced — locally balancing the access path.
• Sequence. Repeat zig-zig and zig-zag until x's parent is the root, then perform zig once. After the final zig, x is the root.
• Top-down vs bottom-up. The original Sleator-Tarjan algorithm walks down to find x then up to splay (bottom-up). A top-down variant splits the tree into left and right spines as it descends and joins them at x at the end — saves a parent pointer per node.

Operations

• Search(T, k). Walk like a normal BST. Whether you find k or hit a null, splay the last node visited (k itself, or its predecessor or successor) to the root. Amortized O(log n).
• Insert(T, k). Standard BST insert, then splay the new node to the root.
• Delete(T, k). Splay k to the root. Now k has left subtree L and right subtree R. Splay the largest element of L to the root of L; this leaves L's new root with no right child. Attach R as that new root's right child.
• Join(L, R). Precondition: every key in L < every key in R. Splay the largest key of L to the root, then attach R as its right child. O(log n) amortized.
• Split(T, k). Splay k to the root. The left subtree is L (keys < k), and {k} ∪ right subtree is R. Or define exclusive vs inclusive based on convention.
• All operations. Reduce to splay + a constant amount of pointer surgery. Total amortized cost: O(log n) per operation.

Splay tree theorems

• Balance theorem. Any sequence of m accesses on an n-node splay tree takes O((m + n) log n) total time. Equivalent to O(log n) amortized per access.
• Static optimality. For any sequence sigma of m accesses with frequencies f_i, splay-tree cost is O(m + sum f_i log(m / f_i)) — within a constant of the entropy bound, hence within a constant of the best static BST.
• Static finger. Fix a "finger" key f. The cost of accessing key x_t at time t is O(log(|rank(x_t) - rank(f)| + 2)). Useful when accesses cluster around a fixed pivot.
• Working set. If x has been accessed t(x) times since its last access in a sequence, the amortized cost of accessing x is O(log(t(x) + 2)). Recent keys are cheap.
• Sequential access. Inorder traversal of all n keys costs O(n) total. Each successor is found in O(1) amortized.
• Dynamic finger (proven 2000). Cost of accessing x_t after x_{t-1} is O(log(|rank(x_t) - rank(x_{t-1})| + 2)) — the finger moves with each access.
• Dynamic optimality conjecture (open). Splay trees are conjectured to be O(1)-competitive against the optimal offline BST. Best known competitive ratio is O(log log n) via Tango trees and multi-splay trees.

The access lemma and potential function

• Size and rank. s(x) = number of nodes in x's subtree (including x). r(x) = floor(log2(s(x))).
• Potential. Phi = sum over all nodes x of r(x). Phi is a non-negative integer.
• Access lemma. Splaying node x in a tree of root T has amortized cost <= 3 * (r(T) - r(x)) + 1.
• Per-step credit. Each zig-zig and zig-zag step on x costs amortized at most 3 * (r_after(x) - r_before(x)). Each zig step costs at most 3 * (r_after(x) - r_before(x)) + 1.
• Telescoping. Summing along the splay path: total amortized = 3 * (r(T) - r(x)) + 1 = O(log n) since r(T) <= log2(n).
• Why zig-zig before zig-zag. The case analysis reveals zig-zig has tighter slack in the telescoping; reversing the order of rotations within a zig-zig breaks the inequality.

Common misconceptions

• "Always O(log n)." Single ops can be O(n) — splaying a leaf in a linear chain costs n. The O(log n) is amortized over a sequence; for a single isolated query, expect linear in the worst case.
• "Just like AVL." AVL rotates only on imbalance, never on read. Splay rotates on every access — even reads. That makes splay write-heavy and unfit for read-only concurrent contexts.
• "Zig-zag is the same as a double rotation." Mechanically yes, but the order matters: rotate at parent, then at grandparent. Doing them in the reverse order ruins the amortized bound.
• "Splaying improves balance." It tends to balance the access path; it does not balance the tree as a whole. Worst-case height of a splay tree can be n at any moment.
• "Splay trees are O(log n) per op like red-black." Different guarantees: red-black is worst-case O(log n) per op; splay is amortized O(log n). For latency-sensitive systems, the distinction matters.
• "Persistent / immutable splay trees are easy." They're hard precisely because reads mutate. Each read creates a new version; bookkeeping is non-trivial.
• "Splay trees beat hash tables for caches." Hash tables are O(1) average for point lookups. Splay trees beat hash tables only when ordered queries (range, predecessor, successor) matter or when access patterns are highly skewed.

Pseudocode

• Splay(x). While x has a parent, identify the configuration: if grandparent null → zig; else if zig-zig pattern → rotate(g, parent_dir); rotate(p, x_dir); else (zig-zag) → rotate(p, x_dir); rotate(g, opposite_dir).
• Rotate(node, direction). Swap node with its child on the given side, repointing parent and the moved child's other subtree. Standard BST rotation, ~10 lines.
• Search. Find x as in BST, then splay(x).
• Insert. BST-insert, then splay(new_node).
• Delete. Splay(k); set new_root = join(left_subtree, right_subtree).
• Lines of code. A complete splay tree fits in 100 to 150 lines of C++. Less than half the size of a red-black tree implementation.