ICS 211 Homework H10: Sort by using a Binary Search Tree

Purpose

Our next abstract data structure is the Binary Tree. For this homework assignment we are going to implement a Binary Search Tree to sort Contacts. This assignment should give you more practice with Eclipse and using a tree to store and sort information.

Section 6.5 Binary Search Trees has a very good write up of Binary Search Trees with code. Remember to give credit if you use the source code from the textbook.

Tasks

1. Create a package named edu.ics211.h10

This is where we will put all our classes for homework 10.

In this assignment you will implement a BinarySearchTree class, Contact class, ContactComparator, and use them to sort the Contacts.

2. Create a Contact class and a ContactComparator to compare them

Your ContactComparator must implement the Comparator interface to compare Contacts. It should sort by last name then first name. Your ContactComparator must pass the ContactComparatorTests.

3. Create a BinarySearchTree class that implements the SearchTree and InOrder interfaces

The BinarySearchTree must:

• implement the SearchTree and InOrder interfaces,
• use a Comparator to decide 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 interface InOrder<E> {
  /**
   * Returns the items in sorted order.
   * @return The items in sorted order.
   */
  List<E> inorder();
}

public class BinarySearchTree<E> implements SearchTree<E>, InOrder<E> {
  private Comparator<E> comp;

  /**
   * Creates a new BinarySearchTree.
   * @param c the comparator to use for determining order.
   */
  public BinarySearchTree(Comparator<E> c) {
    ...
  }
  ...
}

Your BinarySearchTree needs to pass BinarySearchTreeTest.

4. Write up an Algorithm Analysis

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.

Testing

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.

Grading Rubric

Turning in the Assignment

The assignment is due on Friday at 11:55pm. You may turn it in early.

1. Does your code follow the Java Coding Standard and pass CheckStyle?
2. Does your code pass the JUnit Tests?
3. Export your project following the instructions at the bottom of the page. Name the file H10.zip
4. Sign into Laulima, then navigate to the ICS211 site. In the left hand side of the site, there is an Assignments tab/link. Click on it and view all of the posted assignments. Select the assignment that you want to turn in and attach your H10.zip file accept the honor pledge to submit the assignment.