In this assignment you will build many BST trees where each tree has a name. To store thenames of all the trees, you will maintain a binary search tree for the tree names.After building the trees, you will have to perform a set of operations and queries.Here is an example. In this example fish, animal, bird, and fruit are part of the name BST.Each node of the name tree points to a BST of items. Here, the fish node points to a BST thatcontains name and count of fishes. Note that all the green colored nodes are of same type ofnode structure and all the black colored nodes are of same type of node structure.Input Specification:You have to read the inputs from standard input using scanfs (No file I/O). There will bemany strings in the inputs and you can assume that all the strings will be lower case letterand the maximum length of a string is 30 character. For simplicity, use static array of char tostore a string.The first line of the input contains three integers N, I, and Q, where N represents number ofTree Names,
I
represents the total number of items in the list to be inserted to all the trees,and Q represents the number of queries listed in the inputs.After the first line, next N lines will contain the list of Names of the trees and you need toinsert them to a Name tree.
Next,
I
lines will contain the list of items to be inserted in different trees. Each line of the list
contains two strings and one integer. The first string contains the name of that tree, second
string contains the item name, and then the last integer contains the count of that item. You
have to insert the item in the tree with that tree name. You need to use the item name as the
key to the BST. Also note that the item count needs to be added to the node as well.
[Assumption: You can assume that a tree name as well as an item name will not be repeated
in the input]
After the
I
lines, the next Q lines will contain a set of queries and you need to process them.
Here is the list of queries:
•
find:
search for a particular item in a given tree and display the count of the item if it
is found. Otherwise, prints item not found. However, if the tree does not exist, then it
prints tree does not exist
o
[Example:
find fruit avocado
should search for avocado in the fruit tree and
then prints the count of avocado. If the fruit tree exists, but the avocado does
not exist, it should print “not found”. However, if fruit tree does not exist, then
it should print tree does not exist.
•
count_before:
this command counts the items in a given tree coming before a given
item name (alphabetically).
o
[For example, if your query is like this
count_before animal deer,
it should
print 4 as cat, bear, alligator, and cow come before deer alphabetically.]
•
check_balance:
It finds whether a given tree is height balanced or not. In order to do
that, you need to know the height of left
sub tree
and then height of right
sub tree
. If
their height
difference’s absolute
value
is more than 1, then we say the tree is
imbalanced. In this assignment, a tree with 1 node, will be consider as height 0, and a
tree with no node will be considered as height -1.
o
[Example:
check_balance animal,
will print, left height 1, right height 3,
difference 2, not balanced]
•
count:
this command prints the total number of items in a given tree.
o
[Example:
count animal,
should print 142 (as 30 + 20+ 10 +50 +3 + 3 +5 +15
= 142)]
•
decrease:
this command reduces the count of an item in a given tree. The min value
of the count needs to be >0. So, if it becomes <=0, you="" need="" to="" delete="" the="">
o
[Example:
decrease fruit mango
50 will reduce the total mango to 50 from
100.]
o
[Another Example:
decrease goldfish 50
will delete the node as goldfish is
reduced to 0]
•
remove:
this command deletes an item from a given tree.
o
[Example:
remove fruit avocado
will delete the avocado node from the fruit
tree]
•
delete_name:
this command delete the entire tree of a given name.
o
[Example:
delete_name animal
will delete the animal tree as well as animal
node from the name tree]
Sample Input:
4
28 21
fish
animal
bird
fruit
animal cat 30
fish goldfish 50
animal dog 20
bird blackbird 10
animal bear 10
fruit mango 100
animal alligator 50
animal tiger 3
animal lion 3
fish swordfish 10
animal deer 5
animal cow 15
fish garfish 5
fish catfish 55
fish salmon 40
bird crow 20
bird dove 10
bird flamingo 15
fruit apple 50
fruit banana 50
fruit nectarine 10
fruit coconut 10
fruit peach 40
fruit apricot 30
fruit avocado 25
fruit cherry 100
fruit cranberry 100
animal horse 6
find fruit avocado
find fish tilapia
find animal cow
find bird crow
find bird cow
find animal cat
count_before animal deer
check_balance animal
check_balance bird
check_balance fish
find flower rose
count animal
count fruit
remove animal cat
find animal cat
count animal
remove fish swordfish
remove fruit avocado
delete_name animal
decrease fruit mango 50
find fruit mango
Output Specification:
You have to write all the output to an
out.txt
file as well
as to the console
. You are allowed
to use a global variable for outfile pointer to simplify your function parameters. However,
note that, if your code does not print in standard console, you may get zero.
After building the tree, you should print the trees in inorder in the specified format shown in
the sample output below.
Sample Output:
animal bird fish fruit
###animal###
alligator bear cat cow deer dog horse lion tiger
###bird###
blackbird crow dove flamingo
###fish###
catfish garfish goldfish salmon swordfish
###fruit###
apple
apricot
avocado
banana
cherry
coconut
cranberry
mango
nectarine peach
25 avocado found in fruit
tilapia not found in fish
15 cow found in animal
20 crow found in bird
cow not found in bird
30 cat found in animal
item before deer: 4
animal:
left height
1, right height 3,
difference
2,
not balanced
bird: left height -1, right height 2,
difference 3, not balanced
fish: left height 1,
right
height 1, difference 0,
balanced
flower does not exist
animal count 142
fruit count 515
cat deleted from animal
cat not
found
in animal
animal count 112
swordfish deleted from fish
avocado
deleted from
fruit
animal deleted
mango reduced
50 mango
found
in fruit
Implementation Restriction.:
1.
You have to use the following structure. You are allowed to modify the structure if needed.
typedef struct itemNode
{
char
name[MAXLEN];
int
count;
struct
itemNode
*left,
*right;
}itemNode;
typedef
struct
treeNameNode
{
char
treeName[MAXLEN];
struct
treeNameNode
*left,
*right;
itemNode
*theTree;
}treeNameNode;
2.In
addition
to
typical
functions
of
tree
implementation,
you
must
have
to
implement
the
following
functions:
i.
createTreeNameNode()
ii.
treeNameNode*
buildNameTree(.....): Based on the data in the file, it will insert
them to the name tree and then finally return the root of the name tree
iii.
traverse_in_traverse(treeNameNode
*root):
this function takes the root of the name tree
and prints the data of the name tree and the corresponding item trees in the format shown in the sample
output. You can call other function from this function as needed.
iv.
treeNameNode * searchNameNode(treeNameNode * root, char treeName[50]):
This
function takes a name string and search this name in the name tree and returns that node.
This
function will help you a lot to go to the item tree.
v.
Note that you might need to crate separate insertion and other functions for name tree and item tree. [I
mean only two insertion function.]
vi.
All the numbers and output must be produced from the trees.
Before
starting
the
assignment,
make
sure
you
review
and
have
aclear
understanding
of
the
Binary
tree
topics,
insertion
and
code,deletion
and
code,
BST
practice
problems
and
related
codes.•
Always
start
as
soon
as
possible
as
they
might
take
time
and
youwill
face
various
issues
during
this
process.•
Read
the
complete
instructions
first.
It
is
always
a
good
idea
toplan
it
and
do
some
paperwork
to
understand
the
problem.•
Analyze
sample
input
output
and
match
them
with
the
description
andthe
tree.•
You
can
use
the
uploaded
BST
code,
and
practice
problem
codes.
But
youwill have to significantly
modify them•
Use strcmp() function for
string
comparison.•
Just
start
by
building
the
name
tree
first
and
see
the
inordertraversal of it•
Then gradually
build
the other trees and test them
as
you go.•
Create
functions
to
simplify
your
code
and
it
will
be
easier
to
testyour code, disable part of
your
code,
etc.•
Use
the
discussion
board
for
any
question,
so
that
others
also
getbenefited from
your
question and
answer.•
Keep patience
and take help from
us when you
get stuck :)Your code must compile in codegrade Platform. If it does not compile in codegrade, we conclude thatyour code does not compile even if it works in your computer.Steps to check your output AUTOMATICALLY in repl.it or other command line based compiler:You can run the following commands to check whether your output is exactly matching with the sampleoutput or not.Step1:
Copy the sample output into sample_out.txt file and move it to the server (you can make yourown sample_out.txt file)Step2:
compile and run your code using typical gcc and other commands. Your code should produceout.txt file.$gcc
main.c
leak_detector_c.c$./a.out
<>Step3:
Run the following command to compare your out.txt file with the sample output file$diff
-i
out.txt
sample_out.txtThe command will not produce any output if the files contain exactly same data. Otherwise, it will tellyou the lines with mismatches.Incase if your code does not match, you can use the following command to see the result in side by side:
$diff
-y
out.txt
sample_out.txt