Assignment 3 balanced binary trees

Assignment 3
Objectives
In this assignment, you will gain a deeper familiarity with balanced binary trees. Your solution
should use a balanced binary tree (such as AVL Tree) but researching another balanced binary
tree and implementing it is allowed.
Beware: The binary search tree shown in class had a bug in delete. Find a way to fix this or
implement a better delete. The tree in this problem is also not a search tree.
Deliverables
Submit two files.
The file named “fancy.h” is your header file. Place all function declarations in this header with
comments on how you designed the header. You may use the header I provide or design your
own. In either case, include a header.
The file named is “fancy.c” is your source file. Implement all functions defined in the header
file. Include a main function in this file.
All input should be read from a file named “fancy.txt”. The input specification will define
precisely what is allowed for input to your program. You need not guard against cases not
allowed in the input.
Scoring
I will run your program multiple times on multiple test files. Your grade will be awarded based
on the number of tests you pass with some points allocated to fulfilling the special
requirements for sorting. Be sure to test your program on more than just the sample cases
provided.
To guard against infinite loops and inefficient implementations, your program will be run for 𝑥𝑥
seconds per test case. Upon grading, you will receive a “results.txt” file detailing which tests
where passed and which failed. Here is a table of possible results:
Error Code Meaning
AC Accepted! :D All is wonderful in the world and your code worked correctly.
WA Wrong Answer: The code executed but produced faulty output.
RTE Runtime Error: The code crashed spewing memory and guts everywhere.
TLE Time Limit Exceeded: I killed the program after 𝑥𝑥 seconds. I feel betrayed.
CTE Compile Time Error: Your code did not compile. 
Fancy Array
filename: fancy
timelimit: 3 seconds
In this problem, you will implement a fancy version of an array using a binary search tree. We
want a data structure that can do each of the following:
• Insert some integer into position 𝑖𝑖 (sliding all values at 𝑗𝑗 where 𝑖𝑖 ≤ 𝑗𝑗 to the right)
• Delete some integer from position 𝑖𝑖 (sliding all values at 𝑗𝑗 where 𝑖𝑖 < 𝑗𝑗 to the left)
• Obtain the value at index 𝑖𝑖.
Each of these operations should work in 𝑂𝑂(log 𝑛𝑛) worst case runtime. (This is why it is a fancy
array.)
Input “fancy.txt”
The first line of input contains a single integer 𝑛𝑛 (1 ≤ 𝑛𝑛 ≤ 106) representing the number of
operations to process.
This is followed by 𝑛𝑛 lines, with one operation per line.
• valueat 𝑖𝑖 (print the value at position 𝑖𝑖 in the array, print “error” if no such value exists)
• insert 𝑖𝑖 𝑣𝑣 (insert the value 𝑣𝑣 into position 𝑖𝑖 in the array)
• delete 𝑖𝑖 (delete the value at position 𝑖𝑖 from the array)
If the current array size is 𝑚𝑚, you may assume that 𝑖𝑖 in the valueat and delete command will be
an integer in the range [0, 𝑚𝑚 − 1]. You may assume that position 𝑖𝑖 in an insert will be in the
range [0, 𝑚𝑚]. The value of 𝑣𝑣, inserted into the array, will be an integer in the range [−109, 109].
Output (stdout)
Output one line for each 𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣𝑣 command, the value at that position in the array when the
command was issued.
Sample 1
Input 8
insert 0 1
insert 0 2
insert 0 3
insert 0 4
delete 2
valueat 0
valueat 1
valueat 2
Output 4
3
1
Sample 2
Input 22
insert 0 1
insert 1 2
insert 1 4
insert 3 3
insert 2 5
valueat 0
valueat 1
valueat 2
valueat 3
valueat 4
delete 2
valueat 2
valueat 3
delete 0
valueat 0
delete 0
valueat 0
delete 0
valueat 0
delete 0
insert 0 100
valueat 0
Output 1
4
5
2
3
2
3
4
2
3
100
Tips
To balance AVL Trees you can store and maintain height information in your tree. To
implement the indexing, you can store the size of each subtree. Here the size is the number of
nodes in that subtree. Think about how this helps you find the 𝑖𝑖
𝑡𝑡ℎ node.