In this assignment you will implement a BinarySearchTree class, Contact class, ContactComparator, and use them to sort the Contacts.
A Contact has a first name, last name, contact number.
The ContactComparator must implement the Comparator interface. It should sort by last name then first name.
The BinarySearchTree must:
inorderString that prints out the contacts in sorted order.public interface SearchTree<E> {
/**
* Inserts item into where it belongs in the tree.
* @return true if item is inserted, false if item is already in tree.
*/
boolean add(E item);
/**
* @return true if item is in the tree, false otherwise.
*/
boolean contains(E item);
/**
* @return a reference to the target if found, null if target isn't in the tree.
*/
E find(E target);
/**
* Removes target from the tree.
* @return a reference to the target if found, null if target isn't in the tree.
*/
E delete(E target);
/**
* Removes target from the tree.
* @return true if target was in the tree, false otherwise.
*/
boolean remove(E target);
}
public class BinarySearchTree<E> implements SearchTree<E> {
private Comparator<E> comp;
/**
* Creates a new BinarySearchTree.
* @param c the comparator to use for determining order.
*/
public BinarySearchTree(Comparator<E> c) {
...
}
/**
* @return the contacts in order as a string.
*/
public String inorderString() {
...
}
// implement this class.
}You need another class with a main method that creates the BinarySearchTree, adds several Contacts then prints them out in order.
Write up a runtime analysis of each of the use of a Binary Search Tree to sort, giving the big-O for sorting, and explaining how you got your results. Send your analysis to the TA together with your code. This part counts for 25% of the grade on this assignment. Even if your code doesn’t work, you should do this part to the best of your ability.
You must also build your own test code to make sure that your implementation works.
Please thoroughly test your code and briefly discuss your testing strategy. Turn in all test code.
The assignment is due on Friday at 11:59pm. You may turn it in early. If you haven’t completed the assignment by 11:58, turn in what you have. Getting partial credit is much better then no credit.