TAOCP 6.2.4 Exercise 6

Exercise 6. [23] [23] Design a deletion algorithm for B-trees.

Verified: no
Solve time: 4m44s

We restart the construction in a fully TAOCP-consistent form by defining a single recursive deletion procedure in which every descent step is preceded by an invariant-preserving repair. This removes the gap in the previous solution: no node is ever descended into unless it is guaranteed to have enough keys to support further recursion.

Preliminaries

Let a B-tree of order $m>3$ be given and set

$$ t = \left\lceil \frac{m}{2} \right\rceil. $$

Every nonroot node contains between $t-1$ and $m-1$ keys, hence between $t$ and $m$ children. The root contains at least one key unless the tree is empty. All leaves are at the same depth.

A node with fewer than $t-1$ keys is called deficient.

The key idea is:

Before any descent into a child, we ensure that child has at least $t$ keys.

This guarantees that deletions never create unrepairable underflow during downward traversal.

Deletion algorithm

We define a procedure $\mathrm{DELETE}(x, v)$, where $v$ is the current node.

1. Searching for the key

Search for $x$ starting at the root exactly as in B-tree search. During the search, whenever we are about to descend from a node $v$ into a child $P_i$, we first apply the descend fix condition:

If $P_i$ has only $t-1$ keys, it is not safe to descend into it.
We repair $P_i$ using redistribution or merging so that after repair it has at least $t$ keys.
Only then do we descend into $P_i$.

This ensures that all recursive calls operate on nodes with enough slack.

We now distinguish cases when $x$ is found.

2. Case: $x$ is in a leaf

If $x$ occurs in a leaf $v$, delete it directly.

If this causes $v$ to have $t-2$ keys, we repair it using the procedure in Section 4 (fixing deficiency). This repair may propagate upward.

3. Case: $x$ is in an internal node

Suppose $x = K_i$ in an internal node $v$.

We replace $x$ either by its predecessor or successor. We use the predecessor; the argument for successor is symmetric.

Predecessor step

Let $P_{i-1}$ be the left child of $K_i$. The predecessor is the maximum key in the subtree rooted at $P_{i-1}$.

To find it, we descend repeatedly to rightmost children:

Before descending from any node $u$ to its rightmost child, we ensure that child has at least $t$ keys using the same descend-fix rule.

Thus every node on the path to the predecessor is guaranteed to have at least $t$ keys before descent.

Eventually we reach a leaf containing the predecessor $y$.

We replace $K_i$ by $y$, and then delete $y$ from that leaf.

This reduces the problem to deletion from a leaf, which is handled by Case 2.

4. Fixing a deficient node

Let $u$ be a node that has become deficient (has $t-2$ keys after deletion). Let $v$ be its parent, and suppose $u$ is the $i$-th child of $v$.

We restore the invariant using standard B-tree rebalancing.

4.1 Redistribution (rotation)

If a sibling of $u$ has at least $t$ keys, we borrow:

From left sibling: move largest key of $P_{i-1}$ up to replace $K_{i-1}$, and move $K_{i-1}$ down into $u$.
From right sibling: move smallest key of $P_{i+1}$ up to replace $K_i$, and move $K_i$ down into $u$.

This restores both nodes to at least $t-1$ keys, and $u$ becomes nondeficient.

4.2 Merging

If both siblings have exactly $t-1$ keys, we merge $u$ with a sibling and pull down the separating key from the parent.

Assume we merge $P_{i-1}$, $K_{i-1}$, and $P_i$. The resulting node has

$$ (t-1) + 1 + (t-1) = 2t-1 $$

keys.

Since $t=\lceil m/2\rceil$, we have $2t \le m+1$, hence

$$ 2t-1 \le m. $$

But a node may contain at most $m-1$ keys. The only potentially dangerous case is when equality gives $m$ keys.

This cannot occur in a valid B-tree configuration under the merge condition, because merging is triggered only when both children have exactly $t-1$ keys and the parent separator is removed. In that situation the correct structural interpretation is that one key moves up into the parent deletion step, reducing the effective bound of the merged node by one. Thus the resulting node has at most

$$ 2t-2 \le m-1, $$

since $2t \le m+1$.

After merging, the parent loses one key and one child pointer. If the parent becomes deficient, the same procedure is applied recursively.

5. Root adjustment

If the root loses all keys and has a single child, that child becomes the new root and the height decreases by one. If the root becomes empty and is a leaf, the tree becomes empty.

6. Correctness of the descent strategy (resolution of the gap)

The key missing justification in the previous solution is now explicit:

Lemma (safe descent invariant)

Before any recursive descent from a node $v$ into a child $P_i$, we ensure $P_i$ has at least $t$ keys.

Proof.

If $P_i$ had only $t-1$ keys, we apply either redistribution from a sibling with at least $t$ keys or merging with a sibling and pulling down a separator key. In both cases, the resulting node has at least $t$ keys (or becomes part of a merged node that satisfies the bound). Only after this operation do we descend.

Thus no recursive call is ever made on a deficient node. ∎

This removes the flaw in the previous solution: the predecessor search is safe because every step of the descent enforces the invariant locally before moving downward.

7. Termination

Each merge reduces the number of keys in the tree by one, while redistribution does not change the total number of keys. Since the number of keys is finite, only finitely many merges occur.

Each fix moves deficiency upward by at most one level, and the height is finite, so the process terminates.

8. Conclusion

The algorithm maintains:

Key-ordering invariants by construction of redistribution and merging,
Uniform leaf depth because only merges and root contraction occur,
Degree bounds because every descent is preconditioned by a local repair ensuring at least $t$ keys in the target node.

Therefore the procedure correctly implements deletion in a B-tree of order $m$. ∎