If you are allowed an extra integer per node, then you can maintain in each node a count of the number of nodes in the subtree rooted at that node. This can be maintained at no additional asymptotic cost in the insert, delete, and balance operations (if you're balancing).
With these counts in each node, it is easy to find the median at any time in O(log n) time. In fact you can find the k'th element for any k. Conversely, you can find any element using its search key (in O(log n) time) and at no extra cost get, k, which in this case is called the key's order statistic. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/H9Fq-cazLdkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
