A search tree can reorganize around the item just accessed
A binary search tree answers a search by following key comparisons. If the tree is a chain, this can take linear time. An AVL tree maintains an explicit height-balance condition to prevent that shape. A splay tree takes a different approach: after finding an item, it moves that node to the root with a prescribed sequence of rotations.
The result need not be height-balanced. A single search can still be expensive. The useful guarantee concerns a sequence of accesses, and its proof accounts for how the tree's potential changes while paying for the rotations. We will prove that guarantee rather than infer it from a few pictures of shallow trees.
Throughout, the tree has a fixed set of distinct keys, and we analyze successful searches followed by splaying the found node. Insertion, deletion and a policy for unsuccessful searches require additional definitions and analysis; they are not operations implemented by the procedure below.
A rotation changes links while preserving search order
Definition 9.1.1
(Binary-search-tree order and a rotation)
Every key in a node's left subtree is smaller than its key; every key in its right subtree is larger. A rotation promotes a child x above its parent p while preserving the inorder sequence of keys.
For a left child x, the right rotation is:
p x
/ \ / \
x C -> A p
/ \ / \
A B B C
The subtrees A, B and C may be empty. The ordering A, x, B, p, C is unchanged. A right child is promoted by the left-right mirror of this rotation.
The pointer implementation must reconnect the promoted node to the old grandparent or to the tree's root, transfer the middle subtree B, and update parent links, including B's parent when B is nonempty. Rotation does not create, remove or change keys. With parent pointers, each rotation changes only a constant number of links.
Write ROTATE_UP(x) for this primitive that promotes x over its
current parent. Whether the rotation is left or right is determined
by which child x currently is.
Splaying chooses a single or double step
Let p be x's parent and g its grandparent when they exist.
- Zig: p is the root. Promote x once.
- Zig-zig: x and p are both left children, or both right children. Promote p over g, then x over p.
- Zig-zag: x and p are on opposite sides. Promote x over p, then x over g.
SPLAY(x):
while parent(x) is not NONE:
p = parent(x)
g = parent(p)
if g is NONE:
ROTATE_UP(x)
else if (x is left child of p) == (p is left child of g):
ROTATE_UP(p)
ROTATE_UP(x)
else:
ROTATE_UP(x)
ROTATE_UP(x)
return x
Every step preserves binary-search-tree order, because every constituent rotation does. Each rotation reduces the depth of the accessed x by one, including a zig-zig step's first rotation at p. The loop therefore terminates with x at the root. If x starts at depth d, there are exactly d rotations; the search itself visits d+1 nodes.
Worked example 9.1.2
(Compare two double steps on three keys)
Start with root 30, its left child 20, and 20's left child 10. Accessing 10 is zig-zig. First promote 20 over 30, giving root 20 with children 10 and 30. Then promote 10, giving root 10 with right child 20, whose right child is 30.
Instead start with root 30, its left child 10, and 10's right child 20. Accessing 20 is zig-zag. Promote 20 over 10, then over 30. The final root is 20 with children 10 and 30.
Both accesses use two rotations and preserve sorted inorder order 10,20,30. The first result is still a chain. Splaying's claim is not that every resulting tree is balanced.
Counterexample mode
Repeatedly promoting x is not the zig-zig rule
In the first three-key example, promoting 10 over 20 first and then over 30 gives root 10 with right child 30, whose left child is 20. That differs from the prescribed zig-zig result.
Both methods preserve search order and move the requested key to the root. Those facts alone do not make them the same algorithm. The access-lemma proof below uses the specified double steps; it is not a performance proof for arbitrary sequences of order-preserving rotations.
Use subtree sizes to define a potential
Definition 9.1.3
(Rank, potential and amortized rotation cost)
For each node v, let be the number of nodes in its subtree, including v. Define its rank and the tree potential by
The logarithm has base 2 throughout. For a local step, write before the step and after it. If the step performs c rotations, its amortized rotation cost is . This is a bookkeeping quantity, not the measured time of that individual step.
Since , we have . These sizes can be mathematical quantities used only in the proof: the basic splaying procedure does not need to store or recompute every subtree size after each rotation.
Only promoted nodes and their former ancestors in the local rotation change subtree sizes: x,p in a zig, or x,p,g in a double step. Other subtrees retain their sizes, and ancestors above the local subtree see the same set of descendants. In a double step, x becomes root of g's old subtree, so . In every step .
The size inequality that pays for two rotations
Lemma 9.1.4
(Two disjoint nonempty subtrees give a rank inequality)
If disjoint nonempty subtrees of sizes a,b both lie inside a subtree of size S, then
Proof
(From the product of the two sizes)
Disjointness gives . Since , we get , where the second inequality uses and positivity. Taking base-2 logarithms of these positive quantities gives .
The subtraction of 2 is important: it will pay for two actual rotations. The inequality cannot be applied to arbitrary overlapping subtrees.
Bound each local splaying step
Lemma 9.1.5
(Amortized cost of one splaying step)
Let one splaying step promote x, with ranks before and after the step. A zig (one rotation) has . A zig-zig or a zig-zag (two rotations) has .
Proof
(Zig, zig-zig and zig-zag computed separately)
Zig. Here p is the root and . Only x,p change rank, so
Thus the bound is at most . A zig can happen only once during a splay, at its end.
Zig-zig. Consider the left-left case; the right-right case is its mirror. Before the step the shape is g(p(x(A,B),C),D). After the two rotations it is x(A,p(B,g(C,D))). Thus the old subtree at x and the new subtree at g are disjoint and lie inside the new subtree at x. The size inequality gives . Using , and ,
Zig-zag. For the left-right case, the old shape is g(p(A,x(B,C)),D), and the new shape is x(p(A,B),g(C,D)). The new subtrees at p and g are disjoint inside the new x-subtree. Hence . Since ,
The last inequality uses the nonnegative rank increase of x. The right-left case is symmetric.
Proof X-ray
Zig-zig: the old x-subtree and the new g-subtree
Only one of the facts used in the zig-zig computation carries real content. The identity cancels two ranks exactly. The inequalities and hold because the new p-subtree lies inside the new x-subtree and the old p-subtree contains the old x-subtree; they only discard terms. The real input is the size inequality, applied to the old x-subtree (the nodes of A, B and x) and the new g-subtree (the nodes of C, D and g). These node sets are disjoint and both lie inside the new x-subtree, so .
The accounting closes because the from that inequality cancels the 2 that stands for two rotations, leaving exactly . Pairing the new p-subtree with the new g-subtree would fail: g lies inside p, so the two sets overlap and the inequality does not apply. In the zig-zag step the new p- and g-subtrees are disjoint, which is why the same inequality works there.
Telescope the local bounds into the access lemma
Theorem 9.1.6
(Access lemma for the fixed-size unweighted tree)
Let x be the successfully accessed node, and let C be the total number of rotations in its splay. Then
Proof
(Sum rank increases of the same accessed node)
Every double step costs at most three times x's rank increase in amortized units; the possible final zig contributes at most one more. The local potential differences telescope to the entire splay's potential difference. The rank increases also telescope, because every local step promotes the same accessed x. Finally x is the root, so its last rank is . Subtract its initial rank to get the first inequality. Its initial rank is nonnegative, giving the second. If x was already the root, the zero-rotation case satisfies the inequality directly.
For m successful accesses on this fixed key set, summing gives
The arbitrary initial tree can contribute potential; do not silently drop that term in a finite sequence bound. Because each search visits nodes and each rotation does constant pointer work, the total successful-search-and-splay cost is under the usual constant-cost key comparison and pointer model. This is an amortized sequence guarantee, without a random-input assumption.
Two accesses with the potential written out
Worked example 9.1.7
(A depth-three access: zig-zig, then zig)
Take the chain with root 40, left child 30, 30's left child 20, and 20's left child 10, and access 10. The subtree sizes at 40, 30, 20, 10 are 4, 3, 2, 1, so .
The node 10 has depth 3, so the splay uses three rotations. The first step is a zig-zig with x=10, p=20, g=30: promote 20 over 30, then 10 over 20. The result has root 40, left child 10, 10's right child 20 and 20's right child 30. Since 10 is now a left child of the root, a zig finishes: the root becomes 10 with right child 40, 40's left child 20, and 20's right child 30. The inorder sequence is still 10,20,30,40.
The final sizes at 10, 40, 20, 30 are 4, 3, 2, 1, so is again and . The amortized cost is . The access lemma allows . The result is a chain of depth 3 again: the potential did not drop, and the splay did not make the tree shallower.
Worked example 9.1.8
(Edge cases: a lone zig, the root, and one key)
Take two keys, with root 20 and left child 10, and access 10. Here . Because 10 is a child of the root, one zig suffices: the root becomes 10 with right child 20, and is again 1. So , within the step bound .
Now access 10 again. It is already the root, so no rotation occurs and the potential does not change; . The lemma, with , allows , and . With a single key the splay does nothing, and the lemma's bound is .
An individual access can still cost linear time
In a chain of n nodes, accessing the deepest key visits n nodes and uses n-1 rotations. The access lemma bounds actual rotations plus the potential change, so a large decrease in potential can pay for an expensive access. It does not place the same logarithmic bound on that access's actual rotation count.
After an access, the same key is at the root and a repeated successful access needs no rotations. This illustrates how reorganization can help, but the theorem was proved for every sequence, including sequences without repetitions. Splay trees obtain their stated guarantee through the prescribed updates and amortized accounting, rather than an AVL-style height invariant.
Whether splay trees match the best possible tree strategy on every sequence is the dynamic optimality conjecture, which is unproved.
A natural next question
Is splaying as good as any search-tree strategy?
Whether splay trees match the best possible tree strategy on every sequence is the dynamic optimality conjecture, which is unproved.
The access lemma compares splaying only with the cost of a balanced tree. A stronger question asks whether, on every access sequence, the total cost of splaying stays within a constant factor of the cost of the best binary-search-tree strategy, one allowed to rearrange the tree between accesses with the whole sequence known in advance. The dynamic optimality conjecture says yes. This unit does not prove it, and it remains a conjecture.
Common mistakes in splay accounting
Common mistake
(Applying the size inequality to nested subtrees)
The inequality needs disjoint subtrees. If one takes a subtree inside itself, so that , the left side is , which exceeds the right side by 2. In a zig-zig step the new p-subtree contains the new g-subtree, so those two cannot be paired; the old x-subtree and the new g-subtree can.
Common mistake
(Dropping the initial potential from a sequence bound)
The bound is false. For and a chain of 32 keys whose deepest key is accessed, , while . The term , which can be as large as , is what pays for the difference.
Common mistake
(Expecting a splayed tree to be balanced)
Splaying guarantees an amortized bound on a sequence of accesses, not a shape. In the depth-three example above, the tree after the access is again a chain of four nodes, and a later access to its deepest key would again cost three rotations.
Solved exercises
Quick check
(1. The order of two rotations matters)
Start with root 30, left child 20, and 20's left child 10. Splay 10. Give the root after the first rotation and the final shape. Compare with promoting 10 twice instead.
Solution · Solution 1
The prescribed zig-zig step first promotes 20, so the intermediate root is 20 with children 10,30. Promoting 10 next gives root 10, right child 20 and 20's right child 30. Promoting 10 twice instead gives root 10, right child 30 and 30's left child 20. Both inorder sequences are 10,20,30, but the shapes differ. Only the first is the specified zig-zig step.
Quick check
(2. Compute a real and an amortized cost)
Start with root 30, its left child 10, and 10's right child 20. Splay 20. Compute the potential before and after, the rotation count, and the amortized rotation cost using base-2 logarithms.
Solution · Solution 2
The initial subtree sizes at 30,10,20 are 3,2,1, so the potential is . Zig-zag produces root 20 with leaf children 10,30, whose potential is . There are two actual rotations and potential change , so the amortized rotation cost is . The actual pointer operations still occurred; the smaller bookkeeping cost reflects the drop in potential.
Quick check
(3. Keep the initial-potential term)
For 16 successful accesses to a fixed eight-key splay tree of arbitrary initial shape, use the proved coarse bounds to bound total rotations and total nodes visited by the searches. Is this a probabilistic claim?
Solution · Solution 3
and . Thus total rotations are at most . Each search visits one more node than its rotation count, so total visited nodes are at most . These are conservative deterministic sequence bounds; they do not assume random accesses or compute an expectation over input sequences.
Quick check
(4. A logarithmic amortized bound is not a per-access cap)
A 32-key tree is a chain, and a successful search accesses its deepest node. How many nodes are visited and how many rotations occur? Why does this not contradict the access lemma's upper bound of on its amortized rotation cost?
Solution · Solution 4
The search visits 32 nodes and performs 31 rotations. The lemma bounds , not 31 alone. Its conclusion allows the potential to decrease by enough to cover the difference; the full proof guarantees such a decrease for this splay. Therefore the linear actual access and the logarithmic amortized bound are consistent. A height-balance invariant would be a different guarantee, which splaying has not claimed.