# Probability of comparison of two nodes after insertion in AVL tree

Suppose $$K=a_1 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.

• What's the motivation for the question? Jan 26 at 17:49

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$$.
• 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}]$. Jan 26 at 17:40