CSC 427: Data Structures and Algorithm Analysis
Fall 2007

HW5: Recursion and Binary Search Trees

  1. Add the following methods to the BST class: /** Returns the number of nodes stored in the tree */ public static <E extends Comparable<? super E>> int numNodes(TreeNode<E> current) /** Returns the height of the tree (i.e., longest path length from root to a leaf) */ public static <E extends Comparable<? super E>> int height(TreeNode<E> current) /** Returns the weight of the tree (i.e., sum of all node depths) */ public static <E extends Comparable<? super E>> int weight(TreeNode<E> current) /** Returns the average cost of a search in the tree (i.e., weight/size) */ public static <E extends Comparable<? super E>> double avgCost(TreeNode<E> current)
  2. It has been proven that the average search cost for an arbitrary item in an arbitrary binary search tree of N items is O(log N). You are to verify this result experimentally. Write a program that 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 display the average of these costs over all of the constructed trees. In addition, it should display 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 average height = 21.76
  3. Run your program from part 2 for various values of N, using T = 1,000. Report the average height and cost of searching the trees you constructed. Do your statistics support the claims that the average height and cost of searching a randomly constructed binary search tree are both O(log N)? Justify your answer.

    number of values (N) ⌈log2(N)⌉ average cost average height
    N = 1,000   
    N = 2,000   
    N = 4,000   
    N = 8,000