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:

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:

- 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?
- Does the value of k have any impact on the absolute times or the rate-of-growth?