Review Problems P1. Starting with an empty AVL tree, show the state after each of the following sequences of operations. [You may show the state after each individual operation, but be sure to label each state shown with the operation(s) that lead to it.] a) insert the letters B, E, A, G, D, and J in that order, one at a time; b) insert the letters F, K, H, and I in that order, one at a time; c) insert the letters C and L in that order, one at a time, and then delete the letter C; d) starting with the tree from Part (b), insert the letters C and L in that order, one at a time, and then delete the letter A; e) starting with the tree from Part (b), insert the letters C and L in that order, one at a time, and the delete the letter H. Hint: Nothing interesting happens until the last operation in a sequence. P2. Starting with an empty 2-3 tree where keys are stored in every node (rather than just in the leaves), show the state after each of the following sequences of operations. [You may show the state after each individual operation, but be sure to label each state shown with the operation(s) that lead to it.] a) insert the letters B, G, and F in that order, one at a time; b) insert the letters A, H, and E in that order, one at a time; c) insert the letters C and D in that order, one at a time; d) delete the letter E; e) delete the letter H. P3. Starting with an empty 2-3-4 tree where keys are stored in every node (rather than just in the leaves), show the state after each of the following sequences of operations. [You may show the state after each individual operation, but be sure to label each state shown with the operation(s) that lead to it.] a) insert the letters B, E, H, and J, in that order, one at a time; b) insert the letters I and L, in that order, one at a time; c) insert the letters A, C, F, G, K, and D, in that order, one at a time; d) delete the letters A and B, in that order, one at a time. Note: Keys are stored in all nodes, not just in the leaves; and you may not split or combine nodes during the downward pass. P4. Show the state of the min heap (either using the sequential representation or as a binary min tree) after each of the following sets of operations. [You may show the state after each individual operation, but be sure to label each state shown with the operation(s) that lead to it.] a) Starting with an empty min heap, insert the nine letters in the word COMPUTING in the order they appear in the word. b) Starting with the heap constructed in part (a), delete the smallest letter twice. c) Starting with the letters in COMPUTING in the first nine slots of the sequential representation of a heap, use the linear-time heapify algorithm to create a heap. P5. Let T be a nonempty AVL tree in which each of the N unique keys is an integer. Describe an O(log(N)) algorithm for finding the integer in T that is closest to the integer D (or any such integer in T if there are two or more). Explain why your algorithm runs in O(log(N)) time. P6. [Annotated Trees] Benno Bitwiddle, the chief programmer at elaY Software, is adding a new function to his BST ADT: Qth(T,Q) returns the Q-th largest key in the tree T. However, Benno does not know how to make Qth() run in time O(height(T)) like insertion and deletion, and has come to you for advice. Describe * the extra information that he should store in each node of the tree to make this possible; * how the extra information at a node X in T can be updated in O(1) time from the key K stored in X and the extra information stored in the children of X (which will ensure that insert() and delete() run in time O(height(T))); and * an O(height(T)) implementation of Qth() that uses this information. Explain why your algorithm works as well as how. You need NOT describe how to do insertion or deletion in a BST. Note: If you are unable to help Benno, for half-credit you may describe a slower implementation of Qth() that does not use any extra information. P7. Write a C function that, given N and the int array X, rearranges the elements X[0], X[1], ..., X[N-1] in DECREASING order. That is, supply the missing code (including variable declarations, if needed) below. How many comparisons does your function require (as a function of N) in the worst case? In the best case? void sortDecreasing (int n, int x[]) { CS-223-04/12/16