Insertion Case 2: Uncle is Black, Triangle Configuration
What you'll learn: How to handle the "triangle" insertion case in Red-Black trees by transforming it into a simpler "line" configuration.
The Triangle Problem
When inserting a red node into a Red-Black tree, you may violate the "no two consecutive red nodes" rule. If the uncle node is black (or null), you need to perform rotations. The triangle configuration occurs when the newly inserted node, its parent, and grandparent form a zig-zag pattern—like a bent elbow or triangle shape.
For example:
- Grandparent → Left child (parent) → Right child (new node), OR
- Grandparent → Right child (parent) → Left child (new node)
Converting Triangle to Line
The triangle case cannot be directly fixed with a single rotation. Instead, you must first convert it into a line configuration (which you'll resolve in the next step).
How it works:
- Identify that you have a triangle: the new node is an "inner child" (opposite direction from its parent relative to the grandparent)
- Perform a rotation at the parent to straighten the path
- After this rotation, the original new node moves up and the parent moves down, creating a straight line from grandparent to the bottom
Example: If the path goes right-then-left (grandparent→right child→left grandchild), perform a right rotation on the parent. This transforms the triangle into a left-left line.
Key Takeaway: The triangle configuration in Red-Black tree insertion requires an initial rotation at the parent level to convert it into a line configuration before final rebalancing can occur.