Splay Tree Amortized Analysis

What "amortized O(log n)" actually means

Amortized cost is the per-operation average over a sequence. Real cost is what one operation actually pays — sometimes 1, sometimes n. The amortized framework rewrites this as: amortized(op) = real(op) + Phi_after − Phi_before, where Phi is a chosen potential function. Sum over a sequence and the deltas telescope: sum amortized = sum real + Phi_final − Phi_initial. If we can bound the per-op amortized cost by O(log n) and the total potential by O(n log n), we get a sequence bound of O((m + n) log n).

For a splay tree of n nodes, the maximum potential is sum over all x of log2(s(x)) ≤ n * log2(n). So even if Phi_initial is zero and Phi_final is n log n, that adds only an n log n term to the total — absorbed into the bound. Critically, the bound holds without any assumption on the access distribution or starting tree shape.

Choosing the potential: rank and Phi

Sleator and Tarjan's choice is so spare it feels obvious in hindsight. For each node x in the tree, let s(x) be the number of nodes in x's subtree (including x itself). Let r(x) = floor(log2(s(x))) — the rank of x. The potential is

Phi = sum over all nodes x of r(x).

For a tree of n nodes, the root has rank floor(log2(n)). Leaves have rank 0. A balanced tree has Phi = O(n) (most nodes are near the leaves). A linear chain has Phi = sum_{k=1..n} floor(log2(k)) = O(n log n). The worst Phi is also O(n log n), and any Phi gap between two snapshots of the same key set is bounded by n log n. That n log n slack is the "n log n" in the O((m+n) log n) bound.

The access lemma — what to prove

The access lemma says: splaying node x in a tree T has amortized cost at most 3 * (r(T) − r(x)) + 1. This is the lemma that makes everything else fall into place. Once we have it, any single splay costs amortized at most 3 * log2(n) + 1 = O(log n), and since every other operation (insert, delete, join, split) reduces to a constant number of splays, all of them are O(log n) amortized too.

The proof analyzes one splay step at a time. Each step is one of three patterns:

• Zig (terminal). When parent(x) is the root, single rotation. Amortized cost ≤ 3 * (r'(x) − r(x)) + 1. The +1 absorbs the actual rotation cost; the 3 * delta_r telescopes.
• Zig-zig (same-side). Two same-direction rotations. Amortized cost ≤ 3 * (r'(x) − r(x)). The case analysis uses the inequality log2(a) + log2(b) ≤ 2 * log2((a+b)/2) − 2 for the rank changes, exploiting concavity of log.
• Zig-zag (opposite-side). Two opposite-direction rotations. Amortized cost ≤ 3 * (r'(x) − r(x)). Same concavity trick on different subtree sizes.

Summing over a splay path of length k:

total_amortized ≤ sum_{i=1..k} 3 * (r_{i+1}(x) − r_i(x)) + 1
                 = 3 * (r_final(x) − r_initial(x)) + 1
                 = 3 * (r(T) − r(x)) + 1
                 ≤ 3 * log2(n) + 1
                 = O(log n).

Telescoping kills every intermediate term. The bound is tight; you can't get better than 3 * (r(T) − r(x)) with this potential.

Worked zig-zig with numbers

Let x sit in a chain of 8 nodes, deep on the left. Before splay: s(x) = 1, s(p) = 2, s(g) = 3. So r(x) = 0, r(p) = 1, r(g) = 1 (floor(log2(3)) = 1). Phi contribution of these three nodes: 0 + 1 + 1 = 2. The rest of the tree contributes a fixed amount we don't touch.

After one zig-zig: x is at the top of these three, p is x's right child, g is p's right child. New sizes: s(x) = 3, s(p) = 2, s(g) = 1. New ranks: r(x) = 1, r(p) = 1, r(g) = 0. Phi contribution: 1 + 1 + 0 = 2. The total Phi is unchanged for these three nodes — but the access path now has x at the top instead of at the bottom. The amortized accounting paid 3 * (r'(x) − r(x)) = 3 * 1 = 3 units, which absorbed the 2 rotations of actual cost (2 units) plus stored 1 unit as future credit.

In a longer chain, the savings compound. A chain of 16 with x at depth 4: before, x has rank 0 and root has rank 4; after splaying x to the root, x has rank 4 and former root has dropped. Telescoping bounds the entire splay at 3 * 4 + 1 = 13 amortized units — vs. 4 actual rotations. The extra 9 units pre-pay for future splays whose costs may exceed their rank gain.

Why zig-zig needs grandparent-first

The proof of the zig-zig step uses the following geometric fact. Before the rotation, x has subtree-size a; sibling-of-x (call it d) has size b; subtree at grandparent g (excluding x's, p's subtrees) has size c. Total subtree-size at g before is roughly a + b + c. After zig-zig, x has the whole thing — size a + b + c. So r'(x) = log2(a + b + c).

If we rotate p first instead, the intermediate shape doesn't yield the inequality. Specifically, the standard zig-zig analysis bounds the cost by 3 * (r'(x) − r(x)) by using log(a) + log(c) ≤ 2 * log((a+c)/2) = 2 * (log(a+c) − 1) — concavity of log applied to a and c. The reversed rotation produces a different pairing, and the bound becomes 3 * (r'(x) − r(x)) + 2 instead of 3 * (r'(x) − r(x)) — the constant +2 per step would not telescope, breaking the O(log n) result.

Theorems that follow from the access lemma

• Balance theorem. Total cost of m operations on an n-node splay tree is O((m + n) log n). Direct consequence of access lemma + amortized analysis bookkeeping.
• Static optimality. For frequencies f_i, total cost is O(m + sum_i f_i log(m / f_i)). Use generalized rank with weights w_i = f_i / m; apply access lemma.
• Static finger. Cost of accessing x_t with fixed finger f is O(log(|rank(x_t) − rank(f)| + 2)). Weights decay with rank-distance from f.
• Working set. Cost of accessing x_t is O(log(w(x_t) + 2)), where w is the number of distinct keys accessed since x_t's last access. Weights = 1 / (access-recency)^2.
• Sequential access. n consecutive successor accesses cost O(n) total. Each access has rank-gain that absorbs the next access's cost. Proven by Tarjan 1985 via a different potential.
• Dynamic finger. Cost of accessing x_t after x_{t-1} is O(log(|rank(x_t) − rank(x_{t-1})| + 2)). Proven by Cole 2000 — a much harder argument than the static-finger version.
• Dynamic optimality (conjectured). Cost is within O(1) of the optimal offline BST. Open since 1985; best known is O(log log n) via Tango trees.

Amortized vs worst-case — practical impact

	Splay tree	Red-black tree	AVL tree
Lookup amortized	O(log n)	O(log n)	O(log n)
Lookup worst-case	O(n)	O(log n)	O(log n)
Insert amortized	O(log n)	O(log n)	O(log n)
Insert worst-case	O(n)	O(log n)	O(log n)
Working-set bound	Yes, O(log w(x))	No	No
Static optimality	Yes	No	No
Per-node metadata	None	1 color bit	balance factor (2 bits)
Concurrent reads	Lock required (reads mutate)	Read-only safe	Read-only safe

For real-time systems, the O(n) worst-case kills splay. A single splay on a pathological chain is linear; no amortization helps a single deadline. But for caches, kernel data structures with skewed access (Linux mm splay history), and adaptive query planners, the static-optimality and working-set bounds dominate the practical performance.

Common misconceptions

• "Amortized means probabilistic." No — amortized is a deterministic worst-case bound on a sequence's total cost. There's no randomness; splay's bound holds for any sequence of any length on any tree shape.
• "Phi must always increase." No — Phi can decrease across an operation. Decreases mean we're "spending" previously stored credit; increases mean we're "saving" for future work. The bound concerns the difference, not the trajectory.
• "The access lemma is tight." The constant 3 can be tightened to 3 with care, but not less. The 3 comes from the concavity inequality log(a) + log(c) ≤ 2 log((a+c)/2) which itself is tight when a = c. Sharper potentials exist for restricted cases.
• "Splay trees outperform red-black on uniform random access." No — on uniform random access, both are O(log n) amortized but splay rotates aggressively (mutating on reads), losing on cache and concurrency. Use splay where access is skewed.
• "Reset Phi between operations." No — Phi is a function of the current tree, not a per-op accumulator. It carries across the entire sequence; you only compute Phi_initial and Phi_final.

A 3-step proof outline you can reproduce

1. Define Phi = sum r(x). Note Phi ≥ 0 always; Phi ≤ n log n for any n-node tree.
2. Prove the per-step bounds. Each zig, zig-zig, zig-zag step has amortized cost ≤ 3 * delta_r(x) [+ 1 only on zig]. Three case analyses using the concavity of log.
3. Telescope. Sum over the splay path. Intermediate r terms cancel. Final bound: 3 * (r(T) − r(x)) + 1 ≤ 3 log2 n + 1.

Total length: 4 pages in the original 1985 paper. The Erickson textbook proof is 6 pages with worked diagrams. The intuition lives entirely in the access lemma; once you have it, every splay theorem is a corollary.