Description
In this homework, you are going to implement a phonebook which will help the user to make several operations faster such as searching, adding, deleting contacts. For this purpose, you are required to store the contact information in the Binary Search Tree (BST) and AVL tree and experience the implementation and performance differences between both data structures. Your tree implementations MUST be template-based.
The Contacts Input File
We will provide you with input files (phonebooks) which are lists of contacts of different sizes where each line is composed of:
firstName lastName phoneNumber city
There is only ONE space between each field. And, each person has only ONE first name and last name.
Therefore, in each line, there are exactly 4 strings. An example input file can be as follows:
You can assume that the given input file is valid.
The functionalities
There has to be 6 available functions in your program:
- SearchContact
- AddContact
- DeleteContact
- InOrderPrintToFile
- PreOrderPrintToFile
- DrawTreeToFile
AddContact: Adds a new contact for a given firstName, lastName, phoneNumber and city information to both BST and AVL trees. Note that, while inserting into trees, the comparison should be done by alphabetically.
If the given contact info already exists, print a message to warn the user such as “The given contact full name already exists in the database.” To decide whether a contact info already exists, a full match must be done for the full name. Note that full name is the concatenation of firstName and lastName by leaving a blank between them. For instance, if firstName is “Ali” and lastName is “Veli”, then the full name will be “Ali Veli”.
DeleteContact: Given the full contact name (firstName+lastName), your program should remove that contact from the phonebook.
SearchAContact: The search should be performed this way:
- Whenever you enter a full name, your program will display the contact(s) that matches the search full name.
- If a partial string is entered, your program should display the contact(s) whose full name starts with the entered partial word (see sample runs for examples).
InOrderPrintToFile: Print out the phonebook in Pre-order to a file named phonebookInOrder.txt . The information that should be printed is the full name, phone number and city, the same as the input file but ordered as InOrder sorted.
(Debugging hint: the orderings should be identical).
PreOrderPrintToFile: Print out the phonebook in Pre-order to a file named phonebookPreOrder.txt . The information that should be printed is the full name, phone number and city, the same as the input file but ordered as PreOrder sorted.
DrawTreeToFile: Prints out both BST and AVL (as shown below) into 2 separate files named as phonebookTreeBST.txt and phonebookTreeAVL.txt .
The flow of the program
Once you run your program, it should read the input file (One of the samples given to you, ex: PhoneBook-sample2.txt) and load all its contacts into a BST and an AVL tree. After that, your program should display a menu of functionalities (functions from 1 to 5 , given in sample runs) that it should perform successfully. Once a selection of a function is made, it should be executed for both trees, the BST and the AVL.
Your program will display the execution times of each operation performed from the list in both trees (The sample runs will explain it thoroughly).
Important: Each node in the tree should contain (Full name, Tel number and City).
Your program should have a list of options to choose which function to run on the phone book, the screenshots below show you how your program should look after running it.
First, it prompts to ask for an input file which is the phonebook .txt file that will be provided to you. Then, after entering the correct file name, the phonebook should be loaded to both, the BST and AVL trees. (Don’t forget to measure tree creation times for both trees).
From this example, you might have noticed that after loading the phonebook to each tree, it prints the heights of both left and right subtrees for both BST & AVL trees to show whether the tree is balanced or not. It is IMPORTANT to note that your program must redisplay the same menu after running any operation in order to perform another one.
Note: The InOrder and PreOrder functions should be run using the same choice from the menu (choice number 4).
Sample runs
Input file: PhoneBook-sample(i).txt Output files:
- txt
- txt
- txt
- txt
Sample Run 1; ( Printing & Drawing)
phonebookPreOrder.txt phonebookInOrder.txt
Hint (Drawing): To draw the tree, you can write a recursive function that traverses the tree’s levels. It is pretty similar to a pre-order printing function with few additional code lines where you have to draw something according to whether you are in the left subtree or right subtree of each node
Sample Runs 2 & 3
For Sample runs 2 and 3 you can access their files from the sample runs folder (inside homework2 folder) lin k since the input sizes are much bigger and there is no room for displaying their outputs in the homework document.
Sample Run 4 (Searching)
An example showing the search operation Another example showing the search
being faster in an AVL than in a BST tree operation being faster in an AVL than in a
BST tree
Important: You should make sure that your code runs on any random input file of any size, therefore, we would probably use other inputs rather than the samples that we have provided you in the homework folder.
Sample Run 5 ( Deletion)
As you will notice in the figure below, the deletion in the AVL tree took less time than the deletion in the BST, it is about 500 times faster. However, when the maximum height in the BST is close to the maximum height of the AVL tree, then there will be cases where the deletion in BST is faster than in AVL. Please note that you should print a message to indicate that the deletion “terminated successfully” in case the contact to be deleted exists in the phonebook, otherwise, it should print “Not found ”.
Sample Run 6 (Insertion)
