What is a Splay Tree?
Learn what a splay tree is, how zig/zig-zig/zig-zag rotations work, amortized O(log n) bounds, and how to answer this interview question.
Expected Interview Answer
A splay tree is a self-adjusting binary search tree that moves any node accessed — via search, insert, or delete — to the root using a sequence of rotations called splaying, so recently or frequently accessed elements stay near the top and become cheap to reach again.
Splaying uses three rotation patterns depending on the accessed node's position relative to its parent and grandparent: zig (single rotation when the node's parent is the root), zig-zig (two same-direction rotations when node, parent, and grandparent are aligned), and zig-zag (two opposite-direction rotations when they zigzag). Every operation ends with the accessed node at the root, regardless of whether it was a search, insert, or delete. Individual operations can cost O(n) in the worst case on an unlucky access pattern, but amortized analysis shows any sequence of m operations costs O(m log n) total, which is why splay trees are analyzed with amortized rather than worst-case-per-operation bounds. This makes them especially good for workloads with locality of reference, like caches or LRU-style access patterns, where recently touched items are likely to be touched again soon.
- Amortized O(log n) per operation over any sequence
- Recently accessed elements become fast to re-access
- No extra balance metadata (like heights or colors) to maintain
- Naturally adapts to access-pattern locality
AI Mentor Explanation
A splay tree is like a kit bag where whichever piece of gear you just used gets moved to the very top of the bag through a sequence of small rearranging shuffles, not just tossed on top. If you grab a bat that's buried deep, you don't just yank it out; you repeatedly swap it past the items directly above it in pairs, following a zig, zig-zig, or zig-zag pattern depending on how it's nested, until it lands on top. Digging for a rarely-used item once in a while can be slow, but because each use also reorganizes the bag, your most-used gear stays consistently easy to grab. Over a whole match's worth of digs, the total digging time stays low even though any single dig could occasionally be deep.
Step-by-Step Explanation
Step 1
Access a node
Perform a normal BST search, insert, or delete to reach the target node.
Step 2
Apply zig for a root-adjacent node
If the node's parent is the root, do a single rotation to bring it to the root.
Step 3
Apply zig-zig or zig-zag otherwise
If node, parent, and grandparent line up the same way, rotate twice in that direction (zig-zig); if they zigzag, rotate in opposite directions (zig-zag).
Step 4
Repeat until the node is the root
Continue splaying rotations up the tree until the accessed node becomes the new root.
What Interviewer Expects
- Explain that every access moves the touched node to the root via splaying
- Name the three rotation cases: zig, zig-zig, zig-zag
- State the bound is amortized O(log n), not worst-case-per-operation
- Give a use case that benefits from access locality, like caches
Common Mistakes
- Claiming splay trees guarantee O(log n) for every single operation
- Confusing zig-zig with zig-zag rotation patterns
- Forgetting that even search operations trigger a splay, not just insert/delete
- Not mentioning amortized analysis as the reason the average bound holds
Best Answer (HR Friendly)
“A splay tree is a binary search tree that reorganizes itself every time you touch a node, moving that node all the way up to the root through a series of rotations. I like it for workloads where recently accessed items tend to get accessed again soon, like a cache, because even though a single access can occasionally be slow, the average cost across many accesses stays logarithmic.”
Code Example
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def rotate_right(x):
y = x.left
x.left = y.right
y.right = x
return y
def rotate_left(x):
y = x.right
x.right = y.left
y.left = x
return y
def splay(root, key):
if root is None or root.key == key:
return root
if key < root.key:
if root.left is None:
return root
if key < root.left.key:
root.left.left = splay(root.left.left, key)
root = rotate_right(root)
elif key > root.left.key:
root.left.right = splay(root.left.right, key)
if root.left.right:
root.left = rotate_left(root.left)
return rotate_right(root) if root.left else root
else:
if root.right is None:
return root
if key > root.right.key:
root.right.right = splay(root.right.right, key)
root = rotate_left(root)
elif key < root.right.key:
root.right.left = splay(root.right.left, key)
if root.right.left:
root.right = rotate_right(root.right)
return rotate_left(root) if root.right else rootFollow-up Questions
- How does amortized analysis prove the O(log n) bound for splay trees?
- Why does even a search operation trigger a full splay?
- How would you use a splay tree to implement an efficient LRU cache?
- How does a splay tree compare to an AVL or red-black tree in practice?
MCQ Practice
1. What happens to a node after it is accessed in a splay tree?
Splaying rotates the accessed node all the way up to the root, regardless of whether the access was a search, insert, or delete.
2. What is the amortized time complexity of operations on a splay tree?
Any sequence of m operations on a splay tree costs O(m log n) total, giving an amortized O(log n) per operation, even though a single operation can cost O(n).
3. Which rotation pattern is used when a node, its parent, and its grandparent are all aligned in the same direction?
The zig-zig case applies two same-direction rotations when the node-parent-grandparent chain is aligned straight.
Flash Cards
What operation does every access (search, insert, or delete) trigger in a splay tree? — Splaying — a sequence of rotations that moves the accessed node to the root.
Name the three rotation cases in splaying. — Zig (single rotation), zig-zig (two same-direction rotations), and zig-zag (two opposite-direction rotations).
Is a splay tree's O(log n) bound per-operation guaranteed or amortized? — Amortized — a single operation can cost O(n), but any sequence of m operations costs O(m log n) total.
What kind of workload benefits most from a splay tree? — Workloads with access locality, like caches, where recently touched items are likely accessed again soon.