A median of an AVL. How to take advantage of the AVL?

Problem Detail: 

Here is the source of my question.

Given a self-balancing tree (AVL), code a method that returns the median.

(Median: the numerical value separating the higher half of a data sample from the lower half. Example: if the series is

2, 7, 4, 9, 1, 5, 8, 3, 6

then the median is 5.)

I can offer the following solution:

1. Traverse the given tree, return the number of elements.
2. Traverse n / 2 + 1 (if n is odd) the tree again applying an in-order tree walk. The value of the n / 2 + 1th element is the median.

But I can do it with a binary search tree, can't I? Is there a better algorithm for an AVL?

Asked By : Maksim Dmitriev

Answered By : Yuval Filmus

If you modify the AVL tree by storing the size of the subtree at each node rather than just its height, then you can find the median in time $O(\log n)$ using the fact that the tree is balanced. To accomplish this, you write a more general procedure Select which accepts a node $v$ and a number $k$, and finds the $k$th smallest node at the subtree rooted at $v$.

Suppose that the left subtree (if any) has $L$ nodes. If $k \leq L$ then we recurse to the left subtree. If $k = L+1$ then we return $v$. Otherwise we recurse to the right subtree, reducing $k$ by $L+1$.

The running time of this algorithm is linear in the height of the tree, which is $O(\log n)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41473