TAOCP 6.2.2 Exercise 29

Let the 31 keys be the most common English words in Fig.

taocpmathematicsalgorithmsvolume-3project

Section 6.2.2: Binary Tree Searching

Exercise 29. [40] [40] What is the worst possible binary search tree for the 31 most common English words, using the frequency data of Fig. 12?

Verified: no
Solve time: 4m36s

Corrected Solution

Let the 31 keys be the most common English words in Fig. 12, ordered lexicographically as

$$ K_1 < K_2 < \cdots < K_{31}, $$

with positive successful-search frequencies $f_1,\dots,f_{31}$.

For a BST $T$, let $\mathrm{depth}(K_i)$ be the number of edges from the root. The cost is

$$ C(T)=\sum_{i=1}^{31} f_i(\mathrm{depth}(K_i)+1). $$

Since $\sum f_i$ is constant, we maximize

$$ W(T)=\sum_{i=1}^{31} f_i,\mathrm{depth}(K_i). $$

1. A correct rotation argument

Consider a BST and a standard right or left rotation.

Let $x$ be a node with right child $y$, and let $A$ be the left subtree of $y$:

$$ x \rightarrow y,\quad A = \text{left}(y). $$

After a left rotation at $x$:

  • $y$ moves up one level, so $\mathrm{depth}(y)$ decreases by $1$,
  • $x$ moves down one level, so $\mathrm{depth}(x)$ increases by $1$,
  • every node in $A$ remains attached below $y$ and does not change depth,
  • all other nodes are unchanged.

Therefore the change in weighted cost is

$$ \Delta W = f_x - f_y. $$

Key consequence

A rotation improves the objective iff $f_x > f_y$.

Thus rotations do not generically increase cost; they only swap relative depths of adjacent nodes according to frequency ordering. In particular, the previous claim that all non-chains can be improved was incorrect.

2. Correct structural principle

We now determine the true structure of a worst BST.

Observe that in any BST, along any root-to-leaf path, keys appear in strictly increasing or decreasing lexicographic order depending on whether we move right or left.

However, the objective

$$ W(T)=\sum f_i \cdot \mathrm{depth}(K_i) $$

is maximized when high-frequency keys are placed as deep as possible, since depth only increases cost.

Lemma 1 (Depth monotonicity constraint)

In any BST, the root has minimum depth $0$, and every other node has depth at least $1$. Increasing depth of any node by one increases $W(T)$ by exactly $f_i$.

Thus, to maximize $W(T)$, we want to maximize total depth sums subject to BST constraints.

3. Characterization of maximal-depth BSTs

A BST on fixed keys has maximum possible total depth when it is as unbalanced as possible, i.e., a chain.

Lemma 2 (Maximum total depth is achieved by chains)

Among all BSTs on $n$ fixed keys, the maximum possible value of

$$ \sum_{i=1}^n \mathrm{depth}(K_i) $$

is achieved exactly by degenerate trees (chains), since each branching event moves at least one node closer to the root and reduces total depth.

Therefore, to maximize $W(T)$, we must use a chain.

This is independent of frequencies: any branching reduces total depth of some nodes relative to a chain configuration.

4. Reduction to two candidate trees

A BST chain must respect inorder ordering. Therefore there are exactly two possible shapes:

Right-skewed chain

$$ K_1 \to K_2 \to \cdots \to K_{31}, \quad \mathrm{depth}(K_i)=i-1. $$

Left-skewed chain

$$ K_{31} \to K_{30} \to \cdots \to K_1, \quad \mathrm{depth}(K_i)=31-i. $$

5. Cost comparison

Right chain:

$$ W_R = \sum_{i=1}^{31} f_i(i-1). $$

Left chain:

$$ W_L = \sum_{i=1}^{31} f_i(31-i). $$

Subtract:

$$ W_R - W_L = \sum_{i=1}^{31} f_i(2i-32). $$

Let

$$ S=\sum_{i=1}^{31} (2i-32)f_i. $$

6. Using the frequency structure of Fig. 12

From Fig. 12 (Knuth), the dominant property is that the highest-frequency words are heavily concentrated among the very common function words such as:

  • “the”
  • “of”
  • “and”
  • “to”
  • “a”

In the standard ordering used in Fig. 12, these high-frequency words occur in the middle-to-late lexicographic positions rather than near $K_1$.

The coefficients $2i-32$ satisfy:

  • negative for $i \le 15$,
  • positive for $i \ge 17$,
  • symmetric around the center.

Thus $S$ is positive if and only if more total frequency weight lies in higher-index positions.

From Fig. 12, the cumulative frequency mass is dominated by words whose indices are above the midpoint, especially “the,” which lies in the positive-coefficient region and has the largest weight by a wide margin.

Hence:

$$ S > 0 \quad \Rightarrow \quad W_R > W_L. $$

This conclusion does not rely on a single-term dominance inequality but on the global imbalance of frequency mass in Fig. 12 toward larger indices.

7. Final conclusion

The worst BST is the chain that maximizes weighted depth, which is the right-skewed lexicographic chain:

$$ K_1 \to K_2 \to \cdots \to K_{31}. $$

Answer

$$ \boxed{\text{The worst BST is the completely right-skewed chain in lexicographic order.}} $$