the amortized analysis of splay operations
/ splay rhymes with play /
A splay tree is a binary search tree with no stored balance information at all — no colors, no height fields. Its one idea is that every time you touch a node (search, insert, delete), you 'splay' it: rotate it step by step until it becomes the root. This moves recently used items near the top, so they are fast to reach again. Individual operations are not balanced and a single splay can be slow, yet over any sequence the tree behaves as well as a balanced tree. Amortized analysis is the only way to see why.
Splaying rotates the accessed node x up to the root in double-steps called zig-zig and zig-zag (plus a single zig at the top), and along the way it roughly halves the depth of every node on the access path — the same self-flattening spirit as union-find path compression. The analysis uses the potential method with a clever choice: give each node a weight, define the 'size' s(x) as the total weight in x's subtree, the 'rank' r(x) = log2(s(x)), and let the potential Phi be the sum of r(x) over all nodes. The heart of the proof is the Access Lemma: the amortized cost of splaying x is at most 3*(r(root) - r(x)) + 1. Because rank is a logarithm of subtree size, this telescopes beautifully — the expensive deep splays are exactly the ones that drop the potential a lot, paying for themselves. Summing over a sequence yields O(log n) amortized per operation.
This analysis is the showcase application of the potential method, and it delivers more than a plain balanced tree: splay trees achieve several stronger amortized properties for free, like the static optimality theorem (within a constant factor of the best fixed BST for any access sequence) and fast access to recently used keys. The honest caveats: every bound here is amortized, so one specific splay can cost Theta(n) when it climbs a long path; the choice of potential (sum of logs of subtree sizes) is the hard creative step that no recipe gives you; and although splay trees match balanced trees in the O() sense, their constant factors and extra rotations sometimes make them slower in practice than a red-black tree.
Access a deep node x in a long right-leaning chain. The splay does a cascade of zig-zig steps, lifting x to the root and halving the depth of every node it passed. That one access is expensive, but the tree it leaves is much shallower, so the next accesses are cheap — the potential Phi (sum of log subtree sizes) dropped sharply, paying for the costly splay.
The potential = sum over nodes of log(subtree size); deep expensive splays drop it sharply, so each operation amortizes to O(log n).
Splay-tree O(log n) is amortized, not worst-case per operation: a single splay can still be Theta(n). The potential (sum of logs of subtree sizes) is the inspired choice that makes the proof work — no general recipe produces it.