Homework 6

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

This Homework Is Due By 11:59 PM on Wednesday December 16, 2015

1. Implementation:
   

   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>

   Make sure to include the following methods in the BinarySearchTree<T> class:

   1. height()
   2. height(TreeNode<T> root)
   3. isBalanced()
   4. isBalanced(TreeNode<T> root)
   5. balance()
   6. balance(Object[] arr, int first, int last)

   Create a MyInteger class that extends KeyedItem<KT>.



2. Test Cases:
   

   Your driver program should do the following things 10 times:

   • Create 131,071 MyInteger objects randomly generated. Save all your randomly generated MyInteger objects in a Vector<MyInteger>.
   • Measure the run times for the following test cases:
   • Insert all your MyInteger entries in the BinarySearchTree<MyInteger>.
   • Search your BinarySearchTree<MyInteger> for all the MyInteger entries in your Vector<MyInteger>.
   • Measure and display the height of the BinarySearchTree<MyInteger>.
   • Balance the BinarySearchTree<MyInteger>.


3. Driver Class:
   
   Your driver must be in a class named Driver. Your Driver class must implement the following:
   
   
   1. All the methods specified in the Driver documentation



4. Statistics Class:
   
   In addition to printing the run times for each test case, you will have to also display the average time and the standard deviation. You will have a class named Statistics. and it must implement all the methods specified in the Statistics documentation.

Please make sure that all your Java programs are in the default package.

Please compress the Java programs as a zip file containing:

1. TreeNode.java
2. TreeException.java
3. BinaryTreeBasis.java
4. BinaryTree.java
5. BinarySearchTree.java
6. TreeIterator.java
7. KeyedItem.java
8. MyInteger.java
9. Driver.java
10. Statistics.java

Please submit your zip file at the Mimir Platform Website .