Red-Black Tree Deletion – Complete Examples with Diagrams & Step-by-Step Fixes

---

1. Recap: Red-Black Tree Properties

#	Rule
1	Every node is RED or BLACK
2	Root is BLACK
3	NULL leaves are BLACK
4	No two RED nodes adjacent
5	Same number of BLACK nodes on every path to leaf (Black Height)

---

2. Deletion Overview

Steps

1. Delete node as in BST (3 cases: 0, 1, or 2 children)
2. If deleted node was BLACK → Black Height violation
3. Fix using sibling, parent, and rotations

Goal: Restore Black Height and no RED-RED

---

3. Deletion Cases (After BST Delete)

Case	Deleted Node Color	Fix Needed?
A	RED	No fix (BH unchanged)
B	BLACK	Yes → Double Black

We only fix Case B

---

4. Double Black (DB) Fix – 6 Subcases

Let x = Double Black node (or its replacement)
Let s = Sibling of x
Let p = Parent of x

Case	Condition	Fix
1	s is RED	Recolor + Rotate
2	s is BLACK, both children of s are BLACK	Recolor s to RED
3	s is BLACK, left child of s RED, right BLACK	Right rotate on s
4	s is BLACK, right child of s RED	Left rotate on p + Recolor

---

5. Full Example 1: Delete 20 (Leaf, BLACK)

Initial Tree:
        30(B)
       /    \
     20(B)  40(B)
    /        \
  10(R)      50(R)

Step 1: Delete 20 (BLACK leaf)

→ Replace with NULL → Double Black at NULL

        30(B)
       /    \
     DB     40(B)
    /        \
  10(R)      50(R)

• x = DB (NULL under 30)
• p = 30(B)
• s = 40(B)

---

Case 2: s BLACK, both children BLACK

s = 40(B)
left(40) = NULL(B), right(40) = 50(R)? → Wait, 50 is RED!

→ Not Case 2

---

Case 4: s BLACK, right child RED

s = 40(B), right = 50(R)

Fix:

1. Left rotate on p (30)
2. Swap colors: p → RED, s → BLACK
3. s.right → BLACK

---

After Fix

        40(B)
       /    \
     30(R)  50(B)
    /  
  10(R)

→ Black Height restored
→ No RED-RED
→ Done

---

6. Full Example 2: Delete 50 (Leaf, RED)

        30(B)
       /    \
     20(B)  40(B)
    /        \
  10(R)      50(R)

Delete 50 (RED leaf) → Replace with NULL

        30(B)
       /    \
     20(B)  40(B)
    /      
  10(R)

→ No fix needed (RED deleted → BH unchanged)

---

7. Full Example 3: Delete 40 (Internal, BLACK, 1 child)

        30(B)
       /    \
     20(B)  40(B)
    /        \
  10(R)      50(R)

Delete 40 (BLACK), has right child 50

→ Replace 40 with 50 → 50 becomes Double Black

        30(B)
       /    \
     20(B)  DB(50)
    /      
  10(R)

• x = 50 (DB)
• p = 30(B)
• s = 20(B)

---

Case 2: s BLACK, both children BLACK

s = 20(B), left=10(R), right=NULL → Wait, left is RED!

→ Not Case 2

---

Case 3: s BLACK, left child RED

Fix:

1. Right rotate on s (20)
2. Swap colors: s → RED, s.left → BLACK

Before:
        30(B)
       /    \
     20(B)  50(DB)
    /      
  10(R)

After Right Rotate on 20:
        30(B)
       /    \
     10(R)  50(DB)
      \    
      20(R)

→ Now x = 50(DB), s = 20(R)

---

Case 1: s is RED

Fix:

1. Left rotate on p (30)
2. Swap colors: p → RED, s → BLACK

        20(B)
       /    \
     10(R)  30(R)
             \
             50(DB)

→ Now x = 50(DB), s = NULL (BLACK)

→ Case 2: s BLACK, both children BLACK

Fix: Color s (NULL) → RED (no change), move DB up to p

        20(B)
       /    \
     10(R)  30(DB)

→ x = 30(DB), p = 20(B), s = 10(R)

---

Case 1 Again: s is RED

Fix:

1. Right rotate on p (20)
2. p → RED, s → BLACK

        10(B)
         \
         20(R)
          \
          30(DB)

→ x = 30(DB), s = NULL → Case 2

Fix: Move DB up → p = NULL (root)

→ Root becomes DB → Color root BLACK

        10(B)
         \
         20(R)
          \
          30(B)

Final Tree – Balanced!

---

8. Full Example 4: Delete 10 (Leaf, RED)

        30(B)
       /    \
     20(B)  40(B)
    /        \
  10(R)      50(R)

→ Delete 10 → NULL → No fix (RED)

---

9. Deletion Code (Critical Part)

void deleteFixup(struct RBNode** root, struct RBNode* x) {
    while (x != *root && !isRed(x)) {
        if (x == x->parent->left) {
            struct RBNode* s = x->parent->right;

            // Case 1: s RED
            if (isRed(s)) {
                s->color = BLACK;
                x->parent->color = RED;
                leftRotate(root, x->parent);
                s = x->parent->right;
            }

            // Case 2: s BLACK, both children BLACK
            if (!isRed(s->left) && !isRed(s->right)) {
                s->color = RED;
                x = x->parent;
            } else {
                // Case 3: s BLACK, left RED
                if (isRed(s->left)) {
                    s->left->color = BLACK;
                    s->color = RED;
                    rightRotate(root, s);
                    s = x->parent->right;
                }
                // Case 4: s BLACK, right RED
                s->color = x->parent->color;
                x->parent->color = BLACK;
                s->right->color = BLACK;
                leftRotate(root, x->parent);
                x = *root;
            }
        } else {
            // Symmetric for right side
            // ... (mirror code)
        }
    }
    if (x) x->color = BLACK;
}

---

10. Summary: Deletion Cases

Deleted Node	Fix?	Why
RED leaf	No	BH unchanged
BLACK leaf	Yes	BH decreases
BLACK internal	Yes	Replace with child → DB

---

11. Visual: Deletion Flow

Delete 40 (BLACK)
│
├─ Replace with 50 → 50 is DB
├─ Case 3 → Rotate → Case 1 → Rotate → Case 2 → Move DB up
└─ Final: Balanced tree

---

12. Practice Problems

1. Delete 30 from Example 3 → Show all steps
2. Delete 20 (BLACK leaf) → Use Case 2
3. Delete root (BLACK) → How to fix?
4. Insert 1,2,3,4,5 → Delete 3 → Trace
5. Compare: AVL vs RB deletion rotations

---

13. Key Takeaways

Insight
Only fix if BLACK deleted
Double Black = Black Height violation
Sibling is key to fix
Case 1 (s RED) → Always rotate first
Case 2 → Simplest: recolor and move up
Case 3 & 4 → Rotate to make Case 4
Root fix → Just color BLACK
At most 3 rotations

---

End of Red-Black Deletion Examples