Homework 6

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

This Homework Is Due By 11:59 PM on Wednesday April 22, 2015

1. Implementation: (35 Points)
   

   Adapt the following classes from the textbook to have private data members and the needed getters and setters where necessary:

   1. TreeNode<T>
   2. TreeException
   3. BinaryTreeBasis<T>
   4. BinaryTree<T>
   5. TreeIterator<T>
   6. KeyedItem<KT>
   7. BinarySearchTree<T>

   Add the following methods to the BinarySearchTree<T> class:

   1. public int treeHeight() // This method returns the height of the tree.
   2. public boolean isBalanced() // This method returns true if the tree is balanced, false otherwise.
   3. public void balanceTree() // This method should balance the tree if necessary.

   Create a Person class that extends KeyedItem<KT> and contains the following information:

   1. private String name // Will be used as the Search Key.
   2. private String phoneNumber // Format xxx-xxx-xxxx, where every x is in the range 0-9.

   The Person class should Override the following methods inherited from the Object class:

   1. public boolean equals(Object obj)
   2. public String toString()

   In addition, the Person class should implement the Comparable interface.



2. Test Cases: (15 Points)
   

   Your driver program should do the following things 10 times:

   • Create 131,071 contacts, with randomly generated name and phoneNumber data items. Save all your randomly generated contacts in a Vector<Person>.
   • Measure the run times for the following test cases:
   • Insert all your Person entries in the BinarySearchTree<Person>.
   • Search your BinarySearchTree<Person> for all the Person entries in your Vector<Person>.
   • Use the TreeIterator<Person> to display the first 1000 entries using inOrder traversal.
   • Measure and display the height of the BinarySearchTree<Person>.
   • Balance the BinarySearchTree<Person>.
   • Search your BinarySearchTree<Person> for all the Person entries in your Vector<Person>.
   • Use the TreeIterator<Person> to display the first 1000 entries using inOrder traversal
   • Measure and display the height of the BinarySearchTree<Person>.

   Run all test cases 10 times and make a table with the running time for each run, as well as the average and the standard deviation for each test case. Make sure that you re-create your 100,000 contacts for each test case.

Please submit the completed assignment on Blackboard. You must submit your Java programs as a zip file of your Eclipse project.