HW4 Fast searches Solution

Description

The key motivation for this assignment is the illustation of a tree datastructure to support the fast searches of the linked lists. A very similar implementation of trees is commonly used by relational databases to build the search indexes for fast information lookups.

You have two tasks to accomplish (1) is to create a linked list that stores airport information and (2) create two search trees that will reference the LList objects for fast lookup. The LList and struct structures are very similar to your previous homework, except they don’t store printers/printJobs but flights. A couble observations:

• don’t store the information in sorted order but in order the input file lists the airports

• there is exactly one instance of a airport struct, but multiple references from different trees

• a real life application would have as many search trees as there is “search by” terms

Your program fastLookup will read a text file as an argument, then executes a command line function.

The command line instructions include

./fastLookup <file name>

d <airportId> # deletes the airport by airport ID from the trees and LList

and the struct itself and repairs the structures as needed

sn <airportId> # search for an ariport by airport ID in the id tree

sc <airportCity> # search for all ariports in a search city in the city tree

sl <airportId> # search for an ariport by airport ID in the LList

q # quit the airport tracker and deallocate ALL memory

The airport struct data are stored in a struct called airport. The structs are stored in a LList by inserting at the head or tail.

The tree structure will build a binary search tree that will reference (point to) the customer structs stored in the LList and contain the rest of the airport information. The tree structure stores the pointer to the left and right child trees and the pointer to the airport data object. The search key is NOT stored in the tree node, but retrieved by following the pointer object and accessing the data object’s field airportID or airport city. The functionality of the search function will simply print

the entire airport record from the object or prints an error message. The search by city is tricky, as the corresponding search tree will have duplicate search keys and your search will have to descend all the way to the leaves to print out all matching ariports at the search city. The search by airport ID on the other hand can stop as soon as it find the search airport key since it is unique.

Motivating example abbreviated to use only airportID and city:

Operational requirements:

1. Airport ID data will be stored in a airport struct

2. A Linked List will keep track of the objects

3. All structures must be allocated on the heap and property freed when information is deleted or the application terminates

4. The linked list will support the following functions/operations:

print LList – prints the list

search by airportID – find and print the airport details located by its unique airport ID.

5. The search trees will support the following functions/operations:

search tree: by airport ID, or by city depending on which tree is used

6. Delete function will delete by airportID. This function will delete the entire record from LList, both search trees and the struct itself.

Implement delete simply and naively, find the struct in the LList, delete the LList node, but before deleting the struct, find the tree node in a tree, delete that node, repeat and find and delete the node from the other tree, and finally deallocate the airport node. (Note: The binary search trees as well as the LList must be property repaired after deletion)

7. I will let you design the rest of your program’s functionality, structs, logic, functions. Couple suggestions: No function of more then 10-20 lines, each malloc has a matching free, separate the functionality operations on the LList, Tree, Airport ADT (don’t mix these, unless you absolutely have to), …

8. If you have time and/or want additional practice, you can add the command line functionality to add an airport <a> <airport information> which will add an airport as an object to a LList and adds the search nodes to both search trees.

9. Dealing with duplicates in the search by city BST. When you encounter an airport that is in the same city as another records (LosAngeles for example), insert the tree node at the time of BST creation immediately as the left child after the duplicate node. For example, if the root “Portland” has a left child “Palmer”, when attempting to insert the second “Portland” into the city BST, it will be the left child of the first “Portland”. The tree will look as “Portland” left child is “Portland” left child is “Palmer”. Handling duplicates is required for city BST only. If the key is not duplicated, it is always added as a leaf to the tree.

10. The datafile has the following fields (and formats) that should be stored in
your airport struct:
I. AirportNumber Unique number for this airport – irrelevant.
II. Name		Name of airport.
III. City	Main airport city. THIS IS YOUR SEARCH CRITERIA FIELD = city
IV. Country		Country or territory where airport is located.
V. IATA	3-letter IATA code. Null if not assigned/unknown.
VI. ICAO	4-letter ICAO code. THIS IS YOUR SEARCH CRITERIA FIELD = airportID
VII. Latitude		Decimal degrees. Negative is South, positive is North.
VIII. Longitude		Decimal degrees. Negative is West, positive is East.
IX. Altitude		In feet.
X. Timezone		Hours offset from UTC.
XI. DST	Daylight savings time. One of E (Europe), A (US/Canada), S (South

America), O (Australia), Z (New Zealand), N (None) or U (Unknown).

XII. Tz database time zone Timezone in “tz” (Olson) format.

XIII.Type The airport type:”airport”, “station”, “port” and “unknown”

XIV. Source Source of this data. “OurAirports”

11. Yes, although we are only using two fields from each line, you have to parse and save the entire line in the airport struct.

Hints and Useful functions:
check out different formating for
strdup	– copy information from stack to heap
atoi	– convert a string to an integer
strtok	– tokenize a line
strcmp	– compares two strings against each other.
toupper	– converts character to upper case (included in ctype.h). It looks like to

covert a string to upper case you have to do it character by character.

Design the delete function recursively, as you will need to set the previous tree node’s (left or right) pointer value to either null or a successor child.

Run your code through the valgrind to confirm you are not leaking memory.

On ‘q’ command line option, make sure you delete and deallocate the LList, airport structs, and both trees.

I don’t care if you add the airport to the LList at the head or tail.

Start with some super simple examples that will generate simple trees that you can easily check for correctness (by themselves, with the data pointers ignores) to make sure you can reliably delete tree nodes.

Grading criteria:

(10 points) Code Operation: Does code do what is listed in the specification? Note:

code that does NOT compile will receive 0 points for code operation.

o 1 points print

o 2 points make search tree

o 3 points delete from search tree

o 1 points malloc

o 2 point free

o 1 point makefile (works for compiling and cleaning)

(5 points) Good programming practices including programming style (5 points) Summary report: Completeness, correctness, and clarity

HW 4 Report Guidelines and Format – use the template provided below. Include the questions in your write-up.

Name: CS 305 HW 4 Report

1. Questions (include these in your write-up):

1a. (.5 point) If your program does not meet the specifications, please note the differences and anything that is not working correctly. If it works, write “Meets all specifications.”

1b. (2 point) Copy and paste your terminal window inputs and outputs to show operation of your code. Generate 5 different data files using the original data file I provided for the homework. Show how the search times differ when using these files as an input to your program and searching them. To make the test files open the airport.dat file in a spreasheet program and sort the rows according the following criteria. Save the altered files as airport1.dat, ariport2.dat … 5. The alternatively sorted files should include the following:

file 1: all records sorted by airportID

file 2: all records reverse sorted by airportID

file 3: partially sorted records by city

file 4: partially reverse sorted records by city

file 5: randomly sorted records in the source data

Prepare a cumulative report of running searches on your files (a table would be nice). The searches should include looking for a record that does not exist, the last record inserted, record in the deepest branch of a tree, etc.

2c. (1.5 point) For each function in your program give a O (big-O) running time on input size n. This is not empirically measured, but calculated from the algorithm’s analysis. (Node, functions are named differently in your code)

Function	Best	Worst	Average	What is the input that causes the best/
	time	time	time	worst/ average running times?
Search airportID
Search LList
Delete airportID from all structures
RepairTree (after deletion)
Make airportID Tree

3a. (.25 pt) How much time did you spend in total on this homework assignment (including the report)?

3b. (.25 pt) What was the most challenging part for you when completing this assignment?

Appendix A: (copy this statement if it applies to you) I verify that the code and this write- up were authored by me. I have documented the help I have received in comments in the code files.

Appendix B: Copy and paste your source files .c, your header files .h and makefile here (use Courier New 8pt font so the characters line up correctly)