0
$\begingroup$

So theres the classic problem of finding the median in an AVL BST in O(log(n))* However given two AVLs, each having N different values (all values in both trees combined would be 2N different values) how would one find the median** in O(log(n))?

edit: Nodes can have the size of the subtree in each node like in *

I've been given a hint: Let one of the trees be A and the other B, and let AL denote the left subtree of A, and so on for AR BL BR. In O(1), rule out the existance of the median in one of the subtrees.

edit: so far I have this:

let X=min{tree roots}, Y=max{tree roots}  
|YR|+|XR|>=n   => XL is out 
|XL|+|YL|>=n-1 => YR is out

as far as I can tell, this holds well and is O(1). I'm not too sure how to proceed from here.

Thoughts and hints would be appreciated!

for further clarification, the trees are like in the last page of: https://courses.csail.mit.edu/6.006/spring11/rec/rec04.pdf

*by storing the size of the subtree in each node, this is simple enough

**the median here is defined as the Nth key if they were to be layed out sorted from low to high.

$\endgroup$
  • $\begingroup$ How would you do it if each node was augmented with its rank in the tree? What can be said about the rank of the root of a (sub-)tree obeying the AVL balance criterion? $\endgroup$ – greybeard May 22 '18 at 16:22
  • $\begingroup$ by rank im assuming you mean the position of the node key if they were to be sorted. I can tell that the rank of the root is lower bound by 2^(L+1)-1 and upper bound by 2^(L+2)-1 or vice verse but its not very specific, how would that help me get rid of a sub tree? sorry if this seems trivial, i just dont see it. $\endgroup$ – alphil May 23 '18 at 7:02
  • $\begingroup$ I just don't see it same here, but then, you wrote Thoughts [& hints] appreciated. For peace of mind, I nourish my inkling that the problem statement is off (incomplete preconditions (for whole problem or O(1) [ruling out one of four] subtrees)). Please be sure to add a/the resolution, if any. $\endgroup$ – greybeard May 23 '18 at 7:36
  • $\begingroup$ (It would be trivial, too, if the balance criterion was weight may differ by one, tops in stead of height.) $\endgroup$ – greybeard May 23 '18 at 7:43
  • $\begingroup$ storing the rank is allowed (my original intention was that the first asterisk was allowed to be used on the new problem, however rank is equivalent in the case of a single tree). other than that, though, this is the problem as stated... $\endgroup$ – alphil May 23 '18 at 9:54

Your Answer

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

Browse other questions tagged or ask your own question.