Removal from B-Tree

The remove(x) operation in a BTree is, again, most easily implemented as a recursive method. Although the recursive implementation of remove(x) spreads the complexity across several methods.

Visual demonstration of the remove() operation

The overall process, which is illustrated in below illustration, is fairly straightforward.

By shuffling keys around, removal is reduced to the problem of removing a value, $x^{\prime}$, from some leaf, u. Removing $x^{\prime}$ may leave u with less than $B − 1$ keys; this situation is called an underflow.

When an underflow occurs, u either borrows keys from, or is merged with, one of its siblings. If u is merged with a sibling, then u’s parent will now have one less child and one less key, which can cause u’s parent to underflow; this is again corrected by borrowing or merging, but merging may cause u’s grandparent to underflow. This process works its way back up to the root until there is no more underflow or until the root has its last two children merged into a single child. When the latter case occurs, the root is removed and its lone child becomes the new root.

Next we delve into the details of how each of these steps is implemented. The first job of the remove(x) method is to find the element x that should be removed. If x is found in a leaf, then x is removed from this leaf. Otherwise, if x is found at u.keys[i] for some internal node, u, then the algorithm removes the smallest value, $x^{\prime}$, in the subtree rooted at u.children[i + 1]. The value $x^{\prime}$ ...