$($c$)$ You are required to design an augmented Self$-$Balancing $($ AVL search tree or R$-$B Tree$)$

Binary Search Tree for computing the it th order statisties in $O(logn)$ time always. Maintain

one key plus some extra information per node in the tree. Answer the following:

i$.$ Show using appropriate example$($s$)$ that the running time of finding $i-$th order

statisties for a collection of keys arranged in the form of a self$-$balancing BST is

not $O(logn)$ if you do not properly augment some extra information in the BST$.$

ii$.$ Clearly state the extra information you atg required to store with each tree node

and how this information will be used to compute the i$-$th order statisties.

iii. Clearly design the procedure for finding the i$-$th smallest element in the tree. Your

procedure must only take care of outputting the $i-$th order statisties and not on

balancing the BST$.$