The Three Splaying Steps: Zig, Zig-Zag, and Zig-Zig
To splay node $x$ to the root, we repeat two-level steps according to the geometry of $x$, its parent $p$, and its grandparent $g$ until $x$ is the root:
- Zig (Terminal Single Step, $p$ is the root): Rotate the edge $(p, x)$ once so $x$ becomes the new root. Occurs at most once at the very end of
splay(x). - Zig-Zag ($x$ and $p$ lean in opposite directions—e.g., $p = g.\text{left}$ and $x = p.\text{right}$): Rotate $x$ above $p$, then rotate $x$ above $g$ (identical to an AVL LR/RL double rotation).
- Zig-Zig ($x$ and $p$ lean in the SAME direction—e.g., $p = g.\text{left}$ and $x = p.\text{left}$): Rotate $p$ above $g$ FIRST, and then rotate $x$ above $p$! Notice how this differs from Move-to-Root (which would rotate $x$ above $p$ first and then $x$ above $g$). By rotating $g$ first, $g$ is pushed down two levels, folding the long path in half!
| Splay Tree Property / Theorem | Bound (for $M$ Accesses on $N$ Nodes) | Physical Meaning |
|---|---|---|
| Balance Theorem | O((M + N) log N) | Matches worst-case AVL / Red-Black over any sequence |
| Static Optimality Theorem | O(M + ∑ q_i log(M / q_i)) | Matches optimal static Huffman/Knuth BST (Shannon entropy!) |
| Working-Set Theorem | O(N log N + ∑ log(t_k + 1)) | Accessing the $t$-th most recently used item takes $O(\log t)$! |
| Sequential Access (Tarjan 1985) | O(N) Total (O(1) per item!) | Splaying keys $1, 2, \dots, N$ in sorted order takes linear time |
Sleator–Tarjan Access Lemma Proof: Why Zig-Zig Releases Potential
Define the subtree size $s(u) = |\text{subtree}(u)|$, the node rank $r(u) = \lfloor \log_2 s(u) \rfloor$, and the tree potential $\Phi(T) = \sum_{u \in T} r(u)$. We prove that the amortized cost of a Zig-Zig or Zig-Zag step lifting $x$ above $p$ and $g$ is bounded by:
$$\hat{c}_{\text{step}} = 2 + r'(x) + r'(p) + r'(g) - r(x) - r(p) - r(g) \le 3(r'(x) - r(x))$$
where $r$ and $r'$ denote ranks before and after the double rotation. Observe that after the step, $x$ roots the exact subtree previously rooted at $g$, so $r'(x) = r(g)$, and clearly $r(p) \ge r(x)$ and $r'(p) \le r'(x)$. Thus the left side simplifies to $2 + r'(p) + r'(g) - r(x) - r(p) \le 2 + r'(x) + r'(g) - 2r(x)$. Now comes the magic of Zig-Zig: before the step, $x$'s subtree and $g$'s post-rotation subtree are completely disjoint inside $g$'s original subtree! Therefore:
$$s(x) + s'(g) \le s(g) = s'(x)$$
By the concavity of $\log_2$: for any positive $a + b \le c$, $\log_2 a + \log_2 b \le 2 \log_2(c/2) = 2 \log_2 c - 2$. Applying this with $a = s(x), b = s'(g), c = s'(x)$ gives $r(x) + r'(g) \le 2r'(x) - 2$, so the $+2$ actual rotation cost cancels the $-2$ from concavity:
$$\hat{c}_{\text{step}} \le 2 + r'(x) + (2r'(x) - 2 - r(x)) - 2r(x) = 3(r'(x) - r(x))!$$
Telescoping $\sum 3(r'(x) - r(x))$ across all steps from $x$'s initial rank $r_0(x)$ up to the root rank $r(\text{root}) = \log_2 N$ (plus $+1$ for the final Zig) proves the Access Lemma: $\text{Amortized Cost}(\text{splay}(x)) \le 3(\log_2 N - \log_2 s(x)) + 1 = O(\log N)$!
Inspect how a Treap simultaneously satisfies BST order on keys and Max-Heap order on random priorities via two primitives — split(T, k) and merge(L, R) — and how Splay Tree zig-zig rotations halve path depth.
Invariant & State
Hardware Reality: Splay Trees as Self-Organizing L1 Cache & Link-Cut Tree Auxiliary Paths
Because Splay Trees satisfy the Working-Set Theorem (re-accessing one of the $k$ most recently touched keys takes $O(\log k)$ comparisons), they act like a hardware LRU cache embedded inside a search tree, making them popular in network packet classifiers and GCC's libiberty (splay-tree.c). Even more importantly, because splay(x) requires zero balance fields and splits/joins paths at the root, Sleator and Tarjan built Link-Cut Trees (supporting $O(\log N)$ dynamic forest connectivity and path aggregates) using Splay Trees as the auxiliary heavy-path representation!
Implementation: Sleator-Tarjan Bottom-Up Splay Engine
// C++20: Sleator-Tarjan Bottom-Up Splay Tree (Zero Balance Metadata, O(log N) Amortized)
struct SplayNode {
int key;
SplayNode *ch[2] = {nullptr, nullptr}, *p = nullptr;
explicit SplayNode(int k) : key(k) {}
};
// Returns 0 if x is a left child, 1 if x is a right child
inline int dir(const SplayNode* x) noexcept {
return x->p->ch[1] == x;
}
// Rotates x one step up above its parent p
void rotate(SplayNode* x) noexcept {
SplayNode* p = x->p;
SplayNode* g = p->p;
int d = dir(x);
p->ch[d] = x->ch[d ^ 1];
if (x->ch[d ^ 1]) x->ch[d ^ 1]->p = p;
x->ch[d ^ 1] = p;
p->p = x;
x->p = g;
if (g) g->ch[g->ch[1] == p] = x;
}
// Splays x to the root using Zig, Zig-Zig (rotate p first!), and Zig-Zag
SplayNode* splay(SplayNode* x) noexcept {
if (!x) return nullptr;
while (x->p != nullptr) {
SplayNode* p = x->p;
SplayNode* g = p->p;
if (g == nullptr) {
rotate(x); // Zig (p is root)
} else if (dir(p) == dir(x)) {
rotate(p); // Zig-Zig: rotate p with g FIRST!
rotate(x);
} else {
rotate(x); // Zig-Zag: rotate x twice
rotate(x);
}
}
return x;
}Failure Modes & Adversarial Pitfalls
- Searching for a Non-Existent Key Without Splaying the Last Visited Node: If
find(key)hits anullpointer after walking down a long $O(N)$ chain and returnsfalsewithout splaying the last non-null node visited before falling off the tree, an attacker can repeatedly query a missing key in $\Theta(N)$ time forever without paying down the tree's potential! Always splay the last visited node even on an unsuccessful search. - Multi-Threaded Read Contention: Because even a read-only
find(key)mutates the tree viasplay(x)all the way to the root, concurrent readers cannot share a Splay Tree without an exclusive mutex lock.