B-tree Delete

• This is a B-Tree with degree t=32
  • What is the minimum keys?
  • What is the maximum keys?
• Delete the following values from the tree, one at a time in the order of: 41, 13, 12, 11, 15.
• Redraw the tree after each insertion.

Start

Delete 41 from leaf, Case 1.

Delete 13 from internal node, Case 2a.

Delete 12 from internal node, Case 2c. Combine 11 | 12| 15, then delete 12 from leaf.

Delete 11, Case 3b. 11 must be in left side rooted at 10.

All siblings of 10 (40) have t-1 keys.

Merge x (25) with children.

Always results in new node of 2t-1 keys and decreasing height by 1.

Recurse on appropriate subtree (11|15) of 10|25|40 and delete.

Delete 15, Case 3a.

15 has only t-1 keys but can borrow from 5|7 with t keys.