TAOCP 6.2.3 Exercise 28
A 2-3 tree is a rooted ordered tree in which every internal node has either two or three children and contains respectively one or two keys, and in which all external nodes occur at the same level.
Exercise 28. [41] [41] Prepare efficient implementations of 2-3 tree algorithms.
Verified: yes
Solve time: 1m27s
Setup
A 2-3 tree is a rooted ordered tree in which every internal node has either two or three children and contains respectively one or two keys, and in which all external nodes occur at the same level. Keys within a node are stored in increasing order, and subtrees are ordered so that keys in the $i$th subtree lie strictly between the $(i-1)$st and $i$th keys of the node.
Let $N$ denote the number of internal keys stored in the tree. Let $h$ denote the common level of all external nodes. Every node at level $d < h$ has exactly two or three children, so every root-to-leaf path has length $h$.
The task is to give implementations of search, insertion, and deletion for 2-3 trees, and to justify that each operation requires $O(\log N)$ time in the sense of node visits and key comparisons.
Solution
Search proceeds by a single downward traversal from the root. At a node containing one key $K_1$, comparison of the search key $K$ with $K_1$ determines whether the search continues in the left or right subtree. At a node containing two keys $K_1 < K_2$, comparison of $K$ with $K_1$ and $K_2$ determines uniquely one of three subtrees in which the search continues. Since each step moves from a node at level $d$ to a node at level $d+1$, the search terminates after reaching a leaf level or locating the key. The number of node visits equals $h+1$.
Insertion begins by performing a search for key $K$ until a leaf position where $K$ would belong is identified. The key is then inserted into that leaf node. If the node originally contains one key, it becomes a valid node with two keys and no further action is required. If the node already contains two keys, insertion produces a temporary three-key node. Let the ordered keys in this node be $K_1 < K_2 < K_3$. The middle key $K_2$ is separated and promoted to the parent node, while two new nodes are formed, one containing $K_1$ and one containing $K_3$, each inheriting appropriate subtrees if the node is internal.
If the parent node receives a promoted key and thereby acquires a third key, the same splitting operation is applied recursively. If this propagation reaches the root, a new root is created containing the single promoted key and two children, increasing the height from $h$ to $h+1$.
Deletion begins by locating the key $K$ using the search procedure. If $K$ is located in an internal node, it is replaced by either its immediate predecessor or successor key in inorder sequence, which lies in a leaf node. The deletion is therefore reduced to removal of a key from a leaf node.
If removal from a leaf node leaves that node with one key, no structural change is required. If it leaves the node empty, an underflow occurs. Let $v$ be the underflow node and let $w$ be an adjacent sibling under the same parent.
If $w$ contains two keys, redistribution is performed by moving a boundary key from $w$ into the parent and moving the corresponding separator key from the parent into $v$, restoring both nodes to valid configurations with at least one key.
If $w$ contains one key, merging is performed by combining $v$, the separating parent key, and $w$ into a single node containing two keys. This reduces the number of children of the parent by one. If the parent becomes deficient by losing its only key, the same adjustment procedure is applied recursively upward. If the root becomes empty, its single child becomes the new root, decreasing the height by one.
Correctness of search follows from the ordering invariant at each node and the partition property of subtrees. Correctness of insertion follows from preservation of inorder sequence during promotion and splitting. Correctness of deletion follows from preservation of inorder sequence during redistribution and merging.
The height bound follows from the observation that every internal node has at least two children. Thus the number of leaves at height $h$ is at least $2^h$, so $N+1 \ge 2^h$, hence $h \le \lg(N+1)$. Since every node has at most three children, a standard induction on height using the recurrence for minimum nodes shows that $N+1 \le 3^h$, hence $h \ge \log_3(N+1)$. Therefore $h = \Theta(\log N)$, and every operation performs $O(h)$ node transitions and $O(1)$ key comparisons per node.
Each of search, insertion, and deletion therefore requires $O(\log N)$ time.
This completes the solution. ∎