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

Deletion Cases: Black Sibling with Red Children

Resolve double-black situations when the black sibling has at least one red child.

Deletion Cases: Black Sibling with Red Children

What you'll learn: How to fix a double-black node when its black sibling has at least one red child in a Red-Black tree.


The Situation

After deleting a node in a Red-Black tree, you may encounter a "double-black" problem where a node violates the black-height property. When the sibling of this double-black node is black and has at least one red child, you can resolve the violation through rotations and recoloring.

Why This Case is Special

Unlike the red sibling case (which requires a preliminary rotation), having a black sibling with red children gives you the "building blocks" needed to redistribute the black-height directly. The red child acts like a resource you can use to balance things out.

The Solution Strategy

This case splits into subcases based on which child is red (left, right, or both):

  1. Far red child (same side as sibling): Perform a single rotation toward the double-black node, recolor appropriately
  2. Near red child (opposite side from sibling): First rotate the sibling to convert it to case 1, then apply case 1's solution

Think of it like rearranging furniture: if the red child is already in the right position (far side), you make one move. If it's in the wrong position (near side), you reposition it first, then complete the fix.

The key moves involve:

  • Rotating to bring the black sibling up to the parent's position
  • Recoloring nodes to maintain Red-Black properties
  • The double-black is eliminated in the process

Key Takeaway: When a double-black node's black sibling has at least one red child, use rotations and strategic recoloring to redistribute black-height and resolve the violation in one or two steps.