A splay tree is a self-adjusting BST: every access (search, insert, delete) moves the touched node to the root through a sequence of rotations called "splaying." It has no balance invariants but achieves amortized O(log n) per operation, and recently-accessed keys become very fast (working-set theorem).
Daniel Sleator and Robert Tarjan introduced splay trees in 1985. Where AVL and red-black trees store balance information and repair the shape after every update, a splay tree stores nothing extra and instead restructures itself on every access. Frequently used keys drift toward the root, and long paths are roughly halved each time something deep is touched, which is enough to guarantee good total cost over any sequence of operations.
A naive "move to root" heuristic that simply rotates x with its parent repeatedly can leave a long path almost as long as before, and there are access sequences that cost O(n) per operation forever. The zig-zig case fixes this by rotating the grandparent before the parent. The effect is that every node on the access path ends up roughly half as deep as it was, which is what the amortized analysis relies on.
The values come from running the Python code below: after the seven inserts the tree is the chain shown first (each insert splayed the new key to the root, and every later key happened to be larger than the existing root's left side). Calling splay(t.root, 40) performs zig-zig steps up the left spine; 40 becomes the root, and nodes that were above it are redistributed into the right subtree. Accessing 40 cost five comparisons once, but every key that was on that path is now cheaper to reach.
| Average | Worst | Space | ||||||
|---|---|---|---|---|---|---|---|---|
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion | Worst |
N/A |
Θ(log n) |
Θ(log n) |
Θ(log n) |
N/A |
O(log n) |
O(log n) |
O(log n) |
O(n) |
Splaying applies one of three rotation patterns — zig (parent is root), zig-zig (same side), zig-zag (different sides) — repeatedly until the target reaches the root. Amortized analysis (Sleator & Tarjan, 1985) shows total cost over m operations is O(m log n) even though individual ops can be O(n).
class Node:
__slots__ = ("key", "left", "right")
def __init__(self, key):
self.key, self.left, self.right = key, None, 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):
"""Splay the node with `key` (or last accessed) to the root."""
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 root if root.left is None else _rotate_right(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 root if root.right is None else _rotate_left(root)
class SplayTree:
def __init__(self): self.root = None
def insert(self, key):
if self.root is None:
self.root = Node(key); return
self.root = splay(self.root, key)
if self.root.key == key: return
n = Node(key)
if key < self.root.key:
n.right = self.root; n.left = self.root.left; self.root.left = None
else:
n.left = self.root; n.right = self.root.right; self.root.right = None
self.root = n
t = SplayTree()
for k in [50, 30, 20, 40, 70, 60, 80]: t.insert(k)
print(t.root.key) # 80 — last inserted bubbled to the rootAll operations are expressed in terms of splay. Search splays the key and checks the root. Delete splays the key to the root, removes it, then splays the maximum of the left subtree to the top of that subtree so it has no right child, and attaches the old right subtree there.
def contains(tree, key):
tree.root = splay(tree.root, key)
return tree.root is not None and tree.root.key == key
def delete(tree, key):
if tree.root is None:
return
tree.root = splay(tree.root, key)
if tree.root.key != key:
return # not present
left, right = tree.root.left, tree.root.right
if left is None:
tree.root = right
else:
left = splay(left, key) # key is larger than everything in left,
left.right = right # so its maximum rises and has no right child
tree.root = left
t = SplayTree()
for k in [50, 30, 20, 40, 70, 60, 80]:
t.insert(k)
print(contains(t, 40), t.root.key) # True 40
delete(t, 40)
print(t.root.key) # 30 - the max of the old left subtreeSplitting and joining trees work the same way, which makes splay trees convenient for sequence data structures such as ropes and for link-cut trees, where whole subtrees are cut and reattached.
When to use a splay tree. They fit workloads with strong temporal locality: caches, recently used symbol tables, and sequences where the same small set of keys is accessed repeatedly. The code is short because there is no balance metadata. Prefer a red-black tree or a B-tree when you need worst-case per-operation bounds (for latency-sensitive systems), concurrent readers, or a structure that does not change shape on reads.
splay follows the access path; on long chains use a top-down iterative splay.splay returns the new root; ignoring the return value loses the tree.