Course contentsShow
← Computer Science
Lesson 565 of 2,87213. Balanced TreesFree lesson

Borrowing Keys from Siblings

Fix underfull nodes by borrowing keys from adjacent siblings through parent key rotation.

Borrowing Keys from Siblings

You'll learn: How to fix an underfull B-Tree node by transferring a key from an adjacent sibling through the parent, maintaining balance without merging.

When deleting from a B-Tree, you might create an underfull node — one with fewer keys than the minimum required. Before resorting to merging nodes (which can propagate changes upward), we first check if a sibling can spare a key.

The Core Idea

Think of siblings as neighbors sharing resources. If your node is too empty but your sibling has extras, you can "borrow" through your shared parent:

  1. Identify a sibling with more than the minimum number of keys (it has extras to share)
  2. Rotate keys through the parent: move a parent key down to the underfull node
  3. Replace the parent key with a key from the generous sibling

This is like a circular shift: sibling → parent → underfull node, keeping the BST ordering intact throughout.

Example

Suppose you have nodes where minimum is 2 keys:

  • Underfull node: [10] (only 1 key)
  • Parent key between them: [20]
  • Right sibling: [25, 30, 35] (has 3 keys, can spare one)

After borrowing:

  • Underfull node becomes: [10, 20] (now valid!)
  • Parent gets: [25]
  • Sibling becomes: [30, 35] (still valid)

The key 20 moved down, and 25 moved up. Child pointers also shift accordingly to maintain the search property.

When Borrowing Works

Borrowing only succeeds when a sibling has more than the minimum required keys. If both siblings are already at minimum capacity, you must merge instead.

Key Takeaway: Borrowing from siblings fixes underfull nodes through parent key rotation, maintaining B-Tree invariants without the cost of merging when adjacent nodes have spare capacity.