CSC 421: Algorithm Design and Analysis
Spring 2014

HW3: Divide & Conquer Trees


For this assignment, you will generalize the BinaryTree class to allow for more than one data value to be stored in a node. A multitree of degree N will allow for N-1 values to be stored in a node, with N children nodes. Thus, a binary tree is a multitree of degree 2 (with 1 data value per node and 2 children nodes). A partial implementation of the MultiTree class is provided for you. Implement the following methods (without modifying the exiting constructor and methods):

/** * Determines the size of the multitree. * @return the number of values stored in the multitree */ public int size() /** * Determines whether the multitree contains a specified value. * @param value the value being searched for * @return true if that value is in the multitree; else false */ public boolean contains(E value) /** * Counts the number of times that a value appears in the multitree. * @param value the value being searched for * @return the number of occurrences of that value */ public int numOccurrences(E value) /** * Determines the height of the multitree. * @return the length of the longest path in the multitree. */ public int height() /** * Determines the weight of the multitree. * @return the sums of the depths of all values in the multitree. */ public int weight()


Once you have written and tested these method thoroughly, write a driver that generates random multitrees and reports the average heights and weights of those trees. For each of the degrees 2 through 6, you should generate 1000 different multitrees of that degree. Each multtitree should have 100 random numbers added to it. Use your driver to complete the table below:

average height average weight
degree=2    
degree=3    
degree=4    
degree=5    
degree=6