Data Abstraction and Problem Solving with Java 3rd Edition book name
Implementation:
Adapt the following classes from the textbook to have private data members and the needed getters and setters where necessary:
TreeNode<T>
TreeException
BinaryTreeBasis<T>
BinaryTree<T>
TreeIterator<T>
KeyedItem<KT>
BinarySearchTree<T>
Add the following methods to the BinaryTreeBasis<T> class:
public int treeHeight() // This method returns the height of the tree.
public boolean isBalanced() // This method returns true if the tree is balanced, false otherwise.
public void balanceTree() // This method should balance the tree if necessary.
Create a Person class that extends KeyedItem<KT> and contains the following information:
private String name // Will be used as the Search Key.
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:
public boolean equals(Object obj)
public String toString()
In addition, the Person class should implement the Comparable interface.
Test Cases:
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.