Red-Black Tree Deletion – Complete Examples with Diagrams & Step-by-Step Fixes
Red-Black Tree Deletion – Complete Examples with Diagrams & Step-by-Step Fixes
Red-Black Tree Deletion – Complete Examples with Diagrams & Step-by-Step Fixes
Red-Black Tree Deletion – Complete Examples with Diagrams & Step-by-Step Fixes
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
- Delete node as in BST (3 cases: 0, 1, or 2 children)
- If deleted node was BLACK → Black Height violation
- 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
- Delete 30 from Example 3 → Show all steps
- Delete 20 (BLACK leaf) → Use Case 2
- Delete root (BLACK) → How to fix?
- Insert 1,2,3,4,5 → Delete 3 → Trace
- 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
Red-Black Tree Deletion – Complete Examples with Diagrams & Step-by-Step Fixes
Red-Black Tree Deletion – Complete Examples with Diagrams & Step-by-Step Fixes
Red-Black Tree Deletion – Complete Examples with Diagrams & Step-by-Step Fixes
Red-Black Tree Deletion – Complete Examples with Diagrams & Step-by-Step Fixes
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
- Delete node as in BST (3 cases: 0, 1, or 2 children)
- If deleted node was BLACK → Black Height violation
- 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
- Delete 30 from Example 3 → Show all steps
- Delete 20 (BLACK leaf) → Use Case 2
- Delete root (BLACK) → How to fix?
- Insert 1,2,3,4,5 → Delete 3 → Trace
- 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