Deletion from a B-Tree

Recall: in a BST, if the value to be deleted does not occur in a leaf, we replace it with the largest value from its left subtree, and then delete that value from the left subtree.

We proceed similarly in a B-tree.

Furthermore, the largest value in a left subtree is guaranteed to be in a leaf node.

To delete X from a leaf node:

1. Remove X from current node. There are no subtrees to worry about.

2. If >= (M-1)/2 values, Done! Else, node underflowed and needs repair.

How to repair a non-root node? Consider deleting 6 from: