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

B-Tree Deletion: Internal Node Cases

Delete keys from internal nodes by replacing with predecessor or successor keys from appropriate subtrees.

B-Tree Deletion: Internal Node Cases

What you'll learn: How to handle deletion when the key to remove exists in an internal (non-leaf) node of a B-Tree.

The Challenge with Internal Nodes

When you need to delete a key from an internal node, you can't just remove it—doing so would leave a "hole" and break the B-Tree structure where keys separate child pointers. The solution is clever: replace the key with a suitable substitute from one of its subtrees.

The Replacement Strategy

Think of it like removing a manager from an organizational chart. You don't leave the position empty; you promote someone from below. In a B-Tree, you have two candidates:

  1. Inorder predecessor: The largest key in the left subtree (the key that comes immediately before in sorted order)
  2. Inorder successor: The smallest key in the right subtree (the key that comes immediately after in sorted order)

Either replacement maintains the B-Tree ordering property because these keys naturally "fit" in the internal node's position.

How It Works

When deleting key k from an internal node:

  1. Find the predecessor (from left child subtree) or successor (from right child subtree)
  2. Replace k with that predecessor/successor key
  3. Recursively delete that predecessor/successor from its original leaf node position

This transforms the internal node deletion into a leaf node deletion—a simpler problem you already know how to solve!

The choice between predecessor and successor often depends on which subtree has more keys, helping maintain better balance.

Key Takeaway: B-Tree internal node deletion works by replacing the target key with its inorder predecessor or successor from an appropriate subtree, then recursively deleting that replacement key from its original position (which will be in a leaf or closer to one).