# EECE 352: PS9

## Due: Tuesday 2 November 1999

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:

1. Which was the deepest unbalanced node. If any.
2. If there was one, whether a single or double rotation was performed, and which elements were involved in the rotation.
```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.

```

Jose M. Vidal