As suggested in class, here is the pseudocode to balance an unbushy tree:

TREE-BALANCE (T)

1. create array A(N1)

2. for i = 0 to N1

3. x = T.root

4. A[i] = x

5. TREE-DELETE(T, x)

6. for j = 0 to N1

7. TREE-INSERT(T, A[j])

Assume that the tree, though a little unbalanced, is not that bad, such that at the end of the for loop in lines 2-4 the values in the array are pretty well randomly distributed.

a. Perform an asymptotic analysis of TREE-BALANCE to determine its running time in terms of N. Write out each step in detail. What is the cost of TREE-BALANCE in additional storage space?

b. What is the worst case of a Binary Search Tree? What happens to the running time performance of TREE-BALANCE in this case? What is the overall outcome of the shape of the tree in this case?

c. In the discussion of QUICKSORT we saw an alternative PARTITION function, called RANDOMIZED-PARTION. Thinking about this, how could you devise a helper function to insert between lines 5 and 6 in the above pseudocode that would help address the problem of really badly balanced trees? What would this do to the overall running time of TREE-BALANCE?

d. Devise another approach to TREE-BALANCE to guarantee a very well balanced binary search tree as the result. (Hint: The first lines will probably look the same, but after the completion of the first for loop rather than randomize A, you'll sort A. Then, in place of the second for loop, what would be done next?) Analyze the running time performance of this approach to Tree-Balance.