$.$ In class, we discussed the on$-$line kth largest problem. We solved it$,$ using an augmented AVL$-$tree structure, with the following characteristics:

Insert$($x$)$ in time and space O$($log$2$n$)$ where n is the number of elements in the structure at this time $($i$.$e$.,$ the number of insert operations, minus the number of Delete operations, up until now.$)$

Delete$($x$)$ in time space O$($log$2$n$)$where n is the number$$ of elements in the structure at this time$($i$.$e$.,$ the number of insert operations, minus the number of Delete operations, up until now.$)$

Find$($k$)$ in time O$($log$2$n$)$ and space O$(1)$ where n is the number of elements in the structure at this time. $($i$.$e$.,$ the number of insert operations, minus the number of Delete operations, up until now.$)$

Suppose that instead of doing the find$($k$)$ operation, with k an arbitrary positive

An integer that can vary from one Find to the next, we replace it by

Find$[$n$/4]$

Where n is the number of all elements that are currently stored in the structure. Can you devise a data structure and algorithms for$$

Insert$($x$)$

Delete$($x$)$

Find$([$n$/4])$

Which improve over Find$($k$)$ approach discussed in class $($Obviously$,$ that approach will still apply, so we know that all three operation can certainly be done in time and space O$($log$2$n$)$;however, the question for you to solve is: Can you do better??$)$

Carefully formulate your data structure $,$ outline the three algorithms in some detail, and determine with care the time and space complexities of your three algorithms.

$($If your structures$/$algorithms are based on standard structures$/$algorithms$,$ emphasize in what way yours are different. Do not repeat everything!$)$