TAOCP 6.2.2 Exercise 20

Let the search tree be built by inserting keys in the order $K_1, K_2, \dots, K_n$, where the access probabilities satisfy $p_1 > p_2 > \cdots > p_n.$ The structure of Algorithm $T$ depends only on ke...

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.2.2: Binary Tree Searching

Exercise 20. [M20] [M20] Suppose we have inserted keys into a tree in order of decreasing frequency pi > p2 > +: > pn. Can this tree be substantially worse than the optimum search tree?

Verified: yes
Solve time: 1m28s

Solution

Let the search tree be built by inserting keys in the order $K_1, K_2, \dots, K_n$, where the access probabilities satisfy

$p_1 > p_2 > \cdots > p_n.$

The structure of Algorithm $T$ depends only on key comparisons, not on probabilities. Hence the tree shape is determined entirely by the relative order of the keys $K_1,\dots,K_n$ in the key space.

Assume the worst alignment between probability order and key order, namely that the keys are such that insertion in the order $K_1, K_2, \dots, K_n$ produces a completely skew tree (for instance, $KEY(K_1) < KEY(K_2) < \cdots < KEY(K_n)$). Then each insertion goes to the right child of the previous node, and the resulting binary search tree is a chain of length $n$.

In this tree, the node containing $K_i$ lies at level $i-1$ when the root is at level $0$. A successful search for $K_i$ therefore requires exactly $i$ comparisons.

The expected number of comparisons is therefore

$C = \sum_{i=1}^n i p_i.$

Choose a concrete decreasing distribution satisfying the hypothesis:

$p_i = \frac{1}{i H_n}, \quad \text{where } H_n = \sum_{k=1}^n \frac{1}{k}.$

This sequence satisfies $p_1 > p_2 > \cdots > p_n$ and $\sum_{i=1}^n p_i = 1$.

For this distribution, the cost becomes

$C = \sum_{i=1}^n i \cdot \frac{1}{i H_n} = \sum_{i=1}^n \frac{1}{H_n} = \frac{n}{H_n}.$

Since $H_n = \ln n + O(1)$, this yields

$C = \Theta!\left(\frac{n}{\log n}\right).$

The optimum binary search tree for a fixed probability distribution has expected cost bounded by standard information-theoretic lower bounds:

$C_{\min} \ge H(p_1,\dots,p_n) = \sum_{i=1}^n p_i \lg \frac{1}{p_i}.$

For $p_i = \frac{1}{i H_n}$,

= \frac{1}{H_n} \left(\sum_{i=1}^n \frac{\lg i}{i} + \lg H_n \sum_{i=1}^n \frac{1}{i}\right).$$ The second term simplifies to $\lg H_n$, and the first term is $O(\lg^2 n)$, hence $$H(p_1,\dots,p_n) = O(\lg n).$$ Thus the optimum search tree achieves expected cost $O(\log n)$, while the tree produced by insertion order of decreasing probabilities can have expected cost $\Theta(n/\log n)$. Therefore the ratio between the cost of the resulting tree and the optimal search tree can grow without bound as $n \to \infty$, so the tree can be substantially worse than optimal. This completes the proof. ∎