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: loga N = logb N / logb a