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