0
$\begingroup$

Suppose $K=a_1<a_2<\dots<a_n$ be a set $n$ distinct keys that inserted into an AVL tree $T$. The probability of any permutation of the order of insertion of the sequence $K$ is equal. Also we first insert $a_{40}$ into $T$, how I can find the probability, $a_4$ be ancestor of $a_9$ or $a_9$ be ancestor of $a_4$?

Anyone can give me some hint? I try to find some hint about that.

Improve this question
$\endgroup$
1
  • $\begingroup$ What's the motivation for the question? $\endgroup$
    – jbapple
    Jan 26 at 17:49

1 Answer 1

Reset to default
0
$\begingroup$

When inserting into an AVL tree, the existing nodes are not compared with each other, so the probability of comparing $a_4$ and $a_9$ with each other when inserting $a_{40}$ is $0$.

On the other hand, the probability of comparing $a_{n}$ to both $a_4$ and $a_9$ is derivable asymptotically by considering how many comparisons one makes when doing an insert, which is $O(\lg n)$, making the total probability $O((\lg n/n)^2)$, which is very small - $o(1/n)$.

However, that's true only asymptotically. To get the result for $n = 40$, you have to analyze the expected number of comparisons when inserting into a tree of size $39$. That probably requires some heavier math.

To see how this can change, consider the probability of comparing $a_3$ to both $a_1$ and $a_2$ when inserting $a_3$, which I think is $2/3$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think you might have misunderstood the question. My understanding (which I'm not entirely sure of) is the following. We insert $a_1< \ldots < a_n$ in the AVL tree in random order. Let $A$ be the event that $a_4$ is an ancestor of $a_9$ or $a_9$ is an ancestor of $a_4$ in the resulting AVL tree (after all insertions are done). The question is $\Pr[A \mid \text{$a_{40}$ is the first element to be inserted into the AVL tree}]$. $\endgroup$
    – Dmitry
    Jan 26 at 17:40
  • $\begingroup$ Oh, I was answering an earlier version of the question, before your edit. Oops. $\endgroup$
    – jbapple
    Jan 26 at 17:48
  • $\begingroup$ (Just would like to clarify that I didn't edit the post, in particular because I was not sure about what's asked) $\endgroup$
    – Dmitry
    Jan 26 at 17:50
  • $\begingroup$ Oops, I meant before @Mohammed.Rostami edited the post. $\endgroup$
    – jbapple
    Jan 26 at 17:54

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.