Description
Question 1 – 25 points
(a) [5 points] Draw all valid min-heaps containing these 4 elements 5, 7, 6, 1.
(b) [5 points] How many valid max-heaps containing 5 distinct elements can be built?
(c) [10 points] This question has three subparts which follow one another.
i. Insert 46, 59, 51, 31, 68, 63, 25, 75, 40 to an empty AVL tree, in the given
order. Show only the final tree after all insertions.
ii. Add one more element such that it causes a single right rotation in the tree.
Show the final tree after the insertion.
iii. Insert 1; to the AVL tree. Now, delete one element such that it causes a single
left rotation in the tree. State the deleted number and show the final tree after the
deletion operation.
(d) [5 points] True or false: “Insertion order of the same set of elements into an AVL
tree affects the resulting tree structure”.
If yes, why; if not, provide a counter-example.
Question 2 – 25 points
Implement AVL tree data structure named as AVLTree for maintaining a list of integer
keys with the following methods:
void insert(int value); //inserts an element into the tree
int getNumberOfRotations(); //returns the number of rotations performed so far
while constructing the AVL tree
After that you will analyze the average number of rotations and determine if different
patterns of insertion affect it. Write a global function, void rotationAnalysis()
which does the following:
(a) Creates 1000 random numbers in the range [1,100000] and inserts them into an
empty AVL tree. While inserting elements into the AVL tree, it counts the number of
rotations and it outputs the total number of rotations in the end. Repeat the experiment
for the following sizes: {2000, 3000, 4000,…, 10000}
(b) Instead of creating arrays of random integers, create arrays with elements in the
same range in ascending order and repeat the steps in part (a).
(c) Instead of creating arrays of random integers, create arrays with elements in the
same range in descending order and repeat the steps in part (a).
Put function’s code into analysis.h and analysis.cpp files. Create a main.cpp
file which calls rotationAnalysis() function. When the rotationAnalysis()
function is called, it needs to produce an output similar to the following one:
Array Size Random Ascending Descending
1000 x x x
2000 x x x
3000 x x x
… x x x
After running your program, you are expected to prepare a report about the
experimental results that you obtained in Question 2. In your report, you need to discuss
the following points:
● Do your findings related to average number of rotations in the AVL tree agree
with theoretical results?
● Do different patterns of insertion affect the number of rotations in the AVL tree? If
so, explain how. If not, explain why not.
Question 3 – 50 points
Caezar, the leader of the Planet of the Apes, gained his intelligence from the ALZ – 112
drug and since then he has been learning computer science and hacking. A few days
ago he visited Bilkent and hacked into your computers while you were practicing heaps.
He takes the leaves of the heap that you have built from a given file and permutes them
by picking a permutation uniformly at random. If the heap properties are not satisfied
after the permutation, you need to fix the heap with appropriate methods. He also offers
you a deal where he will either pay 10TL for each swap operation that you perform in
the course of fixing the heap, or a 20 TL ALL worth treat (independently of the count).
You need to write a program for a given file containing integers advising you about the
best deal for you.
You need to implement a MaxHeap class which includes its appropriate methods and
permutation(…)method. In main.cpp class you should take the input from a file
named “input.txt” and build the heap by using the implemented methods. After that
you need to generate every permutation of the leaves and sum up the total number of
swaps that is done for each case. Then you need to compute the average number of
swaps and choose the betterdeal accordingly.
Sample input:
Note: The first line of input contains N – the number of nodes and the second line
contains N unique integers from which a max heap is to be built.
Sample output:
Note: You can print “10 TL per swap is a better option” for the other case.