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

Insertion Case 3: Uncle is Black, Line Configuration

Fix line configurations through rotation and recoloring to restore red-black properties.

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:

  1. 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
  2. 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.