Analysis of Algorithms - 5

BLG 335E – Analysis of Algorithms I
Fall 2013, Recitation 5
11.12.2013
R.A. Atakan Aral
aralat@itu.edu.tr – Research Lab 1
R.A. Doğan Altan
daltan@itu.edu.tr – Research Lab 3

Question 1
• Insert the following sequence of numbers
into a 2-3-4 tree
– {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65, 60,
46, 55, 33, 68, 79, 48}

Solution 1
• 2-3-4 tree: Perfect balance by allowing 1, 2,
or 3 keys per node:
– 2-node: one key, two children.
– 3-node: two keys, three children.
– 4-node: three keys, four children.
• Every path from root to leaf has the same
length.

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}
53

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}
27 53

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}
27 53 75

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}  causes a split
53
7527

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}  causes a split
53
25 27 75

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}
70 75
53
25 27

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}
70 7525 27 41
53

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}  causes a split
27 53
70 7525 41

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}  causes a split
27 53
38 41 70 7525

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}
16 25
27 53
38 41 70 75

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}
16 25
27 53
59 70 7538 41

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}
16 25 36 38 41
27 53
59 70 75

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}  causes a split
16 25
27 53 70
36 38 41 59 75

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}  causes a split
16 25
27 53 70
73 7536 38 41 59

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}
16 25
27 53 70
73 7536 38 41 59 65

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}
16 25 59 60 65
27 53 70
73 7536 38 41

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}  causes a split
that propagates up to the root
53
27 38
16 25 73 7536
70
59 60 6541

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}  causes a split
that propagates up to the root
53
27 38
16 25 41 46 73 7536
70
59 60 65

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}  causes a split
53
27 38
16 25
60 70
41 46 73 756536 59

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}  causes a split
53
27 38
16 25
60 70
55 5941 46 73 756536

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}
53
27 38
33 3616 25
60 70
55 5941 46 73 7565

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}
53
27 38
33 3616 25
60 70
65 6855 5941 46 73 75

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}
53
27 38
33 3616 25
60 70
65 6855 59 73 75 7941 46

Solution 1 (Cont.)
• {53, 27, 75, 25, 70, 41, 38, 16, 59, 36, 73, 65,
60, 46, 55, 33, 68, 79, 48}
53
27 38
33 3616 25 41 46 48
60 70
65 6855 59 73 75 79

Question 2
• 2-3-4 trees are balanced and can be searched in
𝑂(𝑙𝑜𝑔𝑛), but they have different node structures.
• To get 2-3-4 tree advantages in a binary tree format,
we can represent it as a red-black tree.
• Convert the following 2-3-4 tree to a red-black tree
53
27 38
16 25 41 46 73 7536
70
59 60 65

Solution 2
• Properties of a red-black tree:
– the root is always black
– black condition: every path from the root to a
leaf node has the same number of black nodes
– red condition: every red node has a black
parent

Solution 2 (Cont.)
• 2-nodes: can be represented with a black node
• 4-nodes: center value becomes the parent (black)
and the others become children (red)
X Y Z
X
A B
X
A B
A B C D
X
Y
Z
A B C D

Solution 2 (Cont.)
• 3-nodes:
• Note:
1.Red-black trees are not unique
2.However, the corresponding 2-3-4 tree is unique
X Y
A B C
X
Y
A B
C
X
YA
B C
or

Solution 2 (Cont.)
• Top-down conversion algorithm (start at the root):
1. Apply red-black tree representation to each node
2. Repeat for next level…
53
27 38
16 25 41 46 73 7536
70
59 60 65

Solution 2 (Cont.)
53
27 38
16 25 41 46 73 7536
70
59 60 65

53
27
16 25 41 46 73 7536 59 60 65
7038
Solution 2 (Cont.)

53
27
7336
7038
25
16
46
41
7560
6559
Solution 2 (Cont.)

Question 3
• Insert the following sequence of numbers
into a red-black tree
– {2, 1, 4, 5, 9, 3, 6, 7}

Solution 3
 {2, 1, 4, 5, 9, 3, 6, 7}
2

 {2, 1, 4, 5, 9, 3, 6, 7}
2
1
Solution 3 (Cont.)

 {2, 1, 4, 5, 9, 3, 6, 7}
2
1 4
Solution 3 (Cont.)

Solution 3 (Cont.)
 {2, 1, 4, 5, 9, 3, 6, 7}  recoloring
2
1 4
5
2
1 4
5
2
1 4
5
case1 case0

Solution 3 (Cont.)
 {2, 1, 4, 5, 9, 3, 6, 7}  recoloring and rotation
2
1 4
5
9
2
1 4
5
9
2
1 5
94
case3
step1
case3
step2

Solution 3 (Cont.)
 {2, 1, 4, 5, 9, 3, 6, 7}  recoloring
2
1 5
94
3
2
1 5
94
3
case1

Solution 3 (Cont.)
 {2, 1, 4, 5, 9, 3, 6, 7}
2
1 5
94
3 6

Solution 3 (Cont.)
 {2, 1, 4, 5, 9, 3, 6, 7}  recoloring
2
1 5
94
3 6
7
2
1 5
94
3 6
7
case2
step1

Solution 3 (Cont.)
 {2, 1, 4, 5, 9, 3, 6, 7}  2 rotations
2
1 5
94
3 6
7
2
1 5
94
3 7
6
2
1 5
74
3 6 9
case2
step2
case2
step3

Question 4
• Delete 90, 80 and 70 from the following
red-black tree in the given order
65
50 80
90706010
62

Solution 4 (Cont.)
• Delete 90, 80 and 70
65
50 80
90706010
62
65
50 80
706010
62

Solution 4 (Cont.)
65
50 80
706010
62
65
50 80
706010
62
case2

Solution 4 (Cont.)
65
50 80
706010
62
65
50 70
6010
62
absorb black

Solution 4 (Cont.)
65
50 70
6010
62
65
50
6010
62

Solution 4 (Cont.)
65
50
6010
62
50
10 65
60
62
case1

Solution 4 (Cont.)
50
10 65
60
62
50
10 65
62
60
case4

Solution 4 (Cont.)
50
10 65
62
60
50
10 62
60 65
case3

Analysis of Algorithms - 5

Recommended

More Related Content

What's hot (11)

Viewers also liked (18)

Similar to Analysis of Algorithms - 5 (20)

More from AtakanAral (9)

Recently uploaded (20)

Analysis of Algorithms - 5