8
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ The link already answers your question — what more are you looking for? $\endgroup$
    – Yuval Filmus
    Apr 16 '15 at 22:16
  • $\begingroup$ Usually, search algorithms for a Binary Search Tree work with an AVL tree, but with an AVL you get the extra guarantee that your tree's height is logarithmic in the number of nodes. $\endgroup$
    – jmite
    Apr 17 '15 at 9:29
9
$\begingroup$

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)$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Could you please give me an example? $\endgroup$
    – Maksim Dmitriev
    Apr 18 '15 at 10:05
  • $\begingroup$ No, you'll have to construct one yourself. Try to understand what my algorithm is trying to accomplish and how. $\endgroup$
    – Yuval Filmus
    Apr 18 '15 at 14:40
  • $\begingroup$ My solution is on codereview.stackexchange.com/q/104525/23821 $\endgroup$
    – Maksim Dmitriev
    Sep 12 '15 at 20:49
  • $\begingroup$ Can you explain the logic behind this algorithm , I checked this method works but not able to figure out logic behind this . Specifically this part "we recurse to the right subtree, reducing k by L+1." Why aren't we reducing k when recursing left subtree . While the first two cases k ≤ L and k = L+1 are quite clear . $\endgroup$
    – user3798283
    Apr 12 '21 at 2:02
  • $\begingroup$ If $L=5$ then the seventh smallest element is the smallest element in the right subtree, with the third smallest element is the third smallest element in the left subtree. Can you see why? $\endgroup$
    – Yuval Filmus
    Apr 12 '21 at 6:04
0
$\begingroup$

AVL is binary search tree with some special property: it is self-balancing tree. It's height is always logarithmic. Ordinary binary tree in some worst scenario can be linked list (if you add sorted data) so it's height is n. AVL tree in worst scenario is fibonacci tree.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.