Insertion Case 3: Uncle is Black, Line Configuration
What you'll learn: How to fix a red-black tree when a red node and its red parent form a straight line and the uncle is black.
The Line Configuration Problem
After inserting a red node into a red-black tree, you might find yourself with two consecutive red nodes (violating the "no two reds in a row" rule). When the uncle is black and the new node, its parent, and grandparent form a straight line (either all left children or all right children), you have Case 3.
Think of this like three dominoes leaning in the same direction — they form a line, either left-left-left or right-right-right up the tree.
How to Fix It
The fix requires two steps:
-
Rotate at the grandparent in the opposite direction of the line
- If it's a left-line (grandparent → left child → left child), perform a right rotation at grandparent
- If it's a right-line (grandparent → right child → right child), perform a left rotation at grandparent
-
Recolor after rotation:
- The old parent (now in the grandparent's position) becomes black
- The old grandparent (now a child) becomes red
Why This Works
The rotation restructures the tree so the black-height remains consistent on all paths, and the recoloring ensures no two red nodes are adjacent. The single rotation is sufficient because all three nodes are aligned — unlike Case 2 (triangle), which needs two rotations.
Key Takeaway: When a red node and its red parent form a straight line with a black uncle, fix the violation with one rotation at the grandparent (opposite the line direction) followed by swapping the colors of the old parent and grandparent.