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.