Assignment #7

Due: Friday, November 19, 2PM

For this assignment, you will write two more implentations of the interface Dictionary to be used with your program that maintains the database of customers. The first will organize the set of customers in a Binary Search Tree and the second will use a Hash Table with separate chaining.

Since all of these implementations implement the same interface, all you should need to change in your program is the line of code in which the object which stores the set of customers in instantiated.

Here are more details about each of the individual implementations:

• Binary Search Tree: The items are stored in a binary search tree. The ordering is still occording to the ordering as indicated by the compareTo method in the key.

  Implementing the iterators for a binary search tree may take some thought. You need to implement two iterators. One of these is an iterator over all the values that match a particular key. (Recall that there may be more than one customer with the same name). For this iterator, the easiest thing to do would be to create a linked list with all the customers who have the requested name. If you like, you can use the List class in the Java API. The List class already has an iterator() method associated with it which returns an instance of interface Iterator . (There may need to be some additional changes to your code here if you did not store a reference to the iterator as an instance of Iterator in the API).

  The other iterator which you need to implement iterates over the entire tree. Since this may be quite large, it doesn't make sense to make a linked list for all the items in the tree. However, in order to maintain your place in the tree and get to the next item, you may need to travel `upward' in the tree. Since your BST will not have parent pointers, your iterator class (which you will write) must maintain a stack with all the nodes in the path from the root down to the current node. To travel upwards in the tree, you just need to pop the stack. To travel downwards, you need to push the current node onto the stack.




• Hash Table: Use a hash table of size 1031 . For the hash function, append the first, middle and last names, to get a string s . You may use the cyclic shift hash code described on page 364 (p. 346 in the 2nd Edition) of your text. You will then need a compression map to get a number within the desired range.

  It is impractical for hash tables to iterate through the customers in alphabetical order, so it is fine to run through them in whatever order they happen to be stored in the hash table.