Data Structures
Splay Tree
Difficulty: Advanced
Real workloads are rarely uniform. Web caches, compiler symbol tables, and network routers all access the same handful of items thousands of times in a row before moving on. A Splay Tree turns that observation into a balancing strategy:...
Splay Tree
Real workloads are rarely uniform. Web caches, compiler symbol tables, and network routers all access the same handful of items thousands of times in a row before moving on. A Splay Tree turns that observation into a balancing strategy: every access (search, insert, or delete) drags the touched node to the root through a sequence of rotations, so frequently used keys stay shallow and effectively pay O(1) after the first hit.
This lesson covers the three splay rotation cases (zig, zig-zig, and zig-zag) that move a target node toward the root in pairs of levels, the modified search, insert, and delete operations that always end with a splay, and the amortized analysis that yields O(log n) per operation across any sequence of m operations even though individual operations can be O(n) in the worst case. You will also meet the working set theorem, which is the formal version of the temporal-locality intuition.
In Binary Search Tree (BST), accesses left the tree shape unchanged; balanced variants enforced strict structural invariants. The splay tree refuses both options and instead lets the access pattern itself reshape the tree, with no balance factor or color bit stored anywhere.
Next, Treap (Randomized BST) keeps the same single-bit-of-extra-state simplicity but uses random priorities (rather than recent access) to control balance.
Prerequisites:
Binary Search Tree (BST)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain the self-adjusting BST concept and why moving accessed nodes to the root can yield amortized O(log n) performance.
Implement the three splay rotation cases: zig, zig-zig, and zig-zag.
Trace a splay operation on paper given a tree and a target key.
Implement splay tree search, insert, and delete operations using the splay primitive.
Describe the working set property and explain when splay trees outperform balanced BSTs.
Compare splay trees with AVL and Red-Black trees in terms of worst-case guarantees, code complexity, and practical use cases.
Why This Matters
01
Splay trees demonstrate that you do not always need strict balance metadata to achieve logarithmic amortized performance. The self-adjusting property is an elegant alternative to the complex rotation rules of AVL and Red-Black trees.
02
The working set property means splay trees automatically adapt to access patterns: frequently accessed items migrate toward the root and stay fast to reach. This makes them a natural fit for caching layers and compiler symbol tables.
03
Understanding amortized analysis through splay trees deepens your grasp of how algorithms that look expensive per-operation can still be efficient over time -- a concept that appears in dynamic arrays, hash tables, and many real systems.
04
Splay trees are a classic interview topic at companies that value theoretical depth. Interviewers may ask you to compare them with AVL/Red-Black trees or analyze their amortized complexity.
Key Terms
7 terms you'll encounter in this lesson
Splay Tree
A self-adjusting binary search tree where every access (search, insert, delete) moves the accessed node to the root via a sequence of rotations called splaying.
Splay Operation
A series of rotations (zig, zig-zig, zig-zag) applied bottom-up from a target node to the root, bringing the target node to the root position while roughly halving the depth of every node on the access path.
Zig
A single rotation (left or right) applied when the target node is a direct child of the root. It moves the target to the root in one step.
Zig-Zig
A double rotation applied when the target node and its parent are both left children (or both right children) of their respective parents. The parent is rotated first, then the grandparent.
Zig-Zag
A double rotation applied when the target node is a left child but its parent is a right child (or vice versa). The target is rotated twice: first around its parent, then around its grandparent.
Amortized O(log n)
A complexity guarantee meaning that while a single splay operation may take O(n) time, any sequence of m operations takes at most O(m log n) total time, giving O(log n) per operation on average.
Working Set Property
The property that accessing an item that was accessed recently (within the last k operations) costs O(log k) rather than O(log n), because recent items remain near the root.
Heads Up
Common misconceptions to watch out for
"Splay trees guarantee O(log n) for every single operation"
Individual splay operations can take O(n) in the worst case. The O(log n) guarantee is amortized: any sequence of m operations on an n-node tree takes O(m log n) total. Some operations are expensive, but they restructure the tree so subsequent operations are cheap.
"Splaying is just a simple rotation like in AVL trees"
Splaying uses three specific rotation patterns (zig, zig-zig, zig-zag) that differ from AVL's four cases. The zig-zig case is particularly important: it rotates the grandparent first (not the parent), which is what gives the amortized guarantee. Simply rotating bottom-up without the zig-zig pattern gives O(n) amortized cost.
"Splay trees are always worse than AVL/Red-Black trees because of their O(n) worst case"
For workloads with temporal locality (recently accessed items are likely to be accessed again), splay trees often outperform balanced BSTs because frequently accessed nodes cluster near the root. They also use less memory since they store no balance metadata.
"You can skip the splay after a search if the key is not found"
Even when a search fails, you must splay the last node on the access path. This is essential for maintaining the amortized complexity guarantee. Skipping splay operations breaks the potential function argument.