###
CSC 427: Data Structures and Algorithm Analysis

Fall 2004

HW5: Recursion and Binary Search Trees

It has been proven that the *average* search time for an arbitrary item in an arbitrary binary
search tree of N items is O(N). For this assignment, you
will verify this result experimentally. First, add the member functions whose protoypes are
given below to the BinarySearchTree class:

int NumNodes(); // returns total number of nodes in the tree
int Height(); // returns number of nodes on longest path from root
// (root at depth 1, children at depth 2, ... )
int Weight(); // returns weight of the entire tree, derived by
// adding the depths of all nodes in the tree
Once you have these member functions implemented and tested, write a program
(`verify.cpp`) which first prompts the user for the number of items to be stored (N)
and the number of trees to generate (T). Then, it should repeatedly (T times) store N random
numbers in a binary search tree and compute the average cost of searching that tree. Recall
that

average cost of a search = (weight of the tree / number of nodes in tree).
Your program should print out the average of these costs over all of the constructed
trees. In addition, it should print out the average height of the trees. For example,

Number of values to be stored: 1000
Number of trees to generate: 100
Generating 100 trees with 1000 random values:
average cost = 11.9146 = 1.19146 * ceiling(log2(1001))
average height = 21.76 = 2.176 * ceiling(log2(1001))
Note: in order to determine the constant for the average cost and depth, you will need to
be able to compute the base-2 logarithm of a number. In the `cmath` library, there is
a function called `log10` which computes the base-10 logarithm of a number.
Logarithms can easily be converted from one base to another using the formula:
`log`_{a} N = log_{b} N / log_{b} a