Computer Science 2210 - CSCIDBW Home



Computer Science 2210

Lab Assignment 5

Purpose

The purpose of this assignment is to get some experience using binary search trees and AA trees and to analyze the performance of each in finding a specified value in a node.

Assignment

Using the implementation of a binary node, a binary search tree, and an AA tree in the course notes as a basis, implement a program that will build a binary search tree and an AA tree of data from the file named lab5a.dat. The records in this file look like the following:

Wacky I M 084-19-0098 113083 NC

The leftmost 20 columns contain a name that is followed by a social security number, a birth date, and a state of residence respectively. The search will be conducted based on the name field as the search key (i.e., you will have to provide code to support this ordering in the trees in question).

Your program should allow the user to enter a name after which a search for the record containing that name will be conducted in both the binary search tree and the AA tree. Make the search be case-insensitive. Both searches should display the nodes visited in the search process so that you can compare the two approaches in terms of nodes visited. Finally, you should display the entire record containing the name or a NOT FOUND message regarding the name. This may involve some modification to the base code provided.

Test the program with a substantial number of the names found in the file and some not found in the file. Make sure your test cases represent a good sample of the data file (i.e., some – both existing in the file and not - names that are alphabetically at or near the beginning, some in the middle, some at the end, some randomly selected, etc.)

Additional Specifications

The program should be menu-driven. In addition to building the trees and finding the nodes, display each of the trees in each of the four traversal orders discussed in class. The displayed information should be well labeled as to which tree, which order, etc. the data represents. The lines in the bodies of the displays should be numbered.

Draw (using a drawing program) the binary search tree and the AA tree produced in this assignment from this particular data set using the information in the traversal printouts. The drawings should be neat and well labeled.

In a written report of one-page or less, state any conclusions you were able to reach from the observations made during the execution of the program and the data it produces. Indicate why you think the results came out as you see them.

Deliverables

Turn in a zipped file containing your project, source files, executable (lab5TreesYourName.exe), and any data file(s) you used – in a folder labeled Lab5-TreesYourName. It should be clearly labeled with your name, the course number, the lab assignment number, and your email address.

Also, turn in a very short (word-processed) report (one page or less, but not too skimpy) on your findings and your recommendations. It should accompany the drawings of the trees constructed from the data file and the printouts produced by your program. The drawings do not have to be the complete trees, but they should show enough of the nodes at the top of the tree to show that you know each the tree’s shape and contents. Five levels of data should be enough.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download