Proofs: Splaying

The Access Lemma, an amortized bound of 3(r(t) - r(x)) + 1 for splaying full

This proof shows: amortized-time.

Give each node $i$ a weight $w(i) > 0$, which does not change during the splay. For a node $x$, let $s(x)$ be the total weight of the subtree rooted at $x$, and $r(x) = \lg s(x)$. The potential of the tree is $\Phi = \sum_x r(x)$. The cost of a splay is the number of rotations, or 1 if there are none. For a step, write $r$ and $s$ for the values before and $r'$ and $s'$ for the values after.

Fact. For $a, b > 0$, $\lg a + \lg b \le 2 \lg(a + b) - 2$.

Proof. $ab \le ((a + b)/2)^2$ by the inequality of the arithmetic and geometric means, and taking $\lg$ gives $\lg a + \lg b \le 2 \lg(a + b) - 2$. $\square$

In each step, only $x$, its parent $y$ and (for a double step) its grandparent $z$ change their subtrees, so only their ranks change. After the step $x$ roots the subtree that $y$ (zig) or $z$ (double step) rooted, so $r'(x) = r(y)$ or $r'(x) = r(z)$. Also $r(x) \le r(y) \le r(z)$ before the step, since each subtree contains the one below it, and $r'(x) \ge r'(v)$ for each $v$ below $x$ after it.

Zig. The cost is 1, and $\Delta \Phi = r'(x) + r'(y) - r(x) - r(y) = r'(y) - r(x) \le r'(x) - r(x)$, since $r'(x) = r(y)$ and $r'(y) \le r'(x)$. So the amortized cost is at most $1 + (r'(x) - r(x)) \le 1 + 3(r'(x) - r(x))$.

Zig-zig. The cost is 2. With $r'(x) = r(z)$,

using $r'(y) \le r'(x)$ and $r(y) \ge r(x)$. Before the step, the subtree of $x$ holds $x$ and its two subtrees $A, B$; after it, $z$ holds $z$, the old sibling subtree of $y$ and the old other subtree of $z$. These two node sets are disjoint and lie inside the new subtree of $x$, so $s(x) + s'(z) \le s'(x)$. By the fact, $r(x) + r'(z) \le 2 r'(x) - 2$, that is $r'(z) \le 2 r'(x) - r(x) - 2$. So

Zig-zag. The cost is 2. With $r'(x) = r(z)$,

using $r(y) \ge r(x)$. After the step $y$ and $z$ are the two children of $x$, so $s'(y) + s'(z) \le s'(x)$ and, by the fact, $r'(y) + r'(z) \le 2 r'(x) - 2$. So

since $r'(x) \ge r(x)$.

The whole splay. Let the steps be $1, \ldots, m$, with $r_0(x) = r(x)$ before the first and $r_m(x) = r(t)$ after the last, where $t$ is the root before the splay ($x$ ends with the subtree of the whole tree, whose weight is $s(t)$). Only the last step can be a zig. Adding the bounds of the steps, the sum telescopes:

If $x$ is already the root, the cost is 1 and $\Delta\Phi = 0$, which also meets the bound. $\blacksquare$

Consequences. With $w(i) = 1$ for all $n$ nodes, $r(t) = \lg n$ and $r(x) \ge 0$, so the amortized cost is at most $3 \lg n + 1$. For a sequence of $m$ splays, the actual cost is the amortized cost plus $\Phi_0 - \Phi_m$; with unit weights each rank lies between 0 and $\lg n$, so $\Phi_0 - \Phi_m \le n \lg n$, and the total is at most $m(3 \lg n + 1) + n \lg n$. In general $\lg w(i) \le r(i) \le \lg W$ with $W = \sum_i w(i)$, so the net drop of potential is at most $\sum_i \lg(W/w(i))$.

Splaying keeps the binary search tree and ends with x at the root full

This proof shows: correctness, termination.

Let $T$ be a binary search tree with parent pointers in which, for each node $v$, $v.left.p = v$ and $v.right.p = v$ when the children exist, and the root has no parent. Call this the link invariant.

Lemma 1 (rotation). If $x$ has a parent $y$, ROTATE$(x)$ keeps the link invariant and the in-order sequence, makes $y$ a child of $x$, and gives $x$ the old parent $z$ of $y$ (or no parent). The depth of $x$ drops by 1, and the subtree that $x$ now roots holds exactly the nodes of the old subtree of $y$.

Proof. Take $x = y.left$ (line L8); the other case is the mirror image. Let $\alpha, \beta$ be the subtrees of $x$ and $\gamma$ the right subtree of $y$, so the in-order sequence of the subtree of $y$ is $\alpha, x, \beta, y, \gamma$. After line L8, $y$ has children $\beta$ and $\gamma$, and $x$ has children $\alpha$ and $y$, so the sequence of the new subtree of $x$ is $\alpha, x, \beta, y, \gamma$, the same. The parent of the root of $\beta$ is set to $y$ in line L8, the parent of $y$ to $x$ and the parent of $x$ to $z$ in line L10, and the child pointer of $z$ that pointed to $y$ points to $x$ after line L11. All other links are unchanged. So the link invariant holds, and the in-order sequence of the whole tree is unchanged, since the subtree at that position has the same sequence. The keys of $\alpha, x, \beta, y, \gamma$ are in increasing order, so the BST property holds at $x$ and $y$; at every other node the set of keys in each subtree is unchanged. $\square$

Lemma 2 (one round). Assume $x.p \ne $ NIL at line L1. After the round, the link invariant and the in-order sequence still hold, and the depth of $x$ has dropped by 1 (line L3) or by 2 (lines L4 and L5).

Proof. Line L3 is one rotation of $x$. In line L4 the first rotation, ROTATE$(y)$, moves $y$ above $z$; by Lemma 1 the subtree of $y$ keeps $x$ as a child on the same side, so $x$ is still a child of $y$ and the second rotation is legal; it moves $x$ above $y$, and $x$ takes the old place of $z$, so its depth drops by 2. In line L5 the first rotation moves $x$ above $y$, and $x$ takes the place of $y$ as a child of $z$; the second moves $x$ above $z$. Each rotation keeps the invariant and the sequence by Lemma 1. $\square$

Theorem. SPLAY$(T, x)$ ends after $\lceil d/2 \rceil$ rounds and $d$ rotations, where $d$ is the depth of $x$, and then $T$ is a binary search tree with the same in-order sequence, the link invariant, and root $x$.

Proof. By Lemma 2 the depth of $x$ drops by 2 in each round while it is at least 2, and the last round is a zig exactly when the depth is 1. So the number of rounds is $\lceil d/2 \rceil$ and the number of rotations is $d$. The loop stops when $x.p = $ NIL, that is when $x$ is the root, and line L6 records it. The invariants hold after each round by Lemma 2. $\blacksquare$