1
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by Raphael Jul 16 '15 at 12:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\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