You will implement a population database for US counties and states using an AVL
ID: 3769496 • Letter: Y
Question
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 p4small.txt, containing a list of a few population records -- county/state code, population in million, and county/state 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
4. 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 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 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 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)
Explanation / Answer
program :
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
typedefstruct node
{
int data;
struct node *left,*right;
intht;
}node;
node *insert(node *,int);
node *Delete(node *,int);
void
preorder(node *);
void
inorder(node *);
int
height( node *);
node *rotateright(node *);
node *rotateleft(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int BF(node *);
int main()
{
node
*root=NULL;
intx,n,i,op;
do
{
printf(“n1)Create:”);
printf(“n2)Insert:”);
printf(“n3)Delete:”);
printf(“n4)Print:”);
printf(“n5)Quit:”);
printf(“nnEnter
Your Choice:”);
scanf(“%d”,&op);
switch(op)
{
case
1:printf(“nEnter no. of elements:”);
scanf(“%d”,&n);
printf(“nEnter
tree data:”);
root=NULL;
for(i=0;i<n;i++)
{
scanf(“%d”,&x);
root=insert(root,x);
}
break;
case
2:printf(“nEnter a data:”);
scanf(“%d”,&x);
root=insert(root,x);
break;
case
3:printf(“nEnter a data:”);
scanf(“%d”,&x);
root=Delete(root,x);
break;
case
4: printf(“nPreorder
sequence:n”);
preorder(root);
printf(“nnInorder
sequence:n”);
inorder(root);
printf(“n”);
break;
}
}while(op!=5);
return 0;
}
node * insert(node *T,int x)
{
if(T==NULL)
{
T=(node*)malloc(sizeof(node));
T->data=x;
T->left=NULL;
T->right=NULL;
}
else
if(x
> T->data)
{
T->right=insert(T->right,x);
if(BF(T)==-2)
if(x>T->right->data)
T=RR(T);
else
T=RL(T);
}
else
if(x<T->data)
{
T->left=insert(T->left,x);
if(BF(T)==2)
if(x
< T->left->data)
T=LL(T);
else
T=LR(T);
}
T->ht=height(T);
return(T);
}
node * Delete(node *T,int x)
{
node *p;
if(T==NULL)
{
return
NULL;
}
else
if(x
> T->data)
{
T->right=Delete(T->right,x);
if(BF(T)==2)
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else
if(x<T->data)
{
T->left=Delete(T->left,x);
if(BF(T)==-2)
if(BF(T->right)<=0)
T=RR(T);
else
T=RL(T);
}
else
{
if(T->right
!=NULL)
{
p=T->right;
while(p->left
!= NULL)
p=p->left;
T->data=p->data;
T->right=Delete(T->right,p->data);
if(BF(T)==2)
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else
return(T->left);
}
T->ht=height(T);
return(T);
}
int height(node *T)
{
intlh,rh;
if(T==NULL)
return(0);
if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;
if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;
if(lh>rh)
return(lh);
return(rh);
}
node * rotateright(node *x)
{
node
*y;
y=x->left;
x->left=y->right;
y->right=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node * rotateleft(node *x)
{
node
*y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node * RR(node *T)
{
T=rotateleft(T);
return(T);
}
node * LL(node *T)
{
T=rotateright(T);
return(T);
}
node * LR(node *T)
{
T->left=rotateleft(T->left);
T=rotateright(T);
return(T);
}
node * RL(node *T)
{
T->right=rotateright(T->right);
T=rotateleft(T);
return(T);
}
int BF(node *T)
{
intlh,rh;
if(T==NULL)
return(0);
if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;
if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;
return(lh-rh);
}
void preorder(node *T)
{
if(T!=NULL)
{
printf(“%d(Bf=%d)
“,T->data,BF(T));
preorder(T->left);
preorder(T->right);
}
}
void inorder(node *T)
{
if(T!=NULL)
{
inorder(T->left);
printf(“%d(Bf=%d)
“,T->data,BF(T));
inorder(T->right);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.