Insertion in Red-Black Tree: All Cases Explained with Algorithm

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

Red-Black Tree is a self-balancing binary search tree. When a node is inserted, the structure of the tree may violate some of its coloring properties. Therefore, we need to fix those violations using recoloring and rotations to maintain balance.

Let’s explore how insertion works in a Red-Black Tree — step-by-step — including all the violation cases and their fixes.

Properties of Red-Black Tree

Before diving into insertion cases, remember the five key properties of a Red-Black Tree:

1. Each node is either red or black.
2. The root is always black.
3. All leaves (NIL or NULL) are black.
4. If a node is red, both its children must be black (no two reds in a row).
5. Every path from a node to its descendant NULL nodes must have the same number of black nodes (black-height).

Inserting a Node in Red-Black Tree

New nodes are always inserted as RED, which may cause a violation of Red-Black Tree properties. The primary violation is two consecutive RED nodes (which breaks property 4).

Let’s break down all the cases.

Case 1: Parent is Black — No Violation

▶️ Description:

• You insert the new red node z.
• Its parent is black, so property 4 is not violated.

✅ Fix:

No fix is needed. The tree remains valid.

Case 2: Parent is Red — Violation

When the parent is RED, it causes a violation: two red nodes in a row, which violates Red-Black Tree property 4.

Let’s analyze this in two sub-cases depending on the color of the uncle (parent’s sibling).

🔴 Case 2a: Uncle is Red (Recoloring)

▶️ Problem:

• Node z‘s parent and uncle are both red.
• Grandparent is black (because a red node can’t have a red parent).

🛠 Fix:

• Recolor parent and uncle to BLACK.
• Recolor grandparent to RED.
• Move the pointer up to the grandparent and repeat the fix

💡 Example:

      20B
     /   \
   10R   30R
  /
5R ← insert this

Here, both 10 (parent) and 30 (uncle) are red → Apply recoloring.

⚫ Case 2b: Uncle is Black or NIL (Rotation Needed)

This case is more complex and requires rotations and recoloring.

We further divide this based on the shape (inner or outer grandchild):

🔁 Case 2b-i: z is an Inner Child (Left-Right or Right-Left)

• Perform a rotation at z’s parent to make z into an outer child (Left-Left or Right-Right case).
• Then go to Case 2b-ii.

💡 Example:

Inserting 15 in this configuration:

      20B
     /
   10R
     \
     15R ← insert this

Here, z = 15 is an inner grandchild.

First, rotate left at 10, then proceed to the next step.

🔁 Case 2b-ii: z is an Outer Child (Left-Left or Right-Right)

• Recolor the parent to BLACK.
• Recolor the grandparent to RED.
• Rotate at the grandparent.

💡 Example:

After the previous step, we get:

      20B
     /
   15R
   /
 10R

Now:

• Recolor 15 → BLACK, 20 → RED.
• Perform right rotation at 20.

Red-Black Tree Insert Fix-Up Algorithm

RB-Insert(T, z):
    Insert z as in BST, set color[z] = RED

    while color[parent[z]] == RED:
        if parent[z] is left child of grandparent[z]:
            y = uncle[z] (right child of grandparent)
            if color[y] == RED:    # Case 2a
                color[parent[z]] = BLACK
                color[y] = BLACK
                color[grandparent[z]] = RED
                z = grandparent[z]
            else:
                if z == right child of parent[z]:  # Case 2b-i
                    z = parent[z]
                    Left-Rotate(T, z)
                color[parent[z]] = BLACK          # Case 2b-ii
                color[grandparent[z]] = RED
                Right-Rotate(T, grandparent[z])
        else:
            (Same as above, with left and right swapped)

    color[root] = BLACK

Summary Table of Insertion Cases

Case	Condition	Action
Case 1	Parent is Black	No action needed
Case 2a (Recolor)	Parent & Uncle are Red	Recolor parent & uncle, move up
Case 2b-i	Uncle is Black, z is inner child	Rotate at parent
Case 2b-ii	Uncle is Black, z is outer child	Recolor and rotate at grandparent