Question
AVL Tree Implementation using Java
Contents of data file p4small.txt:
06000,66733,CALIFORNIA
06071,1920,"San Bernardino, CA"
06059,6214,"Orange, CA"
06019,1242,"Fresno, CA"
06047,341,"Merced, CA"
06055,225,"Napa, CA"
06065,1784,"Riverside, CA"
06075,2039,"San Francisco, CA"
06073,5351,"San Diego, CA"
06083,721,"Santa Barbara, CA"
06037,22851,"Los Angeles, CA"
06097,655,"Sonoma, CA"
06111,1130,"Ventura, CA"
06001,3648,"Alameda, CA"
06067,1809,"Sacramento, CA"
This project is designed to help you understand tree structure, its implementation, and its usage. You will implement a population database for US counties and states using an AVL Search Tree to store the database records. Define and implement an AVLTree class using county/state code as a key for each record. Download the data file p4smalltxt, containing a list of a few population records - county/state code, population in million, and county/state name separated by commas. Build an AVL search tree from the records of the input data file by inserting one record at a time to the tree. It then provides the following menu 1. Search for a record 2. Insert a record 3. Delete a record . List all records 5. Exit Your program will continue until the user wants to exit this program. For option 1, user will be prompted for the county/state code; if the record is found, display complete record. For option 2, user will be prompted to enter the population record on one line county/state code, city name, population, and county/state name. For option 3, user will be prompted for the county/state code. For option 4, you need to perform an in-order traversal and display one record per line (order by county/state code). In addition, your program would display the time it takes for options 1, 2, and 3, for the sake of this program, it would take one millisecond to examine one node in the tree (i.e., display that the search took 3 milliseconds when an element is found after 3 nodes were examined) Make sure to search, insert, and remove records for, to, and from different points of the tree (root, left, and right node) to show that your implementation is working properly. You need to create one separate class, AVLTree, which handles binary search tree of population records then create an application for doing above tasks using this binary search tree. Feel free to add additional classes (Entry, BinaryTree, BST, etc.) and it is recommended that your AVLTree class would be able to handle all different types of records with key-value pair (i.e., a C++ class template or a Java generic class)
Explanation / Answer
Program:
import java.util.Scanner;
