csc2001f_assignment_2

Write an Electronic Telephone Directory application in Java, using an AVL Tree as an internal data structure. Your AVL Tree implementation can be created from scratch or re-used from anywhere. You may NOT replace the AVL Tree with a different data structure. The data you are given (see attached file) has the following format: 51850 Kianna Squares, Terre Haute|552.531.3674|Gislason Kenna 17386 Stephanie Parks, Palm Springs|018-594-2935 x716|Hickle Leone 97354 Queen Squares, Birmingham|(332)985-4036|Moore Gilbert The fields are: address, telephone number, name. Every full name has a last name and a first name. The fields are separated by "|". The lines of the file are unsorted. When loading this data, the key you must use is the full name. You need to parse each line of text and extract the name. Each record will therefore contain: {full_name, full_entry}. Your tasks are as follows: Write an application SearchAVL to search for an entry based on a full name. Your application must read in a list of queries from a query file, search for each one and output "Not found" or the full entry for each query. The data file must be loaded only once. Conduct an experiment with SearchIt (from previous assignment) and SearchAVL to demonstrate the speed difference for searching between a BST and an AVL tree. Measure the speed of insertion, deletion and search operations. Extract names from the data file and use only these names as queries. Use multiple subsets of the data from n=1 up to n=10000. Draw a graph for each operation that illustrates the relative performance of your applications for different values of n. You may want to instrument your code by inserting timekeeping operations such as the following. If your computer is too fast to take accurate readings of small amounts of time, run the operation multiple times.