B-Tree Deletion with Rebalancing

Topic Overview

Borrow and Merge on Underflow

Deletion removes a key from a leaf, then fixes underflow if a node drops below minimum occupancy by borrowing from a sibling or merging nodes and pulling a separator from the parent. Rebalancing is the symmetric counterpart to split on insert.

Fix Underflow Cases

If left or right sibling has extra keys, rotate keys through parent. Otherwise merge with sibling and remove separator from parent, possibly cascading upward.

cCopy
Loading…

• Delete from internal nodes copies predecessor/successor from leaves
• Merge reduces tree height when root becomes empty separator
• On-disk implementations must log merges for crash safety
• Test alternating insert/delete sequences to expose bugs

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement delete with borrow and merge rebalancing. This exercise asks you to show a case where merge reduces sibling count and updates the parent.

Your Task

Delete keys from a B-tree (MAX_KEYS = 3, MIN_KEYS = 1) and keep it balanced. The tree starts as

cCopy
Loading…

and stays two levels deep: a root of separator keys over leaves, until a merge empties the root.

Delete K:

1. If K is a root key, replace it with its predecessor, the largest key in the leaf to its left, and remove that key from the leaf.
2. Otherwise find the leaf K belongs in (keys below the first separator go to leaf 0, and so on) and remove K. If it is not there, the delete does nothing.
3. If that leaf now has fewer than MIN_KEYS keys, repair it in this order:
   • Borrow from the left sibling, if it has more than MIN_KEYS. The separator between them moves down to the front of this leaf, and the sibling's largest key moves up to replace it.
   • Otherwise borrow from the right sibling, if it has more than MIN_KEYS. The separator moves down to the end of this leaf, and the sibling's smallest key replaces it.
   • Otherwise merge. With a left sibling, the left sibling, the separator and this leaf become one leaf. With only a right sibling, this leaf, the separator and the right sibling do. The separator leaves the root. If the root has no keys left, the merged leaf becomes the whole tree.

Once the tree is a single leaf, deletes just remove keys from it.

Input

delete K commands, one per line.

Output

First the starting tree, tree: [20] / [5,10,15] [25,30,35]. Then for each delete:

1. one of delete K: removed from leaf, delete K: internal key, replaced by predecessor P or delete K: missing;
2. if a repair happened, borrow from left sibling, borrow from right sibling, merge with left sibling or merge with right sibling, followed by root emptied: tree height shrinks when the root ran out of keys;
3. the tree after the delete: tree: [root keys] / [leaf] [leaf] ..., or tree: [keys] once it is a single leaf.

Finally redistributions=R merges=M min_keys_ok=yes. The last field is yes when every leaf under a root has at least MIN_KEYS keys.