Computer Science Programming Homework
xyf123
CH13RB-Tree-P2-5-9-2019.pdf
5/9/2019
1
Insertion in RB Trees
• Insertion must preserve all red-black properties.
• Should an inserted node be colored Red? Black?
• Basic steps: ▪ Use Tree-Insert from BST (slightly modified) to
insert a node x into T.
o Procedure RB-Insert(x).
▪ Color the node x red.
▪ Fix the modified tree by re-coloring nodes and
performing rotation to preserve RB tree property.
o Procedure RB-Insert-Fixup.
Insertion RB-Insert(T, z)
1. y = T.nil
2. x = T.root
3. while x T.nil
4. y = x
5. if z.key < x.key
6. x = x.left
7. else x = x.right
8. z.p = y
9. if y == T.nil
10. T.root = z
11. else if z.key < y.key
12. y.left = z
13. else y.right = z
14. z.left = T.nil
15. z.right = T.nil
16. z.color = RED
17. RB-Insert-Fixup (T, z)
How does it differ from the Tree-
Insert procedure of BSTs?
Which of the RB properties might be
violated?
Fix the violations by calling RB-
Insert-Fixup.
Line 14 to 17.
Insertion – Fixup RB-Insert-Fixup (T, z)
1. while z.p.color == RED
2. if z.p == z.p.p.left
3. y = z.p.p.right // y now is z’s uncle
4. if y.color == RED
5. z.p.color = BLACK // Case 1
6. y.color = BLACK // Case 1
7. z.p.p.color = RED // Case 1
8. z = z.p.p // Case 1
9. else if z == z.p.right // y.color RED
10. z = z.p // Case 2
11. LEFT-ROTATE(T, z) // Case 2
12. z.p.color = BLACK // Case 3
13. z.p.p.color = RED // Case 3
14. RIGHT-ROTATE(T, z.p.p) // Case 3
15. else (if z.p == z.p.p.right)(same as 3-14
16. with “right” and “left” exchanged)
17. T.root.color = BLACK
Case 1 – uncle y is red
• z.p.p (z’s grandparent) must be black, since z and z.p are both red and there are no other violations of property 4.
• Make z.p and y black now z and z.p are not both red. But property 5 might now be violated.
• Make z.p.p red restores property 5. • The next iteration has z.p.p as the new z (i.e., z moves up 2 levels).
C
A D
B
z
y
C
A D
B
new z
z is a right child here.
Similar steps if z is a left child.
z.p
z.p.p
5/9/2019
2
Case 2 – y is black, z is a right child
• Left rotate around z.p, z.p and z switch roles now z is a left child, and both z and z.p are red.
• Takes us immediately to case 3.
C
A
B
z
y
C
B
A
z
y
z.p z.p
Case 3 – y is black, z is a left child
• Make z.p black and z.p.p red.
• Then right rotate on z.p.p. Ensures property 4 is maintained.
• No longer have 2 reds in a row.
• z.p is now black no more iterations.
B
A
C
B
A
y
z.p C
z
The operation of
RB-INSERT-FIXUP
5/9/2019
3
Flow Chart for Insertion in RB Tress Algorithm Analysis
• O(lg n) time to get through RB-Insert up to the call of RB-Insert-Fixup.
• Within RB-Insert-Fixup: ▪ Each iteration takes O(1) time.
▪ Each iteration but the last moves z up 2 levels.
▪ O(lg n) levels O(lg n) time.
▪ Thus, insertion in a red-black tree takes O(lg n) time.
▪ Note: there are at most 2 rotations overall.
o It never performs more than two rotations, since the while
loop terminates if case 2 or case 3 executed.
Example: RB-Tree Insertion
• Insert 8,6,9,11,4,5,12,7 to form a RBTree
8,6,9,11,4,5,12,7
88
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.12
5/9/2019
4
8,6,9,11,4,5,12,7
88
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.13
6
8,6,9,11,4,5,12,7
88
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.14
6 9
8,6,9,11,4,5,12,7
88
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.15
6 9
11
8,6,9,11,4,5,12,7
88
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.16
6 9
114
5/9/2019
5
8,6,9,11,4,5,12,7
• Rotate-left on 4 88
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.17
6 9
114
5
8,6,9,11,4,5,12,7
• Rotate-right on 6 88
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.18
6 9
11
4
5
8,6,9,11,4,5,12,7
88
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.19
6
9
114
5
8,6,9,11,4,5,12,7
88
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.20
6
9
114
5
12
5/9/2019
6
8,6,9,11,4,5,12,7
• Left-Rotate on 9 88
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.21
6
9
114
5
12
8,6,9,11,4,5,12,7
• Left-Rotate on 9 88
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.22
6
11
94
5
12
8,6,9,11,4,5,12,7
88
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.23
6
11
94
5
12
7
8,6,9,11,4,5,12,7
• Done 88
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.24
6
11
94
5
12
7
5/9/2019
7
RB Tree Visualization
• https://www.cs.usfca.edu/~galles/visualization/ RedBlack.html
• https://www.codelike.in/animation/red-black- tree
Pop Quiz 8
2. (10%) Show step by step: insert 6,4,7,9,2,3,10,5 to form
a RBTree (adding R to denote the red color and B to denote
the black color.)
6,4,7,9,2,3,10,5
86
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.27
6,4,7,9,2,3,10,5
86
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.28
4
5/9/2019
8
6,4,7,9,2,3,10,5
86
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.29
6 7
6,4,7,9,2,3,10,5
86
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.30
4 7
9
6,4,7,9,2,3,10,5
86
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.31
4 7
92
6,4,7,9,2,3,10,5
• Rotate-left on 2 86
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.32
4 7
92
3
5/9/2019
9
6,4,7,9,2,3,10,5
• Rotate-right on 4 86
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.33
4 7
9
2
3
6,4,7,9,2,3,10,5
86
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.34
4
7
92
3
6,4,7,9,2,3,10,5
86
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.35
4
7
92
3
10
6,4,7,9,2,3,10,5
• Left-Rotate on 7 86
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.36
4
7
92
3
10
5/9/2019
10
6,4,7,9,2,3,10,5
• Left-Rotate on 7 86
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.37
4
9
72
3
10
6,4,7,9,2,3,10,5
86
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.38
4
9
72
3
10
5
6,4,7,9,2,3,10,5
• Done 86
Red-black properties:
1. Every node is either red or black
2. The root is always black
3. Every leaf (NIL pointer) is black
4. If a node is red, both children are black
5. Every path from node to descendent leaf
contains the same number of black nodes L13.39
4
9
72
3
10
5
