Proofs: Binary search tree

The operations of a binary search tree keep the invariant and return the right answers full

This proof shows: correctness.

We write $S(T)$ for the set of keys of $T$, and $\mathrm{sub}(x)$ for the set of nodes in the subtree rooted at $x$. The invariant is (B1) order, (B2) links and (B3) count, as on the page. We use one consequence of (B1) many times.

Lemma 1 (intervals). Assume (B1). For each node $x$, let $a(x)$ be the largest key of an ancestor $u$ of $x$ such that $x$ is in the right subtree of $u$ (or $-\infty$ if there is none), and let $b(x)$ be the smallest key of an ancestor $u$ such that $x$ is in the left subtree of $u$ (or $+\infty$). Then each key in $\mathrm{sub}(x)$ lies in the open interval $(a(x), b(x))$, and each key of $T$ in this interval is in $\mathrm{sub}(x)$.

Proof. The first part follows from (B1) at each ancestor $u$. For the second part, let $y$ be a node with $a(x) < y.key < b(x)$, and let $u$ be the lowest common ancestor of $x$ and $y$. If $u \ne x$, then $x$ and $y$ are in different subtrees of $u$, or $y = u$. If $x$ is in the left subtree of $u$, then $b(x) \le u.key$, and $y.key \ge u.key$ by (B1) or by $y = u$, so $y.key \ge b(x)$, which is false. The case where $x$ is in the right subtree is the mirror image. So $u = x$, and $y \in \mathrm{sub}(x)$. $\square$

Search. Claim: TREE-SEARCH$(T, k)$ returns the node with key $k$ if $k \in S(T)$, and NIL else. We use the invariant of the loop of line L2: if $k \in S(T)$, then the node with key $k$ is in $\mathrm{sub}(x)$ (with $\mathrm{sub}(\mathrm{NIL}) = \emptyset$). Line L1 sets $x$ to the root, so it holds at the start. In a step, $k \ne x.key$. If $k < x.key$, then by (B1) no node of the right subtree and not $x$ itself has key $k$, so the node with key $k$, if it exists, is in the left subtree, and line L3 moves there. The case $k > x.key$ is the mirror image. Each step increases the depth of $x$ by 1, and the depth is at most $h$, so the loop stops after at most $h + 1$ steps. If it stops with $x \ne$ NIL, then $x.key = k$. If it stops with $x = $ NIL, then $\mathrm{sub}(x)$ is empty, so by the invariant $k \notin S(T)$. The tree is not changed.

Minimum. Claim: TREE-MINIMUM$(x)$ returns the node of $\mathrm{sub}(x)$ with the smallest key. Let $x_0 = x, x_1, \ldots, x_m$ be the path that lines L5 and L6 follow, where $x_m.left = $ NIL. For $i < m$, each key of $\mathrm{sub}(x_i)$ that is not in $\mathrm{sub}(x_{i+1})$ is $x_i.key$ or in the right subtree of $x_i$, so it is larger than each key of $\mathrm{sub}(x_{i+1})$ by (B1). So the minimum of $\mathrm{sub}(x_i)$ is the minimum of $\mathrm{sub}(x_{i+1})$. The node $x_m$ has no left subtree, so by (B1) its key is the minimum of $\mathrm{sub}(x_m)$. By induction from $i = m$ down to $i = 0$, $x_m$ is the minimum of $\mathrm{sub}(x)$.

Successor. Claim: TREE-SUCCESSOR$(x)$ returns the node with the smallest key larger than $x.key$, or NIL if $x.key$ is the maximum. Case 1: $x.right \ne$ NIL. By Lemma 1 applied to $r = x.right$, the keys of $T$ in $(x.key, b(x))$ are the keys of $\mathrm{sub}(r)$, because $a(r) = x.key$ and $b(r) = b(x)$. This set is not empty, so the successor is its minimum, which line L7 returns by the claim on minimum. Case 2: $x.right = $ NIL. Then by Lemma 1 no key of $T$ lies in $(x.key, b(x))$, so the successor is the node with key $b(x)$ if $b(x) < +\infty$, and NIL else. The node with key $b(x)$ is the lowest ancestor $u$ of $x$ such that $x$ is in the left subtree of $u$: a lower such ancestor has a smaller key, because it is in the left subtree of each higher one. Lines L8 to L10 go up from $x$ while the current node is a right child, so they stop at the first ancestor $y$ entered from its left child, which is $u$, or at NIL if there is none. By (B2) the parent pointers are right, so the walk follows the real path. The loop stops because the depth of $x$ drops by 1 in each step.

Insert. Claim: after TREE-INSERT$(T, k, v)$, the tree holds the map with $k$ set to $v$, and (B1) to (B3) hold. If $k \in S(T)$, the loop of lines L12 to L15 is the search for $k$, which reaches the node with key $k$ by the search claim, and line L15 changes only its value. Now let $k \notin S(T)$. The loop follows the search path for $k$ and stops when $x = $ NIL, with $y$ the last node of the path. Let $c$ be the empty child position of $y$ where the loop stopped (left if $k < y.key$, right else). For each node $u$ on the path above this position, the path went left at $u$ exactly when $k < u.key$. So the new node $z$, placed at $c$ by lines L16 to L19, is in the left subtree of $u$ exactly when $k < u.key$, and (B1) holds at each ancestor of $z$. Nodes that are not ancestors of $z$ keep their subtrees, so (B1) holds there too, and $z$ has no subtrees. Line L16 sets $z.p = y$, and the link from $y$ (or from $T.root$ when $y = $ NIL, which happens only for the empty tree) points to $z$, so (B2) holds. The implementation adds 1 to $n$ in this case only, so (B3) holds.

Transplant. Claim: TRANSPLANT$(T, u, v)$ makes the parent of $u$ (or the root field) point to $v$, and sets $v.p = u.p$. This is lines L20 to L23 read directly; it changes no other link.

Delete. Claim: after TREE-DELETE$(T, z)$, $S(T)$ loses exactly $z.key$, each other node keeps its key and value, and (B1) to (B3) hold. Let $P = a(z)$ and $Q = b(z)$. By Lemma 1, each key of $\mathrm{sub}(z)$ lies in $(P, Q)$. The new subtree that takes the place of $z$ has the keys of $\mathrm{sub}(z)$ without $z.key$, so (B1) at the ancestors of $z$ stays true, and we only need (B1) inside the new subtree.

• Case A: $z.left = $ NIL (line L24). The new subtree is the right subtree of $z$, which is a BST.
• Case B: $z.right = $ NIL (line L25). The new subtree is the left subtree of $z$, which is a BST.
• Case C: two children (lines L26 to L28). Let $L$ and $R$ be the left and right subtrees of $z$, and let $y = $ TREE-MINIMUM$(z.right)$, the node of $R$ with the smallest key, so $y.left = $ NIL. Case C1: $y = z.right$. Line L28 puts $y$ in the place of $z$, with $L$ as its left subtree; its right subtree stays $R \setminus \{y\}$. Each key of $L$ is less than $z.key < y.key$, and each key of $R \setminus \{y\}$ is greater than $y.key$ because $y$ is the minimum of $R$. Case C2: $y \ne z.right$. Then $y$ is a left child inside $R$. Line L27 replaces $y$ by its right subtree, which is (B1)-correct inside $R$ by the argument of case A applied to $y$ in the tree $R$, so $R' = R \setminus \{y\}$ is a BST. Then $y$ gets $R'$ as its right subtree, and line L28 puts $y$ in the place of $z$ with $L$ as its left subtree. Each key of $L$ is less than $z.key < y.key$, and each key of $R'$ is greater than $y.key$. In both cases the new subtree is a BST with the keys of $\mathrm{sub}(z)$ except $z.key$.

For (B2): each link that the procedure changes is set in both directions. TRANSPLANT sets the child link and $v.p$, and lines L27 and L28 set $y.right.p$ and $y.left.p$ after they set $y.right$ and $y.left$. The node $z$ is no longer reachable from the root, because its only parent link (or the root field) now points to its replacement. The implementation subtracts 1 from $n$, so (B3) holds.

Termination of the loops. Each loop of the main block moves $x$ one level down (lines L2, L5 and L12) or one level up (line L9), so it runs at most $h + 1$ times.

Theorem. Starting from the empty tree, after any sequence of inserts and deletes, the tree satisfies (B1) to (B3) and stores exactly the map that the sequence defines, and each search, minimum and successor query returns the answer of the ordered set.

Proof. By induction on the number of operations. The empty tree satisfies (B1) to (B3) and stores the empty map. By the insert and delete claims, each update keeps the invariant and changes the map as the dictionary laws require. Queries do not change the tree, and by the search, minimum and successor claims they return the right node. $\blacksquare$