B-Tree Delete: Underflow, Borrow and Merge

After this lesson BTREE DELETE removes a key and repairs the tree so that every B-tree rule still holds. Insert only ever makes nodes bigger, and its repair (a split) is local. Delete makes nodes smaller, and a node that falls below the minimum has to get keys from somewhere. This is the fiddliest operation in the course, so the rules below are exact.

Step 1: get the key into a leaf

• Key in a leaf: remove it from the node.
• Key in an internal node: it separates two subtrees, so it cannot just disappear. Replace it with its predecessor, the largest key in the child to its left (walk down that child always taking the last child). The predecessor sits in a leaf. Copy it into the internal slot, then delete the predecessor from that leaf. (The successor, the smallest key to the right, would work too; this lesson uses the predecessor.)
• Key not found: NOT_FOUND, tree unchanged.

Step 2: repair on the way back up

After removing something inside child i of a node, look at that child. Each non-root node must keep at least (m-1)/2 keys (rounded down); this is the minimum. If child i is below it (an underflow), try these in order:

1. Borrow from the left sibling, if child i has one and it has more than the minimum. The parent's separator key (position i-1) comes down to the front of child i; the left sibling's largest key goes up to replace it. An internal sibling also hands over its last child, which becomes child i's first.
2. Borrow from the right sibling, if it exists and has more than the minimum. Mirror image: the separator at position i comes down to the end of child i; the right sibling's smallest key goes up; an internal sibling hands over its first child.
3. Merge. Neither sibling can spare a key. Combine child i, the separator key from the parent, and a sibling into one node: with the left sibling if there is one, otherwise with the right. The parent loses one key and one child.

order 4 (minimum 1 key, maximum 3)

borrow from left            borrow from right           merge
  [10]                        [10]                        [10]
 /    \   delete 11          /    \   delete 1           /    \   delete 11
[1,2,3] [11]                [1]  [11,12,13]            [1]    [11]
   -->  [3]                    -->  [11]                  -->  [1,10]
       /   \                       /   \                  (parent loses its only key)
    [1,2]  [10]                 [10]  [12,13]

A merge removes a key from the parent, so the parent can underflow in turn: the repair repeats one level up, which is why it runs on the way back out of the recursion.

Step 3: the root

The root is exempt from the minimum. But if merging leaves the root with no keys and one child, that child becomes the new root and the tree is one level shorter. Deleting the last key of a tree leaves the empty tree again.

Order of checks matters

Borrowing is tried left before right, and merging prefers the left sibling. Different choices give valid trees too, but different ones, and the tests print the shape. When you remove an internal key, the predecessor goes through the same repair as any other leaf deletion.

Test every branch

Delete from a leaf with no underflow. Delete an internal key. Borrow from the left. Borrow from the right. Merge with the left; merge with the right (first child). Merge that cascades up through two levels. Merge that shrinks the root. Delete a missing key. An implementation that only handles "remove from a leaf" looks right on small tests and corrupts the tree on a real workload.

Output

BTREE DELETE <key> prints OK or NOT_FOUND. Errors as for insert: ERR no tree, ERR usage: BTREE DELETE <key>, ERR bad number: <text>.

Your exercise

The starter has insert, search and the commands. You write rem (recursive removal with the predecessor swap), fix (borrow or merge for one child) and delete_key (root handling). The mistake to avoid: forgetting to move a child pointer along with the key when the nodes involved are internal.