CS 206: Data Structures
Exercise#18
Due on Tuesday, April 29
Part 1: Redo Exercise 15 to use 1 entry per town (with a list of all zip codes) and entries stored in a Binary Search Tree (as implemented in Exercise 17) using the string TOWN+STATE as the ordering relation.
For demonstrating the correctness of your program, include a printout that shows the output from following queries:
Additionally, after reading in the input file, your program should print the height of the resulting tree.
Part 2: After collecting the data, modify your program so that instead of using TOWN+STATE, it uses the string STATE+TOWN as the ordering relation.
After obtaining all the answers, compute the average number of comparions needed to answer a query, the average number of comparisions needed to answer a successful query, the average number of comparisons needed to answer an unsuccessful query for both parts. Show, on a table, how the two representations (TOWN+STATE and STATE+TOWN) compare against each other (including the resulting heights).
Hand in a prinout of the complete program from Part 2 and the outputs from Part 1 and Part 2.
Technical Notes:
In order to clean up the comparisons, you should implement the Java standard Comparable interface in your city ADT class. The Comparable interface is defined as follows:
public interface Comparable {
public int compareTo(Object item);
}
That is, you will need to implemen the compareTo method
for objects of type CITY (or whatever you named your ADT). In the compareTo
method, you can then use the String class'
compareTo to compare whatever ordering you wish to use (TOWN+STATE
or STATE+TOWN).