Past exam of the computer science course of the University of Oxford / 2018 / Algorithms / 1

A binary search tree is a binary tree storing distinct keys from a total order, with every key in a node's left subtree smaller than that node's key and every key in its right subtree larger. The condition concerns entire subtrees, not just immediate neighbours.

For membership, start at the root of a tree and compare the target with the current key. Return true on equality; continue into the left subtree for a smaller target and the right subtree for a larger target; return false on an empty subtree. The binary search tree ordering ensures that a discarded subtree cannot contain the target. Each step descends one level, so the algorithm terminates and uses $O(h+1)$ time complexity for height of a binary tree $h$, under constant-time key comparison.

First perform splaying on the key to be deleted, making its node the root of a tree. Delete that root, leaving left and right subtrees $L,R$. If either is empty, return the other. Otherwise find the maximum key $m$ of $L$ by following right-child references, and perform splaying on $m$ within $L$. This makes $m$ the root of $L$ with an empty right subtree. Attach $R$ there. The result is the original splay tree with exactly the selected key removed. An unsuccessful lookup leaves the represented set unchanged.

For algorithm correctness, all keys of $L$ are smaller than the deleted key, and all keys of $R$ are larger. Splaying preserves the binary search tree property by the permitted assumption. Since $m$ is the maximum of $L$, it has no larger key within $L$; since every key of $R$ exceeds $m$, attaching $R$ as its right subtree preserves every ordering condition. All remaining keys occur once. This is the join-based deletion of a splay tree.^[ref]

No. In a red-black tree with no red nodes, equal black height forces every graph path from the root to an absent-child position to have the same length. A real node cannot have exactly one real child: the two paths through that node would then have different numbers of black nodes. Recursively, every real level must be full. The tree is therefore a perfect binary tree.

With $h$ real levels its size is $1+2+\cdots +2^{h-1}=2^h-1$. A size of $23$ would require $2^h=24$, which is impossible for an integer $h$. The black null sentinels are not counted among the $23$ stored entries. This is the all-black red-black tree size criterion.

Use the conventional bottom-up red-black tree insertion: insert a red node by the binary search tree rule, repair a red parent with recolouring or tree rotations, and make the root black. Write $B$ and $R$ for black and red. The first three insertions give root $34_B$, with $21_R$ on the left and $55_R$ on the right.

Inserting $40$ as the left child of $55$ gives a red parent and a red uncle. Recolour $21,55$ black and retain a black root $34$. Inserting $45$ then gives the inner configuration $55_B$–$40_R$–$45_R$. A left tree rotation at $40$, followed by a right tree rotation at $55$, produces a subtree rooted at $45_B$ with $40_R$ and $55_R$ beneath it. Finally insert $37_R$ to the left of $40_R$. Its uncle $55_R$ is red, so recolour $40,55$ black and $45$ red. No further repair is required because $45$ has black parent $34$.

The final root is $34_B$; its left child is $21_B$ and its right child is $45_R$. Under $45_R$ are $40_B$ on the left and $55_B$ on the right; $40_B$ has left child $37_R$. All omitted children are black null sentinels. Each root-to-null graph path has two real black nodes, and no red node has a red child.

Write $y=x+1$. After splaying on $x$, that key is at the root, and $y$ is the smallest key in its right subtree. This uses the integer assumption: no stored key lies strictly between $x$ and $y$. Thus $y$ has an empty left subtree while it remains within the right subtree of $x$.

Now perform ordinary bottom-up splaying on $y$. Until the final step involving $x$, all tree rotations occur below $x$ and leave it at the root. There are only two possible final cases.

Therefore $x$ becomes the left child of $x+1$. The argument applies more generally to consecutive keys in a binary search tree, even when their numerical difference is not one.

Use the usual bottom-up splaying operations. We prove the stronger result that at most three successful calls suffice. No insertions or deletions are needed.

If the chosen key $x$ is the minimum stored key, first perform splaying on $x$ and then on its immediate successor. The argument for consecutive keys in a binary search tree makes $x$ the left child of the successor with an empty right subtree; minimality makes its left subtree empty too. Hence $x$ is a leaf of a rooted tree. The maximum-key case is the mirror image.

Suppose $x$ is an interior key. Since at least four keys are stored, there are either two keys larger than $x$ or two smaller than $x$. In the former case choose four consecutive stored keyswhere $a$ is the predecessor of $x$, and $b,c$ are the next two successors. Perform $\mathrm{Splay}(c),\mathrm{Splay}(a),\mathrm{Splay}(b)$.

Here is a complete check of the local shapes. After the first call, $c$ is the root. After the second, $a$ is the root; every key below $a$ is in its left subtree $A$, and every key above $c$ stays in the right subtree $D$ of $c$. These outside subtrees cannot interfere with the next search. Between $a$ and $c$ there are only $x,b$. The last step of splaying on $a$ is either a zig step, leaving $c$ as its right child; a zig-zag step, with the same result; or a zig-zig step, leaving some $p\in \{x,b\}$ as its right child with $c$ immediately to the right of $p$. Consequently the possible right subtrees of $a$ are exactly among these four forms, using $k(L,R)$ for a node with its left and right subtrees:Here an unexpanded $x$ or $b$ denotes a node with no children. Each row follows by the indicated one or two tree rotations in each bottom-up step. All rows end with $x$ as the right child of $a$, with both its subtrees empty. If instead two keys below $x$ are available, reflect the construction, exchanging left and right and reversing the order of keys. This proves splaying a chosen node into a leaf for every node of every splay tree of size at least four.