Description
Problem 1
Implement an AVL Tree with the following operations it supports –

Find: Finds whether a given key k is present a given AVL Tree

Add: Inserts a given key k into the given AVL Tree. This operation needs you to appropriately implement the rotate operations which happen during the insertion phase. For doing this, you must keep an additional field at each and every node which can contain 0, 1 or 1 to indicate height balance of the node.

Construct: Calls insert operation repeatedly for a given list of elements one after the other to construct a fresh AVL Tree.

Measure: Measure the time spend during rotations using the time function.
You can use the following table to design your functions. You can also refer to the sample input and output case provided.
Key 
Function 
Input Format 
Description 

0 
readData 
0 N 
Reads the next N lines containing N keys and stores them into 

k1 
an array of size N called Arr. 

k2 

k3 

… 

kN 

1 
add 
1 k 
Inserts the given key k into the AVL Tree. 

2 
construct 
2 
Initializes an empty AVL tree and inserts all the elements of 

Arr into it, in the same order as they were inserted into Arr. 

3 
find 
3 k 
Finds whether a given key k exists in the AVL tree. Prints 1 if 

found, 0 otherwise. 

4 
measure 
4 
Measures the total time taken in rotations during the 

construction and prints it. 

Sample input and output – 1 

Sample Input 
Sample Output 

0 4 
0 

40 
1 

23 
<total time> 

35 

43 

2 

3 33 

3 35 

4 

1 

1  P a g e 