Assignment V

Due date March 5.

For the following questions, write pseudocode, or use the programming language of your choice. Recall that in either case the most powerful construct in any language is the comment! That is to say, explain your design.

1. Suppose you are given a sorted array of N numbers. How would you build a regular binary tree (i.e. one with no additional clever structures) that is as balanced as possible? Hint: how do you find the best root for the tree?

2. Suppose you have a simple binary tree, where each node holds just a value and two pointers to child nodes. Write a function or method to determine whether this tree has the balance property of an AVL tree. As usual, recursion solves everything.

3.Recall that the sparsest AVL tree is one in which every node is as unbalanced as it can be.

a. What is the number of nodes in the sparsest AVL tree of height 10? (Formula discussed in class).

b. Write a method that builds the sparsest AVL tree that holds the numbers 1,2...N, where N is the number of nodes of the sparsest AVL tree of height h.

4. From text: problems R-3.5 and R-3.6 (p. 212).

5. Suppose we have a balanced binary search tree of some kind. The smallest element stored in the tree is the leftmost descendant of the root, and the largest is the rightmost descendant. Suppose we want to use the tree to find efficiently the kth element in order. Can you think of a way to enrich the information stored at every node, so that this operation can be performed in logarithmic time?