Q1. [10] Balanced Binary Search Tree

Write an algorithms min() and max(), which return the key-value pair (k, e) with smallest and largest key, respectively, in O(log n) time in the balanced binary search tree.

Q2. [10] AVL Tree

Consider the insertion of the following keys (in the given order) into an initially empty AVL tree:

15, 45, 55, 35, 25, 40, 10. Draw the final AVL tree.

Q3. [10] AVL Tree

Draw the AVL tree resulting from the removal of the key 40 from the AVL tree of Figure below.

Q4. [10] AVL Tree

Professor Amadeus claims that the order of keys to be inserted into an AVL tree does not matter; i.e. the same tree always results every time. Give a counter example that contradicts Prof. Amadeuss claim.

Q5. [Optional, 10] AVL Tree

Draw an example of an AVL tree such that a single remove operation could require Q(log n) trinode restructurings (i.e. rotations) from a leaf to the root in order to restore the height-balance property.

Q6. [20] Red-Black Tree

[10] Draw the Red-Black tree after each insertion of 35 and 40 into the given RB-tree above.

[10] In the given Red-Black Tree above, draw the resulting Red-Black tree after deleting 10..

Q7. [30] Minimum Heap

In the array A[1..10] that stores the elements [35, 30, 25, 27, 22, 20, 18, 15, 10, 5],

Construct a min-heap in the array A. Draw the final heap.

Draw the min-heap after removing Minimum key in 2).

From the min-heap in 2), sort the array A in the descending order. Show the content of array A after sorting five smallest keys.

Q8. [10] Heap Sort

A maximum heap is used to sort an array A of length n in ascending order.

What is the running time of Heap-Sort algorithm on an array A that is already sorted in ascending order? Explain your answer.