This problem set does not involve any programming. You will hand in your written solutions as usual (don't forget the cover sheet).
Problem 1: Show the tree that results after inserting the following numbers into a Binary Search Tree (in the order they are given).
10, 9, 11, 7, 5, 2, 1, 12, 13, 15, 20
In the trees belows the "lower" branch is the left branch.
That is, flip the paper clockwise 90 degrees.
Insert 10
10
---------------------------
Insert 9
10
9
---------------------------
Insert 11
11
10
9
---------------------------
Insert 7
11
10
9
7
---------------------------
Insert 5
11
10
9
7
5
---------------------------
Insert 2
11
10
9
7
5
2
---------------------------
Insert 1
11
10
9
7
5
2
1
---------------------------
Insert 12
12
11
10
9
7
5
2
1
---------------------------
Insert 13
13
12
11
10
9
7
5
2
1
---------------------------
Insert 15
15
13
12
11
10
9
7
5
2
1
---------------------------
Insert 20
20
15
13
12
11
10
9
7
5
2
1
---------------------------
Problem 2: Show the tree that results after removing each one of the numbers below from the tree in Problem 1. Remove the numbers in the order that they appear.
10, 9, 11, 7
Remove 10
20
15
13
12
11
9
7
5
2
1
---------------------------
Remove 9
20
15
13
12
11
7
5
2
1
---------------------------
Remove 11
20
15
13
12
7
5
2
1
---------------------------
Remove 7
20
15
13
12
5
2
1
---------------------------
Problem 3: Show the tree that results after inseting each one of the numbers below into an AVL tree. For each insertion you must also specify:
10, 9, 11, 7, 5, 2, 20, 13, 21
Insert 10
10
------------------------------------
Insert 9
10
9
------------------------------------
Insert 11
11
10
9
------------------------------------
Insert 7
11
10
9
7
------------------------------------
Insert 5
11
10
9
7
5 oops 9 is unbalanced, do a single rotation (7-9)
11
10
9
7
5
now 7 is a child of 10
------------------------------------
Insert 2
11
10
9
7
5
2
oops, now 10 is unbalanced
do a single rotation (7-10)
11
10
9
7
5
2
------------------------------------
Insert 20
20
11
10
9
7
5
2
------------------------------------
Insert 25
25
20
11
10
9
7
5
2
oops, 11 is unbalanced, single rotation (20-11)
25
20
11
10
9
7
5
2
------------------------------------
Insert 13
25
20
13
11
10
9
7
5
2
10 is unbalanced, do a double rotation, 11-20-10
25
20
13
11
10
9
7
5
2
------------------------------------
Insert 21
25
21
20
13
11
10
9
7
5
2
7 is unbalanced, single rotation 11-7
25
21
20
13
11
10
9
7
5
2
Problem 4: Repeat Problem 3 for this list:
10, 12, 14, 16, 18, 20, 19, 17, 15, 13, 11, 9, 8, 7, 6
Insert 10
10
----------------------------------------
Insert 12
12
10
Insert 14
14
12
10
10 is unbalanced, single rotation, 12-10
14
12
10
Insert 16
16
14
12
10
Insert 18
18
16
14
12
10
14 is unbalanced, single rotation 16-14
18
16
14
12
10
Insert 20
20
18
16
14
12
10
12 is unbalanced, single rotation 16-12
20
18
16
14
12
10
Insert 19
20
19
18
16
14
12
10
18 is unbalanced, double rotation 19-20-18
20
19
18
16
14
12
10
Insert 17
20
19
18
17
16
14
12
10
Insert 15
20
19
18
17
16
15
14
12
10
Insert 13
20
19
18
17
16
15
14
13
12
10
Insert 11
20
19
18
17
16
15
14
13
12
11
10
Insert 9
20
19
18
17
16
15
14
13
12
11
10
9
Insert 8
20
19
18
17
16
15
14
13
12
11
10
9
8
Insert 7
20
19
18
17
16
15
14
13
12
11
10
9
8
7
9 is unbalanced, single rotation 8-9
20
19
18
17
16
15
14
13
12
11
10
9
8
7
Insert 6
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
10 is unbalanced, single rotation 8-10
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
Problem 5: Show the tree that results after inseting each one of the numbers below into a Red Black tree. Make sure your drawings show which are the red and which are the black nodes. For each insertion you must also specify which, if any, rotations where performed.
10, 9, 11, 7, 5, 2, 1, 12, 13, 15, 20
Insert 10
[B]10
---------------------------------------
Insert 09
[B]10
[R]09
---------------------------------------
Insert 11
[R]11
[B]10
[R]09
---------------------------------------
Insert 07
[B]11
[B]10
[B]09
[R]07
---------------------------------------
Insert 05
[B]11
[B]10
[B]09
[R]07
[R]05
- 5' parent is red, rotate 7-9
[B]11
[B]10
[R]09
[B]07
[R]05
---------------------------------------
Insert 02
[B]11
[B]10
[B]09
[R]07
[B]05
[R]02
---------------------------------------
Insert 01
[B]11
[B]10
[B]09
[R]07
[B]05
[R]02
[R]01
-two red nodes, rotate 2-5
[B]11
[B]10
[B]09
[R]07
[R]05
[B]02
[R]01
---------------------------------------
Insert 12
[R]12
[B]11
[B]10
[B]09
[R]07
[R]05
[B]02
[R]01
---------------------------------------
Insert 13
[R]13
[R]12
[B]11
[B]10
[B]09
[R]07
[R]05
[B]02
[R]01
two red nodes, rotate 12-11
[R]13
[B]12
[R]11
[B]10
[B]09
[R]07
[R]05
[B]02
[R]01
---------------------------------------
Insert 15
[R]15
[B]13
[R]12
[B]11
[B]10
[B]09
[R]07
[R]05
[B]02
[R]01
---------------------------------------
Insert 20
[R]20
[R]15
[B]13
[R]12
[B]11
[B]10
[B]09
[R]07
[R]05
[B]02
[R]01
two red nodes, rotate 15-13
[R]20
[B]15
[R]13
[R]12
[B]11
[B]10
[B]09
[R]07
[R]05
[B]02
[R]01
---------------------------------------
Problem 6: Repeat Problem 5 for this list:
10, 9, 8, 7, 6, 3, 4, 1, 2, 15, 14, 13, 12, 11
Insert 10
[B]10
---------------------------------------
Insert 09
[B]10
[R]09
---------------------------------------
Insert 08
[R]10
[B]09
[R]08
---------------------------------------
Insert 07
[B]10
[B]09
[B]08
[R]07
---------------------------------------
Insert 06
[B]10
[B]09
[B]08
[R]07
[R]06
two reds, rotate 7-8
[B]10
[B]09
[R]08
[B]07
[R]06
---------------------------------------
Insert 03
[B]10
[B]09
[B]08
[R]07
[B]06
[R]03
---------------------------------------
Insert 04
[B]10
[B]09
[B]08
[R]07
[B]06
[R]04
[R]03
two reds, double rotation 4-6
[B]10
[B]09
[B]08
[R]07
[R]06
[B]04
[R]03
---------------------------------------
Insert 01
[B]10
[R]09
[B]08
[B]07
[B]06
[R]04
[B]03
[R]01
---------------------------------------
Insert 02
[B]10
[R]09
[B]08
[B]07
[B]06
[R]04
[B]03
[R]02
[R]01
two reds, double rotation, 2-3
[B]10
[R]09
[B]08
[B]07
[B]06
[R]04
[R]03
[B]02
[R]01
---------------------------------------
Insert 15
[R]15
[B]10
[R]09
[B]08
[B]07
[B]06
[R]04
[R]03
[B]02
[R]01
---------------------------------------
Insert 14
[R]15
[R]14
[B]10
[R]09
[B]08
[B]07
[B]06
[R]04
[R]03
[B]02
[R]01
two reds, double rotation
[R]15
[B]14
[R]10
[R]09
[B]08
[B]07
[B]06
[R]04
[R]03
[B]02
[R]01
---------------------------------------
Insert 13
[B]15
[R]14
[R]13
[B]10
[B]09
[B]08
[B]07
[B]06
[B]04
[R]03
[B]02
[R]01
---------------------------------------
Insert 12
[B]15
[R]14
[R]13
[R]12
[B]10
[B]09
[B]08
[B]07
[B]06
[B]04
[R]03
[B]02
[R]01
two reds, double rotation 12-10
[B]15
[R]14
[R]13
[B]12
[R]10
[B]09
[B]08
[B]07
[B]06
[B]04
[R]03
[B]02
[R]01
---------------------------------------
Insert 11
[B]15
[R]14
[B]13
[B]12
[R]11
[B]10
[R]09
[B]08
[B]07
[B]06
[B]04
[R]03
[B]02
[R]01
---------------------------------------
Problem 7: Show the tree that results after inseting
each one of the numbers below into an AA tree. Make sure
you show the level of each node, as well as each and every one
of the skew and split transformations, identifying
them as such.
10, 9, 11, 7, 5, 2, 1, 12, 13, 15, 20
Insert 10
[1]10
Insert 9
[1]10
[1]9
skew
[1]10
[1]9
Insert 11
[1]11
[1]10
[1]9
split
[1]11
[2]10
[1]9
Insert 7
[1]11
[2]10
[1]9
[1]7
skew
[1]11
[2]10
[1]9
[1]7
Insert 5
[1]11
[2]10
[1]9
[1]7
[1]5
skew
[1]11
[2]10
[1]9
[1]7
[1]5
split
[1]11
[2]10
[1]9
[2]7
[1]5
skew
[1]11
[2]10
[1]9
[2]7
[1]5
Insert 2
[1]11
[2]10
[1]9
[2]7
[1]5
[1]2
skew
[1]11
[2]10
[1]9
[2]7
[1]5
[1]2
Insert 1
[1]11
[2]10
[1]9
[2]7
[1]5
[1]2
[1]1
skew
[1]11
[2]10
[1]9
[2]7
[1]5
[1]2
[1]1
split
[1]11
[2]10
[1]9
[2]7
[1]5
[2]2
[1]1
skew
[1]11
[2]10
[1]9
[2]7
[1]2
[1]1
split
[1]11
[2]10
[1]9
[3]7
[1]5
[2]2
[1]1
Problem 8: Repeat Problem 7 for this list:
10, 9, 8, 7, 6, 3, 4, 1, 2, 15, 14, 13, 12, 11
Ok, its taking way too long to type these in. The answer to this
problem is outside my door.