Homework Six
Tree Balancing
Due: Thursday March 10

For the last assignment, you created a tree printing routine. You will now need it to help debug this assignment.

Here is a data file that contains 2500 four digit numbers. No values are repeated. Put the values straight into a binary search tree and report the height. Then use the balancing method we discussed in class to partially balance the tree. Report the height again. Example output of your program might be: 

     Initial tree height = 29
  Height after balancing = 16
Note that the optimal height of a binary tree with 2500 nodes would be 12, since log2 2500 = 11.2877. However, our rotate functions are pretty rough, so getting close to 12 is good enough.
Hints:
Again, start slow. Just take that tiny tree from lab 5 and determine its height.

Once you have a height and weight function, add the add function. Test your add function using your print function with a small amount of data - perhaps 10 nodes.

Leave balancing 2500 nodes until after you can balance 10 nodes.