Exercises

1. a. Using its definition, calculate the weighted path length of the following tree. The weight of a node appears at the node.

b. Calculate the weighted path length of the tree using the other method of assigning a "value" to each node and adding up all the "values."

c. Calculate the weighted path length of the same tree by adding the sum of all its weights to the weighted path length of its left subtree plus the weighted path of its right subtree.

2. Write a process function to turn a postorder traversal into a function for determining the weighted path length of a binary tree T based on the method of Exercise 1(b).

3. Determine the Huffman code (tree) for weights 1, 2, 3, 4, 5.

4. Determine the weighted path length for your solution to Exercise 3.

5. The Huffman tree for n weights will always have (n - 1) internal nodes and n terminal nodes. This is because it is a full binary tree. That is, every internal node has exactly 0 or exactly two successors. Prove, by induction on the total number of nodes of a full binary tree, that this is true.

6. Write a nonrecursive function, huffman, with parameters n, weights, tree, and code. Weights is an array containing n weights, code is an array returned containing the n codes (sequences of 0's and 1's) assigned to each weight by the Huffman code, and tree points to the root of the corresponding Huffman tree upon return. Your function should take O(n 1g n) time.

7. Write a recursive version of the function of Exercise 6.

8. Simulate the proof (by induction on n) that the Huffman tree yields a binary tree with minimal weighted path length for n weights for Exercise 3.

9. Write a function decode with parameters n, alpha, and tree. Alpha is a sequence of n 0's and 1's, and tree points to a Huffman tree for the twenty-seven characters of Section 12.3 (determined by their weights). Decode is to decode the sequence of n 0's and 1's into the corresponding characters. The sequence represents a coded version of a message composed of the characters.

10. Suppose you know the Huffman tree for the twenty-seven characters of Section 12.3 (determined by their weights). Write a function encode to encode a message composed of characters into the Huffman code. To do this you might consider using the following data structures:

a. The Huffman tree.

b. An array with twenty-seven records kept in sorted order by character, each record containing a character and its corresponding Huffman code.

c. A hash table of records, each record consisting of a character and its Huffman code; the key is the character.

Discuss the relative advantages and disadvantages for each of these in the function encode.

11. Write a function encode to encode a message in a Huffman code.

12. Let a0 = 10, a1 = 6, a2 = 8, a3 = 4, a4 = 2, b1 = 2, b2 = 5, b3 = 7, b4 = 6. Determine the optimal binary search tree by generating all possible binary search trees storing the four keys with weights 2, 5, 7, and 6, and calculating their weighted path lengths.

13. The recursive approach of Section 12.4.1 is based on the idea that an optimal binary search tree must have an optimal left and an optimal right subtree. Can you use this idea to show that some of the trees you considered in Exercise 12 could have been ignored in searching for the optimal tree?

14. Simulate the bottom-up algorithm of Section 12.4.1 to reproduce the arrays of Figure12.11.

15. Why do we want to find nearly optimal binary search trees rather than optimal binary search trees for large numbers of keys?

16. Find the greedy binary search tree for the weights of Exercise 12 using the definition of a greedy tree. Determine the relative difference between its weighted path length and the optimal value.

17. Find the greedy binary search tree for the weights of Exercise 12 using the implementation of the greedy tree construction. Is its weighted path length the same as the greedy tree of Exercise 16?

18. Write a nonrecursive function greedy to implement the greedy tree construction of Section 12.5.3.

19. Give a recursive definition of a greedy binary search tree.

20. Write a recursive function greedy to implement the greedy tree construction of Section 12.5.3.

21. Another method of constructing a nearly optimal binary search tree is to select the key to be placed at the root to be a key that minimizes the difference between the weights of its left and right subtrees. Having obtained the root, apply this procedure recursively to construct its left and right subtrees. This is a top-down construction, as opposed to the greedy tree construction, which is bottom-up. What tree does it generate for the weights of Exercise 12 and for the example of Section 12.5.2?

22. Write a recursive function for the construction method of Exercise 21. How much time does your function require?

23. Can you find a way to implement the procedure of Exercise 21 in O(n) time, where n is the number of internal keys to be stored?

24. What will a greedy tree look like if the n b's are zero and the n + 1 a's are given by the first n + 1 Fibonacci numbers? Give two answers梠ne when the greedy tree definition is used, and one when the O(n) implementation is used.