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₂n)

n for linear time – O(n)

n² for quadratic time – O(n²)

Data Type	Implementations	Methods	averageTime(n)	worstTime(n)
AVL trees	balanced binary search tree	insert
		find
		height
Red-black 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 Red-black 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 key-item combinations, but the key must be unique

___________ contains key-item 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));

1. What is the output of the following: (3 points)

cout << mymap[“Lucy”] << endl;

2. Explain why the following code produces the given output in alphabetical order. (3 points)

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.