Proofs: Splay tree

Splay tree operations take O(log n) amortized time full

This proof shows: amortized-time.

Setting. Give each node weight 1. For a node $x$ let $s(x)$ be the number of nodes in its subtree and $r(x) = \lg s(x)$. The potential of a tree is $\Phi = \sum_x r(x)$, and of a collection of trees the sum over the trees. Each rank is between 0 and $\lg N$, where $N$ is the largest number of keys at any time. We count the cost of an operation as the number of nodes visited by its searches plus the number of rotations, plus $O(1)$; a search that visits $d + 1$ nodes is followed by a splay of a node at depth $d$, which makes $d$ rotations, so the search costs at most one more than the splay, and it is enough to count rotations plus $O(1)$.

Access Lemma (Sleator and Tarjan, Lemma 1; proved in the complexity proof of splaying). The amortized number of rotations of a splay of $x$ in a tree with root $t$ is at most $3(r(t) - r(x)) + 1 \le 3 \lg N + 1$.

Access. One splay: at most $3 \lg N + 1$ amortized, plus $O(1)$.

Join. The splay of $m$ in $L$ costs at most $3 \lg N + 1$ amortized. Then $R$ is hung below $m$. This changes only the rank of $m$, which becomes $\lg(|L| + |R|) \le \lg N$, so the potential grows by at most $\lg N$. The total is $4 \lg N + O(1)$.

Split. One access, then one link is cut at the root. Cutting a subtree from the root only lowers the rank of the root, and no other rank changes, so the potential does not grow. The total is $3 \lg N + O(1)$.

Insert. One access, at most $3 \lg N + 1$. Then the new node $z$ becomes the root with the old root $r$ below it. The rank of $r$ does not grow (it loses a subtree), no other old rank changes, and $z$ adds $r(z) = \lg(n + 1) \le \lg N$. The total is $4 \lg N + O(1)$.

Delete. One access, at most $3 \lg N + 1$. Removing the root removes its rank, which only lowers $\Phi$. Then a join, at most $4 \lg N + O(1)$. The total is $7 \lg N + O(1)$.

Sequences. For a sequence of $m$ operations that starts from a tree with $n_0$ keys, the actual cost is the sum of the amortized costs plus $\Phi_0 - \Phi_{\text{end}}$. Since $\Phi \ge 0$ and $\Phi_0 \le n_0 \lg n_0$, the total actual cost is at most $m(7 \lg N + O(1)) + n_0 \lg n_0 = O((m + n_0) \log N)$. So each operation costs $O(\log N)$ amortized. $\blacksquare$

Remark. The constant 7 for delete is not tight; it comes from adding the bounds of the parts. Other weight choices in the Access Lemma give the static optimality, static finger and working set theorems.

Splay tree operations keep the binary search tree and return the right answers full

This proof shows: correctness, termination.

We use the result of splaying: SPLAY$(T, x)$ ends, keeps the strict BST property, the in-order sequence and the parent links, and makes $x$ the root. Write $D$ for the set of keys of $T$.

Lemma 1 (access). After ACCESS$(T, k)$ with $D \ne \emptyset$, the root is the node of $k$ if $k \in D$; otherwise the root key is $\mathrm{floor}(k) = \max\{d \in D : d < k\}$ or $\mathrm{ceiling}(k) = \min\{d \in D : d > k\}$. ACCESS returns the node of $k$ or NIL, correctly.

Proof. The loop of line L2 is the BST search; if $k \in D$ it stops at the node of $k$ and line L4 splays it. If $k \notin D$, the search ends at NIL below the last node $\ell$ of the path. If the search left $\ell$ to the left, then $k < \ell.key$ and the left subtree of $\ell$ is empty. Suppose some key $d \in D$ lies strictly between $k$ and $\ell.key$. For each node $v \ne \ell$ on the path, $k$ and $\ell.key$ are on the same side of $v.key$, because $\ell$ is in the subtree that the search for $k$ entered at $v$. So $v.key$ is not in the closed range from $k$ to $\ell.key$, and $d$ is on the same side of $v.key$ as $k$. Hence $d$ is in the subtree that the search entered at each $v$, so it is in the subtree of $\ell$, and as $d < \ell.key$ it is in the empty left subtree of $\ell$, a contradiction. So $\ell.key = \mathrm{ceiling}(k)$. The case to the right gives the floor. Splaying $\ell$ makes it the root. Line L5 tests the root key against $k$. $\square$

Insert. If $k \in D$, line L7 returns and the set does not change. Otherwise, by Lemma 1, the root $r$ is the floor or the ceiling of $k$. If $k < r.key$, then $r$ is the ceiling, so every key in the left subtree of $r$ is less than $r.key$ and not in $(k, r.key)$, hence less than $k$; the keys of $r$ and its right subtree are greater than $k$. So the tree with root $z$, left subtree the old left subtree of $r$, and right subtree $r$ (without its left subtree) has the BST property at $z$, and at $r$ (which lost only a subtree). The case $k > r.key$ is the mirror image. Line L11 sets the parent links. The new key set is $D \cup \{k\}$.

Join. Let all keys of $L$ be less than all keys of $R$. If $L = $ NIL the answer is $R$. Otherwise the maximum $m$ of $L$, after the splay, is the root of $L$; it has no right child, since a right child would have a larger key. Hanging $R$ as its right subtree keeps the BST property at $m$, as all keys of $R$ exceed $m.key$, and at every other node the subtrees are unchanged.

Delete. If ACCESS returns NIL, $k \notin D$ and nothing changes in the set. Otherwise the root holds $k$, its left subtree $L$ holds exactly the keys less than $k$ and its right subtree $R$ the keys greater than $k$. So JOIN$(L, R)$ is legal and gives a BST on $D \setminus \{k\}$.

Split. After ACCESS, the root $r$ is the node of $k$, or its floor or ceiling, by Lemma 1. If $r.key \le k$, then $r$ is $k$ or its floor, so each key of the right subtree of $r$ is greater than $k$ (a key in $(r.key, k]$ would contradict the choice of $r$), and each key of $r$ and its left subtree is at most $r.key \le k$. So line L19 splits $D$ into the keys $\le k$ and $> k$. If $r.key > k$, then $r$ is the ceiling, so every key in the left subtree of $r$ is less than $k$, and line L20 splits correctly.

Termination. Each search walks down a finite tree, each splay ends, and the walk to the maximum in line L16 walks down a finite tree. $\blacksquare$