CSC 421: Algorithm Design and Analysis
Spring 2017

HW3: Decrease/Divide & Conquer Trees

In CSC 321, we considered implementations of binary trees and (through inheritance) binary search trees. The following classes are simplifications of the versions from last semester: BinaryTree.java, BinarySearchTree.java, and TreeDriver.java. The TreeDriver class generates a binary search tree of a user-specified size, then performs repeated searches and times the result. Using this driver, it is possible to demonstrate that the contains method on a randomly-generated binary search tree is O(log N).

In order to prove the adage that "a log is a log," you are to implement more generic k-ary trees. A k-ary tree stores up to k-1 values in a node, with up to k subtrees. Thus, a binary tree is a 2-ary tree. In a k-ary search tree, the binary search tree property is generalized so that the values in the ith subtree must be greater than or equal to the (i-1)th and ith data values in the node. For example, the diagram below shows a 3-ary search tree of numbers:

Because a k-ary tree divides the values into k subtrees at each level, a randomly generated k-ary search tree will have height proportional to logk N. But while the expected height of k-ary trees decreases as k increases, the amount of work that has to be done to search each node increases. As a result, k-ary trees should exhibit the same O(log N) rate of growth pattern as binary search trees.

To demonstrate this, you are to implement two new classes: KaryTree.java and KarySearchTree.java. These classes will closely parallel the BinaryTree and BinarySearchTree classes, but generalized to k-ary trees. You are required to implement the add, contains, size, and toString methods. In a k-ary tree, adding a value at a given node uses the following rule: if there is space at that node, store it there; if not, randomly select a subtree and add the value to that subtree. Adding to a k-ary search tree modifies this: if there is space at that node, insert it into that node in order; if not, add the value to the appropriate subtree (based on the ordering). The order in which values are listed by toString doesn't matter for a k-ary tree, but for k-ary search trees the values should appear in comparable order. For example, the toString method should return the above 3-ary tree as "[1, 2, 3, 4, 8, 10, 12, 14, 16, 18, 20, 21, 24, 30, 40]". For extra credit, you may implement other methods, such as remove, height, and weight.

Once you have your classes completed and tested, make appropriate modifications to the TreeDriver so that it enables you to time repeated searches on k-ary search trees. Provide data and analysis to answer the following questions:

  1. Do k-ary search trees follow the same rate-of-growth pattern as binary search trees? That is, if you double the size of the tree, does the amount of time it takes to perform a search only go up by a constant amount?
  2. Does the value of k have any impact on the absolute times or the rate-of-growth?