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

Deletion Cases: Red Sibling

Handle deletion when the sibling of the double-black node is red through rotation and recoloring.

Deletion Cases: Red Sibling

What you'll learn: How to handle the specific case when deleting a node from a Red-Black tree leaves a "double-black" node whose sibling is red.

When you delete a node from a Red-Black tree, you might create a "double-black" situation—a violation that needs fixing. One particular case occurs when the sibling of this double-black node is red.

The Core Problem

Imagine you've just deleted a black node, and now its former position (or replacement) is "double-black." You look at its sibling—the other child of its parent—and discover that sibling is red. This red sibling blocks certain rebalancing strategies we might want to use.

The Solution: Rotate and Recolor

The fix is straightforward:

  1. Recolor the red sibling to black
  2. Recolor the parent to red (the parent must be black, since it has a red child)
  3. Rotate at the parent in the direction away from the double-black node

If the double-black node is the left child, perform a left rotation. If it's the right child, perform a right rotation.

Why This Works

This rotation doesn't immediately fix the double-black problem, but it transforms it into one of the other, simpler cases. Think of it as clearing the red sibling out of the way so you can now apply standard fixes. After the rotation, the double-black node has a new sibling—and that sibling is now black, which opens up other resolution strategies.

Key Takeaway: When a double-black node's sibling is red during Red-Black tree deletion, rotate away from the double-black node and swap the colors of the parent and sibling, converting the problem into a simpler case.