Rotations in Red-Black Tree

🧑‍💻 By • 📅 Published on: 18 July 2025

Balancing a binary search tree is crucial to ensuring efficient performance. One of the most powerful self-balancing binary search trees is the Red-Black Tree (RBT), widely used in memory management, language libraries (like C++ STL map and set), and database indexing.

But what keeps this tree balanced? The secret lies in rotations – a fundamental set of operations that restructure the tree while maintaining the Red-Black properties.

Different Kinds of Rotations in Red-Black Tree

In a Red-Black Tree (RBT), rotations are key operations used to restore balance when Red-Black properties are violated after insertion or deletion.

There are two basic types of rotations, and they may be combined in specific cases:

1. Left Rotation (Single Rotation)

Purpose:
Used when a right child becomes heavier, and the tree needs to be rotated left to maintain balance.

How it works:

• Node x has a right child y
• We move y up and x becomes the left child of y

Before Rotation:

    x
     \
      y
     / \
    T2 T3

After Left Rotation:

      y
     / \
    x  T3
   / \
 T1  T2

Used in Red-Red violations (e.g., Right-Right case during insert)

2. Right Rotation (Single Rotation)

Purpose:
Used when a left child becomes heavier, and the tree needs to be rotated right.

How it works:

• Node y has a left child x
• We move x up and y becomes the right child of x

Before Rotation:

      y
     /
    x
   / \
 T1  T2

After Right Rotation:

     x
    / \
  T1   y
      / \
     T2 T3

Used in Left-Left case of Red-Red violation

3. Left-Right Rotation (Double Rotation)

Purpose:
Used when the left child has a right-heavy subtree.

Steps:

1. First, perform Left Rotation on left child.
2. Then, perform Right Rotation on grandparent.

Before:

      z
     /
    x
     \
      y

After Left-Right Rotation:

      y
     / \
    x   z

This happens during insertion when node is inserted in Left-Right position.

✅ 4. Right-Left Rotation (Double Rotation)

Purpose:
Used when the right child has a left-heavy subtree.

Steps:

1. First, perform Right Rotation on right child.
2. Then, perform Left Rotation on grandparent.

Before:

      x
       \
        z
       /
      y

After Right-Left Rotation:

      y
     / \
    x   z

This happens during insertion when node is inserted in Right-Left position.

Summary Table of Rotations

Rotation Type	When to Use	Action
Left Rotation	Right-heavy subtree (Right-Right)	Rotate left at the node
Right Rotation	Left-heavy subtree (Left-Left)	Rotate right at the node
Left-Right Rotation	Left-Right case	Left rotate → then right
Right-Left Rotation	Right-Left case	Right rotate → then left

Understand how rotation work on R B Tree?

Suppose we have elements 10, 20, 30 to insert.

Step 1: Insert 10

[10B]

First node → make it Black
(No violation, it becomes the root)

Step 2: Insert 20

  10B
     \
     20R

New node is inserted as Red

No violation: Red node has Black parent → ✅

🚫 Step 3: Insert 30

  10B
     \
     20R
        \
        30R

Violation: Red node (30) has Red parent (20) → 🚨 Red-Red Violation

Fixing the Violation

Here:

• Parent (20) is Right Child of 10
• Uncle is NULL / Black
• Case → Right-Right violation
  👉 Apply Left Rotation on 10

After Left Rotation on 10

   20B
  /   \
10R   30R

• 20 becomes new root
• 10 and 30 are red
• No more red-red violation
• ✅ Valid Red-Black Tree

🌟 Final Tree

   20B
  /   \
10R   30R

Key Concepts in This Example

Step	Action	Reason
1	Insert 10B	Root is always Black
2	Insert 20R	Red child of Black → no issue
3	Insert 30R	Red child of Red → Violation 🚨
4	Left Rotate at 10	Fix Right-Right case
5	Recolor after rotation	Make new root Black, children Red

❓One question might come in your mind

When we inserted 10 and made it Black (10B), and later did a rotation — why did 10 become Red (10R)?

Answer:

Yes, initially, 10 was Black (as it’s the root).
But after the Left Rotation, we need to recolor the nodes to maintain Red-Black Tree properties.

Let’s break it down again with rotation and coloring logic:

📌 Initial Insertions:

• 10 → becomes Black (root)
• 20 → inserted as Red
• 30 → inserted as Red

We now have:

  10B
     \
     20R
        \
        30R

Now a Red-Red violation happens (20R → 30R).

🔄 Fix: Left Rotation at 10

We get:

   20
  /  \
10    30

Now the question is:
What colors should we assign to 10, 20, and 30 after rotation?

🎯 Color Adjustment After Rotation

• The new root (20) becomes Black
• Its children (10, 30) become Red

👉 So now:

   20B
  /   \
10R   30R

Why Recolor?

Because Red-Black Tree properties must be satisfied:

1. Root must be Black
2. No two consecutive Red nodes
3. Black height must remain same

To satisfy these:

• Promote middle node (20) as new Black root
• Demote the rest (10, 30) to Red

✅ Final Tree:

   20B
  /   \
10R   30R

This tree is balanced and follows all RB-Tree rules.

Summary:

• Yes, 10 was initially Black
• But after rotation, roles shift and we recolor to preserve Red-Black rules
• It is normal and necessary to recolor the previous Black node to Red after rotation in certain cases