CSC 321: Data Structures
Fall 2016

HW4: Recursion & Binary Search Trees

  1. Add the following methods to the BinaryTree class:
    numOccur(value)   Returns the number of times value appears in the tree.
    height()   Returns the height of the tree, i.e., the length of the longest path from the root to a leaf.
    weight()   Returns the weight of the tree, i.e., the sum of all the node depths.
    and the following methods to the BinarySearchTree class:
    numBelow(value)   Returns the number of tree entries that are smaller than value.
    numAbove(value)   Returns the number of tree entries that are bigger than value.
    avgCost()   Returns the average cost of a search in the tree, i.e., weight/size.
    Be sure to test your methods thoroughly before continuing.

  2. It has been proven that adding N random elements to a binary search tree will produce, on average, a tree with O(log N) height. In addition, the average search cost for an arbitrary item in such a binary search tree is O(log N). You are to verify these results 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 height and average cost of searching that tree.

    Your program should display the average of these heights and costs over all of the constructed 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+1)⌉ average cost average height
    N =   1,000   
    N =   2,000   
    N =   4,000   
    N =   8,000   
    N = 16,000