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

Insertion Case 1: Uncle is Red

Handle the case where the inserted node's uncle is red through recoloring propagation.

Insertion Case 1: Uncle is Red

What you'll learn: How to fix a Red-Black Tree violation when the newly inserted node's uncle is also red, using a simple recoloring technique.

The Problem

When you insert a new red node into a Red-Black Tree, you might create a violation: two consecutive red nodes (parent and child). To fix this, you need to check the color of the inserted node's "uncle" — the sibling of its parent.

When the uncle is red, you have the simplest case to handle.

The Solution: Recoloring

Instead of rotating nodes (which can be complex), you can fix this violation through recoloring:

  1. Color the parent black (removes the red-red violation)
  2. Color the uncle black (maintains balance on that side)
  3. Color the grandparent red (compensates for adding two black nodes)

Think of it like balancing a scale: you're adding "weight" (blackness) to both sides equally, so you lighten the top (grandparent) to keep things balanced.

Propagation Upward

Here's the catch: making the grandparent red might create a new red-red violation higher up the tree (if the grandparent's parent is also red). So you propagate the fix upward, treating the grandparent as the "newly inserted" node and repeating the process.

Eventually, you either:

  • Reach a point where no violation exists, or
  • Reach the root (which you then color black)

This propagation can continue all the way up the tree, but each step is just recoloring—no rotations needed!

Key Takeaway: When inserting into a Red-Black Tree and the uncle is red, fix violations by recoloring the parent and uncle black and the grandparent red, then propagate the check upward through the tree.