Name _____________________________
CPTR247
Fall '04 (100 points) Exam
3
1. Complete the following table by entering the algorithmic complexity for each method. (1 point each)
Enter one of the following for each:
C for constant time – O(1)
log for logarithmic time – O(log_{2}n)
n for linear time – O(n)
n^{2} for quadratic time – O(n^{2})
Data Type 
Implementations 
Methods 
averageTime(n) 
worstTime(n) 
AVL trees 
balanced binary search tree 
insert 


find 



height 



Redblack trees (and therefore sets, multisets, maps, multimaps) 
balanced binary search tree 
insert 


find 



erase 



begin 



end 



size 



empty 



[ ] (map class only) 



Priority Queue 
Heap (complete binary tree) 
size 


empty 



push 



pop 



top 



make_heap 


2. Give the definition of an AVL tree. (5 points)
3. Explain why AVL trees and Redblack trees are “better” than arbitrary binary search trees. (5 points)
4. Do the specified rotations on the trees given. (8 points)
a. Do a right rotation around 50.
b. Do a right rotation around 17 followed by a left rotation around 10.
5. Below is psuedocode for inserting items into an AVL tree:
· inserted as for a normal binary search tree and its balance factor is set to ‘=’
· ancestor points to the closest ancestor whose balance factor is not ‘=’
Case 1: ancestor is null: no rotations are necessary, adjust balance factors from inserted node to root.
Case 2: ancestor’s balance factor is ‘L’ and insertion was made in the ancestor’s right subtree, or ancestor’s balance factor is ‘R’ and insertion was made to the ancestor’s left subtree: no rotations are necessary, change ancestor’s balance factor to ‘=’ and adjust the balance factors of the nodes between ancestor and inserted node.
Case 3: ancestor’s balance factor is ‘R; and the inserted node is in the right subtree of the right subtree of the ancestor node: do a left rotation around the ancestor node, adjust the balance factors as necessary.
Case 4: ancestor’s balance factor is ‘L’ and the inserted node is in the left subree of the left subtree of the ancestor node: do a right rotation around the ancestor node, adjust the balance factors as necessary.
Case 5: ancestor’s balance factor is ‘L’ and the inserted node is in the right subtree of the left subtree of the ancestor node: do a left rotation around the ancestor’s left child, and then a right rotation around the ancestor node, adjust balance factors as necessary.
Case 6: ancestor’s balance factor is ‘R; and the inserted node is in the left subtree of the right subgtree of the ancestor node: do a right rotation around the ancestor’s right child and then a left rotation around the ancestor, adjust balance factors as necessary.
For each of the following trees, the number indicated is to be inserted into the given tree. State the Case number that is applicable and draw the tree as it would be after the insert is complete. (10 points)
Tree Insert Case # Resulting Tree
3
25
6. Fill in the table below with the container class that is described. Select from set, multiset, map, and multimap. (8 points)
___________ contains keyitem combinations, but the key must be unique
___________ contains keyitem combinations, and you can have more than one item with the same key
___________ a collection of individual items, and there may be duplicates
___________ a collection of individual items, all of which are unique
7. Consider the following code:
typedef map<string, int> themap;
themap mymap;
mymap.insert(pair <string, int> (“Fred”, 59));
mymap.insert(pair <string, int> (“Ethel”, 57));
mymap.insert(pair <string, int> (“Ricky”, 45));
mymap.insert(pair <string, int> (“Lucy”, 42));
cout << mymap[“Lucy”] << endl;
themap::iterator itr;
itr = mymap.begin();
cout << itr>first << “ “ <<
itr>second << endl;
8. Give the definition of a heap. (5 points)
9. For the following heap, fill in the underlying vector with the node values as it would be laid out in memory. (5 points)












10. The value 95 is to be inserted into the heap in question 9. Draw the resulting heap (in tree form). (5 points)
11. The following vector is to be converted into a heap. Give the contents of the vector after it is heapified. (HINT: Construct the “tree version” corresponding to the vector and then go through the heapifying process.) (5 points)
57 
43 
55 
73 
99 
60 
45 
30 
90 
78 










12. Draw the contents of the following priority queue (implemented as a heap) after the pop method has been called. (5 points)
13. Given the following character frequencies, create the Huffman Tree. (5 points)
a: 1800
c: 50
e: 600
n: 800
r: 300
S: 500
t: 900
14. Using the Huffman Tree that you created in the previous question, encode the word Santa (5 points)
EXTRA CREDIT: (10 points)
Let min_{h} be the minimum number of items in an AVL tree of height h. Prove by induction that
min_{h} = fib(h + 3)  1
where fib(n) is the function for the Fibonacci numbers.