TAOCP 6.2.2 Exercise 19
Let $N$ keys be inserted in random order into a binary search tree generated by Algorithm T.
Section 6.2.2: Binary Tree Searching
Exercise 19. [M23] [M23] What is the approximate average number of comparisons, (11), when the input probabilities satisfy the 80-20 law defined in Eq. 6.1, (11)?
Verified: yes
Solve time: 1m23s
Solution
Let $N$ keys be inserted in random order into a binary search tree generated by Algorithm T. For a successful search, the number of comparisons for a key is $d(x)+1$, where $d(x)$ is the depth of node $x$ in the resulting tree. The average number of comparisons is therefore
$$ C_N = 1 + \sum_{x} p_x , \mathbb{E}[d(x)], $$
where $p_x$ is the access probability of key $x$.
Under the 80-20 law of Eq. 6.1-(11), the set of keys is split into two classes: a subset $H$ of size $0.2N$ carrying total probability $0.8$, and a subset $L$ of size $0.8N$ carrying total probability $0.2$. Hence
$$ p_x = \begin{cases} \frac{0.8}{0.2N} = \frac{4}{N}, & x \in H,\[6pt] \frac{0.2}{0.8N} = \frac{1}{4N}, & x \in L. \end{cases} $$
Thus
$$ C_N = 1 + \frac{4}{N} \sum_{x \in H} \mathbb{E}[d(x)] + \frac{1}{4N} \sum_{x \in L} \mathbb{E}[d(x)]. $$
For a random binary search tree built from a random permutation of $N$ keys, the expected internal path length satisfies
$$ \sum_{x} \mathbb{E}[d(x)] = 2N \ln N + O(N), $$
and symmetry of the random insertion model implies that, averaged over any fixed subset of linear size, the mean depth per node differs from the global mean only by $O(1)$. Hence
$$ \frac{1}{N} \sum_{x \in H} \mathbb{E}[d(x)] = 2 \ln N + O(1), \qquad \frac{1}{N} \sum_{x \in L} \mathbb{E}[d(x)] = 2 \ln N + O(1). $$
Substituting these expressions gives
$$ C_N = 1 + 4 \cdot 0.2 , (2 \ln N + O(1)) + \frac{1}{4} \cdot 0.8 , (2 \ln N + O(1)). $$
The coefficients satisfy $4 \cdot 0.2 = 0.8$ and $\frac{1}{4} \cdot 0.8 = 0.2$, so
$$ C_N = 1 + (0.8 + 0.2)(2 \ln N + O(1)) = 1 + 2 \ln N + O(1). $$
The additive constant is absorbed into the $O(1)$ term, so the dominant term is independent of the skew introduced by the 80-20 distribution.
Therefore the approximate average number of comparisons is
$$ \boxed{2 \ln N}. $$
This completes the derivation. ∎