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

Insertion Case 2: Uncle is Black, Triangle Configuration

Resolve triangle configurations with rotations to convert into a line configuration.

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:

  1. Identify that you have a triangle: the new node is an "inner child" (opposite direction from its parent relative to the grandparent)
  2. Perform a rotation at the parent to straighten the path
  3. 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.