Splay Tree
Visualize a self-adjusting search tree that moves recently accessed elements to the root.
By Riano · Published · Updated · Report a correction
Splay Tree
Concept Overview
A Splay Tree is a self-adjusting binary search tree that stores no explicit height or color metadata. Instead, every insertion, lookup, or access performs a sequence of double rotations (splaying) that moves the accessed node x all the way to the root while roughly halving the depth of every node along the access path, achieving O(log n) amortized time per operation.
Mathematical Definition
Let S(x) be the number of nodes in the subtree rooted at x, and define the rank r(x) = log2 S(x) and tree potential Φ = Σx r(x):
Amortized cost of splaying node x at root t:
a ≤ 3(r(t) − r(x)) + 1 ≤ 3 log2 n + 1 = O(log n)
Worked Example: Why Zig-Zig Differs from Two Single Rotations
Suppose keys 10, 20, 30 are inserted in ascending order, splaying each new node to the root:
- Insert 10:
10becomes the root. - Insert 20 (Zig step):
20is attached as the right child of root10. Because10has no parent, a single Zig (Left) rotation places20at the root with left child10. - Insert 30 (Zig): Attached as the right child of root
20and splayed via a single Zig (Left) rotation, forming a left spine30 → 20 → 10of depth 2. - Now insert 5 (Zig-Zig + Zig):
5enters at the bottom of the left spine30 → 20 → 10 → 5. Both5and its parent10are left children of grandparent20, triggering a Zig-Zig (Right-Right) step that rotates grandparent 20 with parent 10 first, then rotates10with5, followed by a final Zig at root30. Folding the grandparent edge first is what halves path depth and makes amortized O(log n) hold.
Interactive Experiment: What to Enter and Observe
Open the Splay Tree module to watch newly inserted keys splay to the root and observe the sequence of Zig, Zig-Zig, and Zig-Zag steps:
- Set Nodes to Insert to
10and Animation Speed to1200ms. - Note the first value in the Pending Insertions queue, then click Play.
- For each insertion, confirm two things on the canvas and in the Status card: (a) the newly inserted value always finishes at the amber-highlighted root node at the top of the canvas, and (b) the Status card lists the exact sequence of splay steps (e.g.,
Zig-Zag (Left-Right) -> Zig (Right)) used to bring it there. - Press Pause when a deep leaf is inserted to compare how a
Zig-Zigstep restructures the path into a more balanced subtree before the next key is inserted.
Assumptions & Limitations
Splay trees guarantee O(log n) amortized time over a sequence of operations rather than O(log n) worst-case time for every individual lookup. A single access on a degenerate chain of n nodes can take Θ(n) time, although the resulting Zig-Zig rotations immediately compress that chain's depth by roughly half so subsequent operations are fast. In addition, because even read-only lookups mutate tree pointers by splaying the accessed node to the root, splay trees require synchronization locks under concurrent read workloads.
References
Sleator and Tarjan introduced splay trees and proved the Access Lemma, Static Optimality Theorem, and Working-Set Theorem in their landmark 1985 paper:
- Sleator, D. D., & Tarjan, R. E. (1985). Self-Adjusting Binary Search Trees. Journal of the ACM, 32(3), 652–686.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Splay Tree module.
Try Splay Tree on Riano →