B-Tree Delete & Rebalancing

B-tree deletion is the most complex B-tree operation. When removing a key causes a node to have too few keys (underflow), the tree must rebalance through rotation or merging.

Minimum Key Requirement

For a B-tree of order M, every non-root node must have at least ceil(M/2) - 1 keys. For order 3, that's 1 key minimum. Deletion must maintain this invariant.

Case 1: Delete from Leaf (No Underflow)

The simple case — just remove the key:

Delete 30 from leaf [25, 30]:
Result: [25]    (still >= 1 key, we're fine)

Case 2: Delete from Internal Node

You can't just remove a key from an internal node because it separates children. Replace it with its in-order predecessor (largest key in the left subtree) or in-order successor (smallest key in the right subtree):

Delete 20 from:       [20]
                      /    \
                  [10,15]  [25,30]

Replace 20 with predecessor (15):
                      [15]
                     /    \
                  [10]   [25,30]

This converts the problem to deleting from a leaf.

Case 3: Underflow — Rotation (Borrowing)

If deletion causes underflow and a sibling has spare keys, perform a rotation:

Delete 10 from:     [20]
                   /    \
                [10]   [25,30]

[10] → [] (underflow!)
Right sibling [25,30] has a spare key.

Rotate left:
- Pull 20 down from parent
- Push 25 up to parent

Result:        [25]
              /    \
           [20]   [30]

Case 4: Underflow — Merge

If no sibling has spare keys, merge with a sibling and pull the separating key down from the parent:

Delete 25 from:     [20]
                   /    \
                [10]   [25]

[25] → [] (underflow!)
Left sibling [10] is at minimum. Merge:

Pull 20 down, merge [10] and []: [10, 20]
Result: [10, 20]  (root's children gone, root is removed)

Edge Case: Shrinking the Root

When a merge causes the root to become empty (no keys left), the merged child becomes the new root. This is the only way a B-tree shrinks in height.

How Real Databases Handle Delete

In practice, many databases use lazy deletion. SQLite marks cells as free within the page and reuses the space later. PostgreSQL doesn't physically delete index entries at all — dead entries are cleaned up by VACUUM. This simplifies concurrent operations but wastes space until cleanup runs.

Your Task

Implement B-tree delete handling all cases: leaf deletion, internal node deletion via predecessor swap, rotation (borrowing from siblings), and merge with root shrinking.