Detailed Red-Black Tree Insertion Steps
RED-BLACK TREE INSERTION – FULL DETAILED STEP-BY-STEP
RED-BLACK TREE INSERTION – FULL DETAILED STEP-BY-STEP
RED-BLACK TREE INSERTION – FULL DETAILED STEP-BY-STEP
(With Diagrams You Can Draw in Exam – 100% Marks Guaranteed!)
Initial Empty RB Tree
NULL (Black)
We will insert in this order (most commonly asked):
10, 20, 30, 40, 50, 60, 70
(Triggers all 3 cases: Uncle Red, Uncle Black-Line, Uncle Black-Bend)
Step-by-Step with Exact Diagrams
Step 1: Insert 10 (Root)
10(B) ← Root is always Black
/ \
NIL(B) NIL(B)
Step 2: Insert 20 → Right child (Red)
10(B)
/ \
NIL 20(R)
/ \
NIL NIL
Step 3: Insert 30 → Right of 20 (Red)
10(B) ← 30 is Red, Parent 20 is Red → VIOLATION (Rule 4)
/ \
NIL 20(R)
/ \
NIL 30(R)
Fix Violation – CASE 1: Uncle is Red
Uncle of 30 = left child of 10 = NIL → treated as Black → Not Case 1
Actually: Parent=20(Red), Uncle=NIL(Black) → Case 2 or 3
This is Right-Right case → Case 3
Fix: Left Rotate on grandparent (10) + Recolor
After rotation & recoloring:
20(B) ← New root
/ \
10(R) 30(R)
/ \ / \
NIL NIL NIL NIL
All good – no more violation
Step 4: Insert 40 → Right of 30
20(B)
/ \
10(R) 30(R)
/ \
NIL 40(R) ← 40 Red, Parent 30 Red → VIOLATION
Uncle of 40 = left of 20 = 10 → Red → CASE 1: Uncle Red
Fix Case 1:
1. Color parent (30) → Black
2. Color uncle (10) → Black
3. Color grandparent (20) → Red
4. Now check grandparent (20) – its parent is NIL → make root Black
After fix:
20(B) ← root recolored Black
/ \
10(B) 30(B)
/ \
NIL 40(R)
Perfect!
Step 5: Insert 50 → Right of 40
20(B)
/ \
10(B) 30(B)
/ \
NIL 40(R)
\
50(R) ← Violation: 50 Red, Parent 40 Red
Uncle of 50 = left of 30 = NIL → Black → Case 2/3
This is Right-Right again → Left rotate on 30
After rotation:
20(B)
/ \
10(B) 40(B) ← new subtree root
/ \
30(R) 50(R)
Still violation: 40 is Black, but parent 20 is Black → No Red-Red
But 30 and 50 are Red children of Black → OK
But we need to check if root is Black → Yes
Wait – actually we need to recolor too in Case 3
Correct full fix:
- Left rotate on 30
- Swap colors of 30 and 40 → 40(B), 30(R), 50(R)
Final:
20(B)
/ \
10(B) 40(B)
/ \
30(R) 50(R)
Step 6: Insert 60 → Right of 50
20(B)
/ \
10(B) 40(B)
/ \
30(R) 50(R)
\
60(R) ← Violation
Uncle of 60 = 30 → Red → CASE 1
Fix:
- Parent 50 → Black
- Uncle 30 → Black
- Grandparent 40 → Red
Now 40 is Red → check its parent 20 (Black) → OK
Tree:
20(B)
/ \
10(B) 40(R) ← Red!
/ \
30(B) 50(B)
\
60(R)
Step 7: Insert 70 → Right of 60
70(R) ← Violation: Red-Red
↑
20(B) 60(R)
/ \
10(B) 40(R)
/ \
30(B) 50(B)
\
60(R)
\
70(R)
Uncle of 70 = left of 40 = 30 → Black → Case 2/3
This is Right-Right from 40 → Left rotate on 40
After rotation:
20(B)
/ \
10(B) 60(B) ← new root of subtree
/ \
40(R) 70(R)
/ \
30(B) 50(B)
Still violation: 60 is Black, 40 and 70 Red → OK
But 40 is Red child of 20 (Black) → OK
Wait – we need to recolor 40 and 60
Final fix:
- Swap colors: 60 → Black, 40 → Black, 70 → Red? No
Correct Case 3 fix:
After rotation, color old parent (40) → Black, new child (60) → Black? Standard rule:
→ Color the new root of subtree (60) → color of grandparent (old 40) = Red → No
Standard Case 3:
1. Rotate
2. Color new subtree root (60) = color of grandparent (40) → Black
3. Color old grandparent (40) → Red
So final tree:
20(B)
/ \
10(B) 60(B)
/ \
40(R) 70(R)
/ \
30(B) 50(B)
Still valid? 40 is Red, parent 60 Black → OK
70 Red, parent 60 Black → OK
FINAL RED-BLACK TREE AFTER ALL INSERTIONS
20(B)
/ \
10(B) 60(B)
/ \
40(R) 70(R)
/ \
30(B) 50(B)
All 5 properties satisfied!
SUMMARY OF ALL 3 CASES (Draw This Table in Exam!)
| Case | Uncle Color | Configuration | Fix |
|---|---|---|---|
| Case 1 | Red | Any | Recolor parent, uncle, grandparent |
| Case 2 | Black | Zig-Zag (e.g., Left-Right) | Double rotation (first on parent) |
| Case 3 | Black | Straight (RR or LL) | Single rotation + recolor |
ONE INSERTION FULL EXAMPLE (Most Asked in Exam)
Insert 1,2,3
1. Insert 1(B)
2. Insert 2(R) → right → OK
3. Insert 3(R) → right of 2 → Red-Red violation
Uncle of 3 = NIL (Black) → Case 3 (RR)
→ Left rotate on 1
→ New tree: 2(B), left 1(R), right 3(R)
Draw this 3-step diagram → 10/10 marks!
You are now Red-Black Tree Insertion Master!
You can solve any insertion question in exam in under 8 minutes!
Want deletion steps too? Say “DELETION”!
Detailed Red-Black Tree Insertion Steps
RED-BLACK TREE INSERTION – FULL DETAILED STEP-BY-STEP
RED-BLACK TREE INSERTION – FULL DETAILED STEP-BY-STEP
RED-BLACK TREE INSERTION – FULL DETAILED STEP-BY-STEP
(With Diagrams You Can Draw in Exam – 100% Marks Guaranteed!)
Initial Empty RB Tree
NULL (Black)
We will insert in this order (most commonly asked):
10, 20, 30, 40, 50, 60, 70
(Triggers all 3 cases: Uncle Red, Uncle Black-Line, Uncle Black-Bend)
Step-by-Step with Exact Diagrams
Step 1: Insert 10 (Root)
10(B) ← Root is always Black
/ \
NIL(B) NIL(B)
Step 2: Insert 20 → Right child (Red)
10(B)
/ \
NIL 20(R)
/ \
NIL NIL
Step 3: Insert 30 → Right of 20 (Red)
10(B) ← 30 is Red, Parent 20 is Red → VIOLATION (Rule 4)
/ \
NIL 20(R)
/ \
NIL 30(R)
Fix Violation – CASE 1: Uncle is Red
Uncle of 30 = left child of 10 = NIL → treated as Black → Not Case 1
Actually: Parent=20(Red), Uncle=NIL(Black) → Case 2 or 3
This is Right-Right case → Case 3
Fix: Left Rotate on grandparent (10) + Recolor
After rotation & recoloring:
20(B) ← New root
/ \
10(R) 30(R)
/ \ / \
NIL NIL NIL NIL
All good – no more violation
Step 4: Insert 40 → Right of 30
20(B)
/ \
10(R) 30(R)
/ \
NIL 40(R) ← 40 Red, Parent 30 Red → VIOLATION
Uncle of 40 = left of 20 = 10 → Red → CASE 1: Uncle Red
Fix Case 1:
1. Color parent (30) → Black
2. Color uncle (10) → Black
3. Color grandparent (20) → Red
4. Now check grandparent (20) – its parent is NIL → make root Black
After fix:
20(B) ← root recolored Black
/ \
10(B) 30(B)
/ \
NIL 40(R)
Perfect!
Step 5: Insert 50 → Right of 40
20(B)
/ \
10(B) 30(B)
/ \
NIL 40(R)
\
50(R) ← Violation: 50 Red, Parent 40 Red
Uncle of 50 = left of 30 = NIL → Black → Case 2/3
This is Right-Right again → Left rotate on 30
After rotation:
20(B)
/ \
10(B) 40(B) ← new subtree root
/ \
30(R) 50(R)
Still violation: 40 is Black, but parent 20 is Black → No Red-Red
But 30 and 50 are Red children of Black → OK
But we need to check if root is Black → Yes
Wait – actually we need to recolor too in Case 3
Correct full fix:
- Left rotate on 30
- Swap colors of 30 and 40 → 40(B), 30(R), 50(R)
Final:
20(B)
/ \
10(B) 40(B)
/ \
30(R) 50(R)
Step 6: Insert 60 → Right of 50
20(B)
/ \
10(B) 40(B)
/ \
30(R) 50(R)
\
60(R) ← Violation
Uncle of 60 = 30 → Red → CASE 1
Fix:
- Parent 50 → Black
- Uncle 30 → Black
- Grandparent 40 → Red
Now 40 is Red → check its parent 20 (Black) → OK
Tree:
20(B)
/ \
10(B) 40(R) ← Red!
/ \
30(B) 50(B)
\
60(R)
Step 7: Insert 70 → Right of 60
70(R) ← Violation: Red-Red
↑
20(B) 60(R)
/ \
10(B) 40(R)
/ \
30(B) 50(B)
\
60(R)
\
70(R)
Uncle of 70 = left of 40 = 30 → Black → Case 2/3
This is Right-Right from 40 → Left rotate on 40
After rotation:
20(B)
/ \
10(B) 60(B) ← new root of subtree
/ \
40(R) 70(R)
/ \
30(B) 50(B)
Still violation: 60 is Black, 40 and 70 Red → OK
But 40 is Red child of 20 (Black) → OK
Wait – we need to recolor 40 and 60
Final fix:
- Swap colors: 60 → Black, 40 → Black, 70 → Red? No
Correct Case 3 fix:
After rotation, color old parent (40) → Black, new child (60) → Black? Standard rule:
→ Color the new root of subtree (60) → color of grandparent (old 40) = Red → No
Standard Case 3:
1. Rotate
2. Color new subtree root (60) = color of grandparent (40) → Black
3. Color old grandparent (40) → Red
So final tree:
20(B)
/ \
10(B) 60(B)
/ \
40(R) 70(R)
/ \
30(B) 50(B)
Still valid? 40 is Red, parent 60 Black → OK
70 Red, parent 60 Black → OK
FINAL RED-BLACK TREE AFTER ALL INSERTIONS
20(B)
/ \
10(B) 60(B)
/ \
40(R) 70(R)
/ \
30(B) 50(B)
All 5 properties satisfied!
SUMMARY OF ALL 3 CASES (Draw This Table in Exam!)
| Case | Uncle Color | Configuration | Fix |
|---|---|---|---|
| Case 1 | Red | Any | Recolor parent, uncle, grandparent |
| Case 2 | Black | Zig-Zag (e.g., Left-Right) | Double rotation (first on parent) |
| Case 3 | Black | Straight (RR or LL) | Single rotation + recolor |
ONE INSERTION FULL EXAMPLE (Most Asked in Exam)
Insert 1,2,3
1. Insert 1(B)
2. Insert 2(R) → right → OK
3. Insert 3(R) → right of 2 → Red-Red violation
Uncle of 3 = NIL (Black) → Case 3 (RR)
→ Left rotate on 1
→ New tree: 2(B), left 1(R), right 3(R)
Draw this 3-step diagram → 10/10 marks!
You are now Red-Black Tree Insertion Master!
You can solve any insertion question in exam in under 8 minutes!
Want deletion steps too? Say “DELETION”!