I have an AVL Tree which every node has a filed with a key which is an integer. I need to save a pointer to the Minimum , Maximum and the $\left \lfloor \frac{n}{4} \right \rfloor $ nodes. the first and the second were pretty easy i just saved a pointer between each node and its follow and back nodes. But i couldn't find a way to save the $\left \lfloor \frac{n}{4} \right \rfloor$ one. Any ideas? thank you.

  • $\begingroup$ Well, the duplicate tells you how to find elements of rank $k$. If you want to maintain a pointer (and not adapt the data structure in other ways), think about under what circumstances you would have to move the pointer, and where. So, assume the pointer is there (invariant); what do you have to do when elements are inserted or deleted? $\endgroup$
    – Raphael
    Jul 16 '15 at 12:17