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:
- Color the parent black (removes the red-red violation)
- Color the uncle black (maintains balance on that side)
- 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.