ADS2_AllSol

4 9 / / \ \ 10 7 5 6 / 11 3. AVL insert : rotation types used : RR, RL, LR 5 / \ 4 7 / / \ 3 6 8 4. 2-3 tree (a) 4 / \ 2 6,8 / \ / | \ 1 3 5 7 9 delete 3: 6 / \ 4 8 / \ / \ 1,2 5 7 9 (b) 2,4 / | \ 1 3 5,6 insert 7: 4 / \

4. 2-3 tree (a) 4 / \ 2 6 / \ / \ 1 3 5 7 Delete 4: - transform to leaf node deletion - merge in bottom-up 3,6 / | \ 1,2 5 7 (b) 3,6 / | \ 1,2 4,5 7,8 Insert 9: split in bottom-up 6 / \ 3 8 / \ / \ 1,2 4,5 7 9

COP 5536 / AD 711R Advanced Data Structures Exam 2 (Mar. 23, 2001) CLOSED BOOK 50 Minutes Note. All answers will be graded on correctness, efficiency, clarity, elegance and other normal criteria that determine quality. The points assigned to each question are provided in parentheses. 1. (a) (2) Insert the following elements into an empty min Fibonacci-heap and show the result: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 (b) (4) Perform DeleteMin operation on the constructed heap, clearly labeling ChildCut value. Show each step. (c) (4) Perform DecreaseKey operation to decrease 17 to 4 and draw the resulting tree. 2. (8) Recall that an Indexed Binary Search Tree ibst has the field leftSize . For any node, the value of its leftSize field is the number of nodes in its left subtree. Write a pseudo code Find-Kth (ibst, k) to locate the k th smallest identifier m in ibst . The run time of your pseudo code should be O( h ), where h is the height of ibst . Show that your algorithm runs in O( h ). Find-Kth (ibst: Tree, k:integer) { if ( ibst == null) error

5 4 3 2 6 /|\ / | \ 8 7 9 (b) after pass 1: 4 2 6 | | /|\ 5 3 8 7 9 after pass 2: 2 / | \ 4 3 6 | /|\ 5 8 7 9 (c) - remove 6 and merge its children - insert the merged tree into the list of min tree roots 2 / | \ 4 3 7 | / \ 5 8 9 3. a.Deletion of 4 8 / \ 5 12 / \ / \ 2 7 10 14 / \ / / \ / \ 1 3 6 9 11 13 15 b.Insertion of 16 5 / \

3 12 / \ / \ 2 4 8 14 / / \ / \ 1 7 10 13 15 / / \ \ 6 9 11 16 4. 24 , 40 / | \ 2 , 22 30 48 / | \ / \ / \ 1 5,11,19 23 29 31,32,36 41,42,43 50 29 / \ 2 , 22 32 , 40 , 48 / | \ / / \ \ 1 5,11,19 23 30 36 41,42,43 50 5. red-black tree (a) Join(S,12,B) i) follow the right-child pointer until rank(B) == rank(x), where rank(B) == 1, x is a node pointer of tree S. S: 3 B: 15 rank(B) == 1 / \\ // 2 9 13 / \

7 10 <-- x // \\ \\ 5 8 11 ii) combine subtree x, 12, and tree B 12 / \ 10 15 \\ // 11 13 iii) connect the combined tree to node 7 through red pointer. 3 / \\ 2 9 / \\ 7 12 //\\ / \ 5 8 10 15 \\ // 11 13 iv) perform RR rotation to remove consecutive red pointers. 9 // \\ 3 12 / \ / \ 2 7 10 15 //\\ \\ // 5 8 11 13 (b) Split(5,S,x,B) for tree S. i) find node 5 and copy node value to x. Since node 5 has left and right child, Init:: tree S is NULL(left subtree) and tree B is NULL (right subtree). ii) perform Join(B, 7, NULL).

B: 7 \\ 8 iii) Join(B, 9, right-subtree of node 9). B: 9 / \ 7 10 \\ \\ 8 11 iv) Join(left-subtree of node 3, 3, S). S: 2 \\ 3 So, the result of split operation: S: 2 x: 5 B: 9 \\ / \ 3 7 10 \\ \\ 8 11

1. F-heap (ChildCut: T(true), F(false)) (a) min 1 7 2 15 / \ | | | (T)3 5(T) 9(T) 13(T) 16(T) (b) min 2 / | \ (T)13 (F)15 3(F) | | \ (T)16 5(F) 7(F) | 9(T) 2. Find-kth(ibst:tree, k:integer) { if (ibst == nulll) error else if (ibst.leftSize == k-1) return (ibst) else if (ibst.leftSize < k-1) return (Find-kth(ibst.rightchild, k-ibstSize)) else return (Find-kth(ibst.leftchild,k)) } 3. AVL tree (balance factor 0 is not shown). (1) (a) ____10____ / \ __5__ __12__ / \ / \ 3 7 11 13 / \ / \ 1 4 6 9 (b) o insert 8 : LR rotation

____ 7 ____ (1) / \ __5__ __10__ / \ (1) / \ 3 6 9 12 / \ / / \ 1 4 8 11 13 o insert 2 : LL rotation ____ 7 ____ / \ __3__ __10__ (-1)/ \ (1) / \ 1 5 9 12 \ / \ / / \ 2 4 6 8 11 13 4. Original Tree (two version) 6 4,8 / \ / | \ 3 9 2 6 10 / \ / \ / \ / \ / \ 1,2 4,5 7,8 10,11 1 3 5 7 9 11 After first deletion: 6 8 / \ / \ 2 9 4,6 10 / \ / \ / | \ / \ 1 4,5 7,8 10,11 1,3 5 7 9 11 After second deletion: 6 6 / \ / \ 2 9 4 8 / \ / \ / \ / \

1 4,5 7,8 10 1,3 5 7 9,10 5. red-black tree (a) Join(S,10,B) i) follow the right-child pointer until rank(B) == rank(x), where rank(B) == 1, x is a node pointer of tree S. S: 3 B: 13 rank(B) == 1 / \\ \\ 1 7 14 / \ 5 9 <-- x // \\ \\ 4 6 10 ii) combine subtree x, 10, and tree B 12 / \ 9 13 \\ \\ 10 14 iii) connect the combined tree to node 5 through red pointer. 3 / \\ 1 7 / \\ 5 12 //\\ / \ 4 6 9 13 \\ \\ 10 14 iv) perform RR rotation to remove consecutive red pointers. 7 // \\ 3 12 / \ / \

1 5 9 13 //\\ \\ \\ 4 6 10 14 (b) Split(5,S,x,B) for tree S. i) find node 5 and copy node value to x. Since node 5 has no child, tree S is NULL (left subtree) and tree B is NULL (right subtree). ii) perform Join(S, 4, NULL). perform Join(B, 6, NULL). S: 4 B: 6 iii) Join(B, 7, right-subtree of node 7). B: 7 / \ 6 9 \\ 10 iv) Join(left-subtree of node 3, 3, S). S: 3 // \\ 1 4 So, the result of split operation: S: 3 x: 5 B: 7 // \\ / \ 1 4 6 9 \\ 10

Sample solution Final Exam, Fall 2002 1. a) After insert 75. a ( 30 50 ) / | \ b(10 15) c(35,40 45) d(55 60 70 75) After insert 65 ( 30 50 65 ) / | \ \ (10 15)(35 40 45) (55 60) e(70 75) b) We have the same assumption as in text that there is enough internal memory to hold all nodes accessed during an operation. Insert 75: 3 disk accesses (2 to read a and d, and 1 to write updated node d) Insert 65: 5 disk accesses (2 to read a and d, and 3 to write nodes d, e and a) c) delete 15. ( 35 50 ) / | \ (10 30) (40 45) (55 60 70) delete 55. ( 35 50 ) / | \ (10 30) (40 45) (60 70) delete 35. ( 50 ) / \ (10 30 40 45) (60 70)

2. Part 1: After RR Rotation. 5 / \ 4 f / \ 3 e / \ c d After LR Rotation 5 / \ 2 7 / \ / \ b 4 f g / \ 3 e / \ c d After RL Rotation. 5 / \ 1 8 / \ / \ a 2 7 h / \ / \ b 4 f g / \ 3 e / \ c d Part B: after searching for a key i., create a new node q, set q -> key to some value other than i to indicate that there is no record in a tree with key i, and then insert q into the search external node. (i.e., id ther search stoped where p->LeftChild = 0, insert q into p->LeftChild).

Because of splays, q will becaome the new root of a tree and it easa splict. 3. node: <label>:<bitnumber>:<key>. After inserting 001000: a:0:001000 / a After inserting 001010: a:0:001000 / b:5:001010 / \ a b After inserting 111110: a:0:001000 / c:1:111110 / \ b:5:001010 c / \ a b After inserting 001011: a:0:001000 / c:1:111110 / \ b:5:001010 c / \ a d:6:001011 / \ b d

After inserting 100000: a:0:001000 / c:1:111110 / \ b:5:001010 e:2:100000 / \ / \ a d:6:001011 e c / \ b d After inserting 110010: a:0:001000 / c:1:111110 / \ b:5:001010 e:2:100000 / \ / \ a d:6:001011 e f:3:110010 / \ / \ b d f c After deleting 0101: a:0:001000 / f:1:110010 / \ b:5:001010 e:2:100000 / \ / \ a d:6:001011 e f / \ b d 4. (10,12) [0,24) [0,24) (10,12) [0,24) (3,4) I (8,16) / I(3,4) /

====> [0,12) (8,16) ====> [0,12) (10,12) \ (8,16) [6,12) [0,24) (3,4) / \ I(23,6) [0,12) (10,12) (23,6) [12,24) ====> \ (8,16) [6,12) [0,24) (3,4) / \ I(13,18)[0,12) (10,12) (23,6) [12,24) ====> \ / (8,16) [6,12) (13,18) [12,18) [0,24) (3,4) / \ I(17,9) [0,12) (10,12) (23,6) [12,24) ====> \ / (8,16) [6,12) (17,9) [12,18) / (13,18) [12,15) 5. (a) (a) If the pixel [i,j] is to the NW,NE, SW, or SE of current partitioning line, go to NW, NE, SW, or SE child. repeat this until a leaf node is reached. This leaf node is the corresponding node to the pixel. You can initialize all the leaf nodes of the quadtree using the scheme in the question (a). This takes O(NlogN) time where N(n^2) is the number of pixels in the image. Then, all internal nodes can be initialized by just traversing in post-order using black, white, and gray colors which takes O(N). So, the total time complexity is O(NlogN). While traversing the tree, you can add the number of pixels in a node if the node stands for white. The number of pixels in the node can be easily computed using tree level (that is, the number of pixels in a node

is 4^l where l is tree level). Of course, if current node is gray, you'll need go down until white node. (b) find_points(kd_node node, int x, int y) if (node == NULL) return; if (node.x > X and node.y > Y) output node; if ( x.discriminator( node ) ) { if (node.x < X) find_points(node->right, x, y); if (node.x > X) { find_points(node->right, x, y); find_points(node->left, x, y); } } if ( y.discriminator( node ) ) { if (node.y < Y) find_points(node->right, x, y); if (node.y > Y) { find_points(node->right, x, y); find_points(node->left, x, y); } }

================================================= Exam01 Solution ================================================= 1. F-heap (ChildCut: T(true), F(false)) (a) min 3 6 2 1 20 / \ | | | \ (T)4 5(T) 7(T) 9(T) 11(T)12(T) | 13(T) (b) After deleteMin operation, we need to combine steps like below: min 2 3 / | \ / \ (T)9 (F)6 11(F) (T)4 5(T) | | \ (T)7 20(F) 12(F) | 13(T) 2. (a) 4 5 9 9 20 20 => | => | => / | => | => / | 4 5 8 5 9 12 9 | | / | / | 4 4 8 5 8 5 | | 4 4 20 20 20 => / / | => / / / | => / / / / | 3 12 9 14 3 12 9 15 14 3 12 9 / | /| /| 8 5 8 5 8 5 | | | 4 4 4

(b) 15 12 9 15 meld(15,9) 15 | | /| => / | ========> / / | 14 3 8 5 12 14 9 12 14 | | / | | 4 3 8 5 3 | 4 3. 11 / \ 7 20 / \ / \ 3 9 14 32 / = / \ / \ 1 12 17 27 37 / 25 Part a: delete 9. 11 / \ (2) 7 20 / / \ 3 14 32 / / \ / \ 1 12 17 27 37 / 25 R1 Rotation 11 (-2) / \ (0) 3 20 (-1) / \ / \ 1 7 14 32 (1) / \ / \ 12 17 27 37 / 25 L0 Rotation 20 (1) / \ 11 (0) 32 (1) / \ / \ 3 14 27 (1) 37 / \ / \ / 1 7 12 17 25

Part b: Insert 26 11 / \ 7 20 / \ / \ 3 9 14 32 / / \ / \ 1 12 17 27 37 / 25 \ 26 LR Rotation 11 / \ 7 20 / \ / \ 3 9 14 32 / / \ / \ 1 12 17 26 37 / \ 25 27 Insert 29 11 / \ 7 20 / \ / \ 3 9 14 32 (2) / / \ / \ 1 12 17 26 37 / \ 25 27 \ 29 LR Rotation: 11 (-1) / \ 7(1) 20 (-1) / \ / \ 3(1) 9 14(0) 27 (0) / / \ / \ 1 12 17 26 (1) 32 / / \ 25 29 37

4. (a) ( 4, 8) (4,8) / | \ Insert 13 / | \ / | \ ===> / | \ (1, 3) (6, 7) (10) (1,3) (6,7) (10,13) (4,8) (4,8) Insert 5 / | \ / | \ + 6 ===> / | \ ===> / | \ \ (1,3) (5)(6,7) (10,13) (1,3) (5) (10,13) 7 (6) / \ / \ (4,6,8) (4) (8) / | \ / \ / \ ===> / | \ ===> / \ / \ (1,3) (5) (7) (10,13) (1,3) (5) (7) (10,13) (b) (7) (5) / \ / \ / \ Delete 7 / \ (3) (12) ===> (3) (12) / \ / \ / \ / \ / \ / \ / \ / \ (1) (5) (9) (14) (1) ( ) (9) (14) (5) (5, 12) / \ / | \ / \ Delete 7 / | \ ===> ( ) (12) ===> (1,3) (9) (14) / / \ / / \ (1,3) (9) (14) Delete 14 (5) ===> / \ / \ (1,3) (9,12)

5. Red-Black Trees (a) 5 Insert 6 / \ ==== L 3 8 // 7 // 6 5 5 5 LLb / \ Insert 10 / \ RRr / \\ ===> 3 7 ===> 3 7 ===> 3 7 // \\ // \\ / \ 6 8 6 8 6 8 \\ \\ 10 10 5 5 5 Insert 1 / \\ Insert 2 / \\ LRb / \\ ===> 3 7 ===> 3 7 ===> 2 7 // / \ // / \ // \\ / \ 1 6 8 1 6 8 1 3 6 8 \\ \\ \\ \\ 10 2 10 10 (b) Step 1: Search 6 and copy it to x. Initialize S and B to NULL. (S=NULL, B=NULL) Step 2: S=NULL B=join(B, 7, 8) B: 8 // \\ 7 10 Step 3: S=(2,5,S) B= same as above S: 2 2 // \\ RRr / \ 1 3 ===> 1 3 \\ \\ 5 5

================================================= Exam02 Solution ================================================= 1. F-heap (ChildCut: T(true), F(false)) (a)The solution can be represented in more than one way. After deleteMin operation, we need to combine steps like below: 4 degree 1 4 | ===> / | degree 2 5(F) 5(F) 15(F) ======> | 22(T) min 3 7 / | \ / \ (T)11 (T)12 4(F) (T)8 9(T) | \ | 5(F) 15(F) 10(T) | 22(T) (b) min 3 7 2 / | \ / \ | (T)11 (F)12 4(T) (T)8 9(T) 22(T) | | 5(F) 10(T) 2. (a) 5 5 5 15 15 15 => | => / | => | => / | => / / | 3 1 3 5 7 5 8 7 5 / | / | / | 1 3 1 3 1 3

15 15 15 => / / / | ==> / / / / | ==> / / / / / | 12 8 7 5 2 12 8 7 5 2 12 4 8 7 5 / | /| / | 1 3 1 3 1 3 (b) two pass method 12 8 7 meld(12,8) 12 meld(12,7) 12 | | | ===== => / | ========> / / | 2 4 5 8 2 7 8 2 /| | | | 1 3 4 5 4 / | 1 3 3. a) 2, 1, 3, and 5 are inserted normally. Then a single rotation inserts 4, yielding 2 / \ 1 4 / \ 3 5 The insertion of 8 requires a single rotation at the root, resulting in 4 / \ 2 5 / \ \ 1 3 8 Next 7 is inserted, which requires a double rotation 4 / \ 2 7 / \ / \ 1 3 5 8 Finally, 6 is inserted yielding the result: 4 / \ 2 7 / \ / \ 1 3 5 8 \

6 part b: 30 / \ 20 55 / \ / \ 15 25 45 60 / \ / \ / == 5 17 23 27 43 / 21 30 / \ 20 55 / \ / 15 25 45 / \ / \ / 5 17 23 27 43 / 21 R1 Rotation 30 (2) / \ 20 (-1) 45 (0) / \ / \ 15 25 43 55 / \ / \ 5 17 23 27 / 21 R-1 Rotation 25 (0) / \ 20 (0) 30 (-1) / \ / \ 15 23 27 45 / \ / / \ 1 7 21 43 55

4. (a) The solution can be represented in more than one way. 25 / \ 21 42 // \ // \\ 3 24 29 60 / \ / \ / \ 1 13 27 36 45 55 // \\ // // \\ 4 19 34 44 50 (b) 24 / \ / \ ( 3 , 21 ) (29 , 42 , 60 ) / | \ / | | \ / | \ / | | \ 1 (4,13,19) 27 (34,36) (44,45,50) 650 24 / \ / \ ( 3 , 19 ) (29 , 42 , 60 ) / | \ / | | \ / | \ / | | \ 1 (4,13) 21 27 (34,36) (44,45,50) 650 5. Red-Black Trees (a) 5 5 5 / \ / \ / \

Rb1 2 15 2 15 2 15 ==> / \ // \ insert(12) / \ // \ RRb / \ // \ 1 3 8 18 ===> 1 3 8 18 =====> 1 3 8 18 / \ / \ / \ 6 9 6 9 6 10 \\ \\ // \\ 10 10 9 12 \\ 12 (b) Step 1: Search 8 and copy it to x. Initialize S and B to NULL. (S=NULL, B=NULL) Step 2: S= 6 B= 9 \\ 10 Step 3: S= 6 B=join(B, 15, 18) B: 15 / \ 9 18 \\ 10 Step 4: S= join(3, 5, S) B= same as above S: x = 8 B: 3 / \ / \\ 9 18 2 5 \\ // / \ 10 1 4 6

Fall 2003 Exam02_solution question 1. min | V 20 3 1 | / \ / / | 25 7 5 13 15 18 | / | | 9 14 26 17 | | 19 30 (a) delete (1) = min min | V 20 3 13 15 18 | / \ / \ | 25 7 5 14 26 17 | | | 9 19 30 joins two min F-heaps with same degree 2 and degree 1 3 15 18 / / | / | (F)13 7 5 (F)20 17 / | | | | 14 26 9 25 30 | 19 (b) DecreaseKey

3 15 18 14 19 / / | / | (T)13 7 5 (F)20 17 | | | | 26 9 25 30 (2) There was a typo in part(a). The balance factor of the root should be -1 instead of +1. I am very sorry for the problem. Thus, I provide sample solutions for the two versions. Remember that you need to identify imbalance type from the node whose balance factor becomes either +2 or -2 when a node is inserted. Version 1: The balance factor of the root is -1. (a) 5 / \ 3 10 / \ / \ 2 4 7 12 / \ / \ 6 9 11 13 (b) insert 8 (RL) 7(0) / \ 5(1) 10 / \ / \ 3 6 9(1) 12 / \ / / \ 2 4 8 11 13 insert 1 (LL) 7(0) / \ 3(0) 10 / \ / \ 2(1) 5 9(1) 12 / / \ / / \ 1 4 6 8 11 13

Version 2: The root is "10" and has balance factor +1. (a) 10 / \ 9 12 / \ / \ 4 6 11 13 / \ / \ 2 3 5 7 (b) insert 8 (LR) 10 / \ 5 12 / \ / \ 3 7 11 13 / \ / \ 2 4 6 9 7(0) / \ 5(1) 10 / \ / \ 3 6 9(1) 12 / \ / / \ 2 4 8 11 13 insert 1 (LL) 7(0) / \ 3(0) 10 / \ / \ 2(1) 5 9(1) 12 / / \ / / \ 1 4 6 8 11 13 (3) (a)

10 I(5) 10 LLb 8 I(1) 8 // ===> // ===> // \\ ===> // \\ 8 8 5 10 5 10 // // 5 1 LLr 8 I(3) 8 LRb 8 ===> / \ ===> / \ ===> / \ 5 10 5 10 3 10 // // // \\ 1 1 1 5 \\ 3 I(7) 8 RRr 8 ===> / \ ===> // \ 3 10 3 10 // \\ / \ 1 5 1 5 \\ \\ 7 7 (b) Step 1. Follow the left child pointers from the root of B to first node x whose rank equals rank(S) = 1. 6 <--- x // 5 Step 2. Combine S, 4, and subtree rooted at 6. 4 / \ 3 6 // // 2 5 Step 3. Combine the result of Step 2 to node "7" through a red pointer. 11 // \ 7 13 // \

4 9 / \ // \\ 3 6 8 10 // // 2 5 Step 4. Imbalance (LLb --> rotate) 7 // \\ 4 11 / \ / \ 3 6 9 13 // // // \\ 2 5 8 10

Exam02 solution. Spring 2003 1. (part a) (after DecreaseKey) min | V 1 15 19 2 13 / | \ | 14 7 9 (T) 17(T) | / 11 10 | 32 (part b) 14 7 9 15 19 2 13 | | | 11 10 17 | 32 2 7 9 15 14 | | | | | 13(F) 11 10 17 19(F) | 32 2 9 14 / | / | | 13(F) 7(F) 10 15 (F) 19(F) | | 11(T) 17 | 32(T) 2 14 / / | | 13(F) 7(F) 9(F) 19(F)

| / | 11(T) 10 15(F) | | 32(T) 17(T) 2) 35 / \ 20 45 (1) / \ / \ 14 30 40(-1) 50 (-1) / \ / \ / \ \ 12 13 26 34 37 43 55 / / == 24 41 Part a: delete 55. 35 / \ 20 45 (2) / \ / \ 14 30 40(-1) 50(0) / \ / \ / \ 12 13 26 25 37 43 / / 24 41 R-1 Rotation 35 (1) / \ 20 (-1) 43 (0) / \ / \ 14 30 40(0) 45(-1) / \ / \ / \ \ 12 13 26 34 37 41 50 / 24 Part b: Insert 21

35 (1) / \ 20 (-1) 45 (1) / \ / \ 14 30 40 50 / \ / \ / \ \ 12 13 26(2)34 37 43 55 / / 24 41 / 21 LL Rotation 35 (1) / \ 20 (-1) 45 (1) / \ / \ 14 30 40 50 / \ / \ / \ \ 12 13 24 34 37 43 55 / \ / 21 26 41 Insert 28 35 / \ 20 45 / \ / \ 14 30(2) 40 50 / \ / \ / \ \ 12 13 24 34 37 43 55 /\ / 21 26 41 \ 28 LR Rotation: 35

/ \ 20 45 / \ / \ 14 26(-1) 40 50 / \ / \ / \ \ 12 13 24 30 37 43 55 / / \ / 21 28 34 41 35 (0) / \ 20 (-1) 45 (1) / \ / \ 14(0) 26(0) 40(-1) 50(-1) / \ / \ / \ \ 12(0) 13(0) 24(1) 30(0) 37(0) 43(1) 55 / / \ / 21(0) 28(0) 34(0) 41 3. Two possibilities (a) 6 4,8 / \ / | \ 3 9 2 6 10 / \ / \ / \ / \ / \ 1,2 4,5 7,8 10,11 1 3 5 7 9 11 (b) after the first deletion 6 8 / \ / \ 2 9 4,6 10 / \ / \ / | \ / \ 1 4,5 7,8 10,11 1,3 5 7 9 11 after the second deletion 5 7

/ \ / \ 2 9 4 10 / \ / \ / \ / \ 1 4 7,8 10,11 1,3 5,6 9 11 4. (a) I(10) I(7) LLb I(2) 12 ===> 12 ===> 12 ===> 10 ===> 10 // // // \\ // \\ 10 10 7 12 7 12 // // 7 2 LLr 10 I(6) 10 LRb 10 ===> / \ ===> / \ ===> / \ 7 12 7 12 6 12 // // // \\ 2 2 2 7 \\ 6 I(9) 10 RRr 10 ===> / \ ===> // \ 6 12 6 12 // \\ / \ 2 7 2 7 \\ \\ 9 9 (b) D(9) 5 D(10) 5 ===> // \\ ===> // \\ 2 8 2 7 / \ / \ / \ / \ 1 3 6 10 1 3 6 8 \\ 7

(c) Step 1. S=null, B=( 7 ) Step 2. S=null, B=join(B, 8, 9) \\ 10 B= 8 RRr 8 // \\ ===> / \ 7 9 7 9 \\ \\ 10 10 Step 3. S=join(2,5,S), B=same as that of step 2. S= 2 / \ 1 3 \\ 5 Final S= 2 B = 8 / \ / \ 1 4 7 9 \\ \\ 5 10 The End.

Instructor: Dr. Sartaj Sahni Spring, 2004 Advanced Data Structures (COP 5536 /AD 711R) Exam 2 CLOSED BOOK 60 Minutes Name: NOTE: 1. For all problems, use only the algorithms discussed in class/text. 2. All answers will be graded on correctness, efficiency, clarity, elegance and other normal criteria that determine quality. 3. The points assigned to each question are provided in parentheses.

1. (12) For the following min Fibonacci heap. (The ChildCut of field shown in parentheses; ChildCut is undefined for the root.) min | V 1 13 / / \ 2(F) 4(T) 3(T) / | / | (T)6 5(F) 10(T) 5(T) | | (T)8 9(F) / | | (F)9 15(T) 11(T) | 18(T) Figure 1. Min Fibonacci heap (a) (6) For the min Fibonacci heap of figure 1, perform a DecreaseKey operation by changing 15 to 2. Draw the resulting min Fibonacci heap, clearly label ChildCut value. (b) (6) For the min Fibonacci heap of figure 1, perform a Delete the min element. Draw the resulting min Fibonacci heap, clearly label ChildCut value.

2. (11) For AV L trees, (a) (6) Start with an empty AVL tree, and perform insert operations using the following keys in the order: 6, 8, 7, 4, 5, and 3. Show each step. (b) (5) Delete key 9 from the following AVL tree. Show each step and specify imbalance type. 4 / \ 2 8 / \ / \ 1 3 6 9 / \ 5 7

3. (15) Start with an empty two - pass max pairing heap, (a) (5) Insert the following sequence of keys: 2, 5, 8, 4, 7, 12, 3, and 9 in this order. Draw the resulting max pairing heap. (b) (5) Perform a IncreaseKey(8,10) operation, which increase the 8 to 18, on the resulting max pairing heap of (a). Show the resulting max pairing heap. (c) (5) For the max pairing heap of figure 2 below, perform a RemoveMax operation using two - pass scheme and show each step. 15 / / / | \ \ \ 10 13 12 11 5 9 7 Figure 2. max pairing heap

4. (12) Use the bottom - up (2-pass) algorithms of red - black trees for this problem. Double lines indicate a red edge and single line a black edge. (a) (7) Insert keys 7, 6, 4, and 3 (in this order) into the following red-black tree. Show each step and specify rotation type/color flip if applied. 2 // \\ 1 5 (b) (5) Delete key 14 from the following red-black tree. Show each step and specify rebalancing type. 10 / \\ 8 14 // \\ / \ 7 9 12 15 // \\ 11 13

Exam02_solution Spring, 2004 question 1. DecreaseKey operation by changing 15 by 2 min | V 1 13 2 8 6 / / \ | | 2(T) 4(T) 3(T) 18(T) 9(F) | / | 5(F) 10(T) 5(T) | 9(F) | 11(T) DeleteMin operation. min | V 2 3 / | \ | (T)6 5(F) 4(F) 13(F) | / | (T)8 10(T) 5(T) / | | (F)9 15(T) 9(F) | | 18(T) 11(T) (2) (a) 6 7 7 7 \ RL / \ I(4) / \ I(5) / \

8 ===> 6 8 ===> 6 8 ===> 6 8 / / / 7 4 4 \ 5 7 7 5 LR / \ I(3) / \ LL / \ ===> 5 8 ===> 5 8 ===> 4 7 / \ / \ / / \ 4 6 4 6 3 6 8 / 3 (b) delete 9 4 / \ 2 8(2) <-- A / \ / 1 3 6(0) / \ 5 7 A is the nearest ancestor of the deleted node. (R0) 4 / \ 2 6 / \ / \ 1 3 5 8 / 7 3) (a) tree with smaller root becomes leftmost subtree. Insert 5 Insert 8 Insert 4 2 ==> 5 ==> 8 ==> 8 | | / \ 2 5 4 5 | | 2 2

Insert 7 Insert 12 Insert 3 ==> 8 ==> 12 ==> 12 / / | | / | 7 4 5 8 3 8 | / / | / / | 2 7 4 5 7 4 5 | | 2 2 Insert 9 =======> 12 / / | 9 3 8 / / | 7 4 5 | 2 (b) 12 18 meld two heaps 18 / | / / | ========> / / / | 9 3 7 4 5 12 7 4 5 | / | | 2 9 3 2 (c) two-pass meld after remove min pass 1: start subtrees left to right. 13 12 9 7 | | | 10 11 5 the number of subtrees was odd, meld remaining original subtree with newly generated subtree. 13 12 9 | | / | 10 11 7 5 Pass 2: start with rightmost subtrees of pass 1 12 13

/ | step2 / | 9 11 ===> 12 10 / | / | 7 5 9 11 / | 7 5 (4) (a) I(7) 2 RRr 2 I(6) 2 ===> // \\ ===> / \ ===> / \ 1 5 1 5 1 5 \\ \\ \\ 7 7 7 // 6 2 2 RLb / \ I(4) / \ ===> 1 6 ===> 1 6 // \\ // \\ 5 7 5 7 // 4 2 2 LLr / \\ I(3) / \\ ==> 1 6 ===> 1 6 / \ / \ 5 7 5 7 // // 4 4 // 3 2 LLb / \\

==> 1 6 / \ 4 7 // \\ 3 5 (b) delete 14 10 / \\ 8 15 // \\ / \ 7 9 12 y // \\ 11 13 Rb2 10 / \\ 8 13 // \\ / \ 7 9 12 15 // 11

Instructor: Dr. Sartaj Sahni Spring, 2004 Advanced Data Structures (COP 5536 /AD 711R) Exam 2 - Make-up CLOSED BOOK 60 Minutes Name: NOTE: 1. For all problems, use only the algorithms discussed in class/text. 2. All answers will be graded on correctness, efficiency, clarity, elegance and other normal criteria that determine quality. 3. The points assigned to each question are provided in parentheses.

1. (14) For the following min Fibonacci heap, assume that the ChildCut field of all node is TRUE (However, the ChildCut of a root node is undefined). min | V 20 3 1 | / \ / / \ 25 7 5 13 15 18 | / | | 9 14 26 17 | | 19 30 (a) (7) Delete the min element. Show each step and clearly label ChildCut values. (b) (7) Perform a DecreaseKey operation by changing 19 to 6 on the resulting Fibobacci heap of (a), clearly label ChildCut values (Draw the resulting Fibonacci heap.)

2. (12) For AVL trees, (a) (6) Construct an AVL tree with following keys: 2,3,4,5,6,7,9,10,11,12, and 13. The root node of the constructed AVL tree must have the key 5 and balance factor +1. All nodes other than the root node have the balance factor 0. (Note: Do not insert the keys in the given sequence.) (b) (6) Insert 8 and 1, in this order, into the AVL tree of Part (a). Show each result and clearly label balance factors and rotation types.

3. (10) Draw a 2-3 tree with 11 elements (keys from 1 to 11) and height 3, where all nodes at levels 2 and 3 are 2-nodes (the root is at level 1). Delete the element in the rightmost node at level 2 and draw the resulting 2-3 tree. From the resulting tree, delete the min element. Draw the new 2-3 tree.

4. (14) For red-black trees, use the bottom - up algorithm for this problem. (a) (7) Construct a red-black tree by inserting the keys in the following sequence into an initially empty red-black tree: 10, 8, 5, 1, 3, and 7 S: 3 B: 11 // // \ 2 7 13 / \ 6 9 // // \\ 5 8 10 Figure. Red-black trees (b) (7) For the red-black trees S and B shown above, perform Join ( S, 4 , B ) operation, showing each step. Double edge indicates a red pointer and single edge indicates a black pointer.

Spring 2004 make-up exam Exam02_solution question 1. min | V 20 3 1 | / \ / / | 25 7 5 13 15 18 | / | | 9 14 26 17 | | 19 30 (a) delete (1) = min min | V 20 3 13 15 18 | / \ / \ | 25 7 5 14 26 17 | | | 9 19 30 joins two min F-heaps with same degree 2 and degree 1 3 15 18 / / | / | (F)13 7 5 (F)20 17 / | | | | 14 26 9 25 30 | 19 (b) DecreaseKey

3 15 18 14 19 / / | / | (T)13 7 5 (F)20 17 | | | | 26 9 25 30 (2) (a) 10 / \ 9 12 / \ / \ 4 6 11 13 / \ / \ 2 3 5 7 (b) insert 8 (LR) 10 / \ 5 12 / \ / \ 3 7 11 13 / \ / \ 2 4 6 9 7(0) / \ 5(1) 10 / \ / \ 3 6 9(1) 12 / \ / / \ 2 4 8 11 13 insert 1 (LL) 7(0) / \ 3(0) 10 / \ / \ 2(1) 5 9(1) 12

/ / \ / / \ 1 4 6 8 11 13 3. (a) 2-3 tree with 11 keys 4, 8 / | \ 2 6 10 / \ / \ / \ 1 3 5 7 9 11 (b) delete "10" First, transform deletion from interior to deletion from a leaf. 4, 8 / | \ 2 6 9 / \ / \ / \ 1 3 5 7 ( ) 11 4, 8 / | \ ===> 2 6 ( ) / \ / \ | 1 3 5 7 9,11 4 / \ ===> 2 6,8 / \ / | \ 1 3 5 7 9,11 (c) delete "1" 4 / \ 2 6,8 / \ / | \ () 3 5 7 9,11

4 / \ ===> ( ) 6,8 | / | \ 2,3 5 7 9,11 6 / \ ===> 4 8 / \ / \ 2,3 5 7 9,11 (4) (a) 10 I(5) 10 LLb 8 I(1) 8 // ===> // ===> // \\ ===> // \\ 8 8 5 10 5 10 // // 5 1 LLr 8 I(3) 8 LRb 8 ===> / \ ===> / \ ===> / \ 5 10 5 10 3 10 // // // \\ 1 1 1 5 \\ 3 I(7) 8 RRr 8 ===> / \ ===> // \ 3 10 3 10 // \\ / \ 1 5 1 5 \\ \\ 7 7 (b) Step 1. Follow the left child pointers from the root of B to first node x whose rank equals rank(S) = 1.

6 <--- x // 5 Step 2. Combine S, 4, and subtree rooted at 6. 4 / \ 3 6 // // 2 5 Step 3. Combine the result of Step 2 to node "7" through a red pointer. 11 // \ 7 13 // \ 4 9 / \ // \\ 3 6 8 10 // // 2 5 Step 4. Imbalance (LLb --> rotate) 7 // \\ 4 11 / \ / \ 3 6 9 13 // // // \\ 2 5 8 10

Instructor: Dr. Sartaj Sahni 2005 Advanced Data Structures (COP 5536 /NTU AD 711R) Exam 2 CLOSED BOOK 70 Minutes Name: NOTE: All answers will be graded on correctness, efficiency, clarity, elegance and other normal criteria that determine quality. The points assigned to each question are provided in parentheses.

1. (a) (10) Insert the following elements into an empty min Fibonacci-heap and show the result: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 (b) (20) Perform DeleteMin operation on the constructed heap, clearly labelling ChildCut value. Show each step. (c) (20) Perform DecreaseKey operation to decrease 17 to 4 and draw the resulting tree.

2. (50) Recall that an Indexed Binary Search Tree ibst has the field leftSize . For any node, the value of its leftSize field is the number of nodes in its left subtree. Write a pesudo code FindK th ( ibst, k ) to locate the k th smallest identifier m in ibst . The run time of your pseudo code should be O ( h ), where h is the height of ibst .

3. (50) Recall that inserting a node into an AVL tree may require LL, LR, RL, or RR rotations. Draw AVL trees in which inserting a node requires an RL rotation. Remember that there are three cases for RL rotation. For each case, indicate a node to be inserted and draw the AVL tree following the insertion.

4. (a) (25) Insert keys 9, 8, 7, 2, 6, 1, 4 and 3 into an initially empty 2-3 tree in the given order. Show each step. (b) (25) Delete the minimum key of the root node, showing each step.

5. (50) Consider the two red-black trees S and B shown below (single line denotes black pointer and double line red pointer): S: 2 B: 12 / \\ \\ 1 5 13 / \ 4 6 // \\ 3 7 (a) (25) Perform Join(S, 10, B) operation, showing each step. (b) (25) For the red-black tree S above, perform Split(3) , showing each step.

COP 5536/AD 711R Advanced Data Structures Spring, 2001 Sample Solutions - Exam 2 1. (a) min | V -1-3-5-7-9-11-13-15-17-19- | | -------------------------- (b) DeleteMin min | V 3 19 / | \ (F)5 7(F) 11(F) | | \ (F)9 13(F) 15(F) | 17(F) (c) decrease 17 to 4 min | V 3 19 4 / | \ (F)5 7(F) 11(F) | | \ (F)9 13(F) 15(T) 2. treeNode FindKth (ibst, k) { if (ibst == null) return null; // not exist if (ibst->leftSize == k-1)

return (ibst) // found else if (ibst->leftSize > k-1) // search left subtree return ( FindKth(ibst->leftChild, k)) else return ( FindKth(ibst->rightChild, k-(ibst->leftSize+1))); } Analysis: Clearly, the algorithm traverses a path from the root to the node containing the k-th smallest key or NULL, error, if k is out of range. In either case, the length if the path is O(h), where h is the height of the tree. 3. RL rotations Numbers in parentheses represents balance factors. (1) case 1: A (-1) A (-2) C (0) \ ==> \ ==> / \ B (0) B (1) (0) A B (0) / C (0) Before Insert C After (2) case 2: A(-1) A(-2) B(0):h+2 / \ / \ / \ h:Al C(0) ==> h:Al C(1) ==> (0)A C(-1) / \ / \ / \ / \ (0)B Cr:h (-1)B Cr:h Al Bl'Br Cr / \ / \ h h h-1 h h-1:Bl Br:h-1 h:Bl' Br:h-1 Before Insert to Bl After (3) case 3: A(-1) A(-2) B(0):h+2 / \ / \ / \ h:Al C(0) ==> h:Al C(1) ==> (1)A C(0)

/ \ / \ / \ / \ (0)B Cr:h (-1)B Cr:h Al Bl Br' Cr / \ / \ h h-1 h h h-1:Bl Br:h-1 h-1:Bl Br':h Before Insert to Br After 4. (a) Insert 8 Insert 7 Insert 2 9 ==> 8,9 ==> 8 ==> 8 / \ / \ 7 9 2,7 9 Insert 6 6,8 Insert 1 6,8 Insert 4 6 ==> / | \ ==> / | \ ==> / \ 2 7 9 1,2 7 9 2 8 / \ / \ 1 4 7 9 Insert 3 6 ==> / \ 2 8 / \ / \ 1 3,4 7 9 (b) Delete 6 4 / \ 2 8 / \ / \ 1 3 7 9 5. (a) Numbers in parentheses represent ranks. i: Follow the right child pointer until rank(B) = rank(x), where rank(B) =1, x is a node pointer of tree S.

ii: Combine subtree x, 10, and B 10 / \ 6 12 \\ \\ 7 13 iii: Combine the result of ii to node 5 through a red pointer 2 / \\ 1 5 / \\ 4 10 // / \ 3 6 12 \\ \\ 7 13 iv: Perform a RR rotation 5 // \\ 2 10 / \ / \ 1 4 6 12 // \\ \\ 3 7 13 (b) i: Search node 3 ii: Perform Join(B', 4, null) B': 4 iii: Join (B', 5, right-subtree of node 5) B': 5 / \ 4 6

\\ 7 iv: Join (left-subtree of node 2, 2, S') S': 1 \\ 2 Result: S X B 1 3 5 \\ / \ 2 4 6 \\ 7

COP 5536/AD 711R Advanced Data Structures Spring, 2001 Sample Solutions - Exam 2 1. (a) min | V -1-3-5-7-9-11-13-15-17-19- | | -------------------------- (b) RemoveMin min | V 3 19 / | \ (F)5 7(F) 11(F) | | \ (F)9 13(F) 15(F) | 17(F) (c) decrease 17 to 4 min | V 3 19 4 / | \ | (F)5 7(F) 11(T) 17(F) | | (F)9 13(F) 2. After RemoveMax 10 9 13 12 17

| / / | | 5 1 6 8 3 | | 2 4 Two passing combine Step 1: 9 13 17 / / / | | | 10 1 6 8 12 3 | | | 5 2 4 Step 2: 9 17 / / / | / | 10 1 6 8 13 3 | | | | 5 2 4 12 Step 3: 17 / / | 9 13 3 / / / | | 10 1 6 8 12 | | | 5 2 4 (b) 3. RL rotations Numbers in parentheses represents balance factors. (1) case 1: A (-1) A (-2) C (0) \ ==> \ ==> / \

B (0) B (1) (0) A B (0) / C (0) Before Insert C After (2) case 2: A(-1) A(-2) B(0):h+2 / \ / \ / \ h:Al C(0) ==> h:Al C(1) ==> (0)A C(-1) / \ / \ / \ / \ (0)B Cr:h (-1)B Cr:h Al Bl'Br Cr / \ / \ h h h-1 h h-1:Bl Br:h-1 h:Bl' Br:h-1 Before Insert to Bl After (3) case 3: A(-1) A(-2) B(0):h+2 / \ / \ / \ h:Al C(0) ==> h:Al C(1) ==> (1)A C(0) / \ / \ / \ / \ (0)B Cr:h (-1)B Cr:h Al Bl Br' Cr / \ / \ h h-1 h h h-1:Bl Br:h-1 h-1:Bl Br':h Before Insert to Br After 4. (a) Insert 8 Insert 7 Insert 2 9 ==> 8,9 ==> 8 ==> 8 / \ / \ 7 9 2,7 9 Insert 6 6,8 Insert 1 6,8 Insert 4 6 ==> / | \ ==> / | \ ==> / \ 2 7 9 1,2 7 9 2 8 / \ / \ 1 4 7 9

Insert 3 6 ==> / \ 2 8 / \ / \ 1 3,4 7 9 (b) Delete 6 4 / \ 2 8 / \ / \ 1 3 7 9 5. (a) Lb1 rotation 2 / \\ 1 6 / \ 5 7 // 3 (b) Numbers in parentheses represent ranks. i: Follow the right child pointer until rank(B) = rank(x), where rank(B) =1, x is a node pointer of tree S. ii: Combine subtree x, 10, and B 10 / \ 6 12 \\ \\ 7 13 iii: Combine the result of ii to node 5 through a red pointer

2 / \\ 1 5 / \\ 4 10 // / \ 3 6 12 \\ \\ 7 13 iv: Perform a RR rotation 5 // \\ 2 10 / \ / \ 1 4 6 12 // \\ \\ 3 7 13 (c) i: Search node 3 ii: Perform Join(B', 4, null) B': 4 iii: Join (B', 5, right-subtree of node 5) B': 5 / \ 4 6 \\ 7 iv: Join (left-subtree of node 2, 2, S') S': 1 \\ 2

Result: S X B 1 3 5 \\ / \ 2 4 6 \\ 7