Homework 5

CMP 338: Data Structures & Algorithms
Lehman College, City University of New York
Spring 2017

This Homework Is Due By 11:55 PM on Sunday May 7, 2017

Overview

In this assignment you will be adding functionality to the BinarySearchTree class that we worked on in class.

You will also be writing a driver to test the BinarySearchTree.

Details

1. TreeItem Class

   You will be using the TreeItem class that we implemented in class. The class may be downloaded from TreeItem.java

2. TreeNode Class

   You will be using the TreeNode class that we implemented in class. The class may be downloaded from TreeNode.java

3. TreeException Class

   You will be using the TreeException class that we implemented in class. The class may be downloaded from TreeException.java

4. TreeIterator Class

   You will be using the TreeIterator class that we implemented in class. The class may be downloaded from TreeIterator.java

5. BinarySearchTree Class

   You will be expanding the functionality of the BinarySearchTree class that we implemented in class. The class may be downloaded from BinarySearchTree.java

   you will be adding the following methods to the BinarySearchTree:

   1. public int height()
   2. private int treeHeight(TreeNode node)
   3. public boolean isBalanced()
   4. private boolean isBalancedSubtree(TreeNode node)
   5. public void balance()
   6. private TreeNode balanceTree(TreeItem[] arr, int first, int last)

6. Driver Class

   You will write the Driver.java class which will implement the Driver Interface. The interface may be downloaded from DriverInterface.java.

7. Test Cases

   You will be instantiating a BinarySearchTree<Integer,String> with TreeItem<Integer,String> objects. Your tree will be expected to properly handle the following test cases:

   1. Create 131,071 TreeItem<Integer,String> objects randomly generated. Save all your randomly generated TreeItem<Integer,String> objects in a Vector<TreeItem<Integer,String>>.
   2. Insert all your TreeItem<Integer,String> objects into the BinarySearchTree<Integer,String>.
   3. Measure the height of the BinarySearchTree<Integer,String>.
   4. Balance the BinarySearchTree<Integer,String>.

Please make sure that all your java classes are in the default package.

Please submit the completed programming assignment on the Mimir Platform Website .

You must submit your Java programs as a zip file of only the classes specified above.