Red-Black Tree Insertion and Deletion
Algorithm for Insertion in a Red-Black Tree
Red-Black Tree Insertion Algorithm
Let x be the newly inserted node. Follow these steps to maintain Red-Black Tree properties:
Step 1: Standard BST Insertion
- Insert x using the standard Binary Search Tree (BST) insertion method.
- Assign the color RED to the newly inserted node x.
Step 2: Handle Violations
If x is the root, change its color to BLACK (increasing the Black height by 1).
Otherwise, if x’s parent is RED, proceed as follows:
Case (a): x’s Uncle is RED
- Set the color of x’s parent (p) and x’s uncle (u) to BLACK.
- Set the color of x’s grandparent (g) to RED.
- Update x = g and repeat Step 2 for the new x.
Case (b): x’s Uncle is BLACK
There are four possible cases based on the structure of x, x’s parent (p), and x’s grandparent (g):
- Left-Left (LL) Case:
- p is the left child of g, and x is the left child of p.
- Solution: Perform a Right Rotation on g.
- Swap the colors of p and g.
- Left-Right (LR) Case:
- p is the left child of g, and x is the right child of p.
- Solution: Perform a Left Rotation on p to convert it into LL Case, then apply Right Rotation on g.
- Swap the colors of p and g.
- Right-Right (RR) Case:
- p is the right child of g, and x is the right child of p.
- Solution: Perform a Left Rotation on g.
- Swap the colors of p and g.
- Right-Left (RL) Case:
- p is the right child of g, and x is the left child of p.
- Solution: Perform a Right Rotation on p to convert it into RR Case, then apply Left Rotation on g.
- Swap the colors of p and g.
Example of Red-Black Tree Insertion
Let’s insert the following sequence of elements into an initially empty Red-Black Tree:
50, 30, 70, 20, 40, 60, 80, 10
Step-by-Step Insertion with Fixes
1. Insert 50
- Since the tree is empty, insert 50 and color it RED.
- As it is the root, change its color to BLACK.
2. Insert 30
- Insert 30 as the left child of 50 and color it RED.
- No violations, as the parent (50) is BLACK
(50B)
/
(30R)
3. Insert 70
- Insert 70 as the right child of 50, color it RED.
- No violations, as the parent (50) is BLACK.
4. Insert 20
- Insert 20 as the left child of 30, color it RED.
- No violations, as parent (30) is RED, but uncle (70) is also RED (Case a).
- Fix (Case a: x’s Uncle is RED):
- Change 30 and 70 to BLACK.
- Change 50 to RED.
- Since 50 is the root, change it back to BLACK.
5. Insert 40
- Insert 40 as the right child of 30, color it RED.
- No violations, as the parent (30) is BLACK.
(50B)
/ \
(30B) (70B)
/ \
(20R) (40R)
6. Insert 60
- Insert 60 as the left child of 70, color it RED.
- No violations, as parent (70) is BLACK.
(50B)
/ \
(30B) (70B)
/ \ /
(20R) (40R) (60R)
7. Insert 80
- Insert 80 as the right child of 70, color it RED.
- No violations, as parent (70) is BLACK.
8. Insert 10
- Insert 10 as the left child of 20.
- Color 10 as RED.
- Observe the violation:
- 20 (parent) is RED.
- 40 (uncle) is also RED.
This is Case a: Uncle is RED.
Fix for Case a: Uncle is RED
- Change the color of 20 (parent) and 40 (uncle) to BLACK.
- Change the color of 30 (grandparent) to RED.
- Now, check for further violations:
- 30‘s parent is 50, which is BLACK, so no further violation occurs.
50 (BLACK)
/ \
30 (R) 70 (B)
/ \ / \
20 (B) 40(B) 60 (R) 80(R)
/
10 (R)
