B-Tree Deletion with Rebalancing

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.

c
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.

Write a C program that implements B-tree deletion with rebalancing.

Requirements:

Use MAX_KEYS=3, MIN_KEYS=1
Implement btree_delete(root, key) that removes a key and rebalances
Implement helper functions:
- borrow_from_left(node, parent_index): redistribute with left sibling
- borrow_from_right(node, parent_index): redistribute with right sibling
- merge_with_sibling(node, parent_index): merge with a sibling
Start with a pre-built tree: Root: keys=[20], children=[left, right] left: keys=[5, 10, 15], is_leaf=1 right: keys=[25, 30, 35], is_leaf=1
Delete 5 (simple, leaf has > MIN_KEYS)
Delete 15 (leaf drops to MIN_KEYS, borrow from right sibling or merge)
Delete 20 (internal node, replace with predecessor or successor)
After each deletion, print the tree structure
Verify that no node has fewer than MIN_KEYS keys
Count and print the number of redistribution and merge operations performed

Borrow and Merge on Underflow

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.

c
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.

Write a C program that implements B-tree deletion with rebalancing.

Requirements:

Use MAX_KEYS=3, MIN_KEYS=1
Implement btree_delete(root, key) that removes a key and rebalances
Implement helper functions:
- borrow_from_left(node, parent_index): redistribute with left sibling
- borrow_from_right(node, parent_index): redistribute with right sibling
- merge_with_sibling(node, parent_index): merge with a sibling
Start with a pre-built tree: Root: keys=[20], children=[left, right] left: keys=[5, 10, 15], is_leaf=1 right: keys=[25, 30, 35], is_leaf=1
Delete 5 (simple, leaf has > MIN_KEYS)
Delete 15 (leaf drops to MIN_KEYS, borrow from right sibling or merge)
Delete 20 (internal node, replace with predecessor or successor)
After each deletion, print the tree structure
Verify that no node has fewer than MIN_KEYS keys
Count and print the number of redistribution and merge operations performed

Topic Overview

Borrow and Merge on Underflow

Fix Underflow Cases

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source

B-Tree Deletion with Rebalancing

Topic Overview

Borrow and Merge on Underflow

Fix Underflow Cases

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source