TAOCP 6.2.2 Exercise 33
Let keys $1,\dots,n$ have search probabilities $p_1,\dots,p_n$ and external probabilities $q_0,\dots,q_n$ as in Section 6.
Section 6.2.2: Binary Tree Searching
Exercise 33. [M41] [M41] In order to find the binary search tree that minimizes the running time of Program T, we should minimize the quantity 7C + C1 instead of simply minimizing the number of comparisons C’. Develop an algorithm that finds optimum binary search trees when different costs are associated with left and right branches in the tree. (Incidentally, when the right cost is twice the left cost, and the node frequencies are all equal, the Fibonacci trees turn out to be optimum; see L. E. Stanfel, JACM 17 (1970), 508-517. On machines that cannot make three-way comparisons at once, a program for Algorithm T will have to make two comparisons in step T2, one for equality and one for less-than; B. Sheil and V. R. Pratt have observed that these comparisons need not involve the same key, and it may well be best to have a binary tree whose internal nodes specify either an equality test or a less-than test but not both. This situation would be interesting to explore as an alternative to the stated problem.)
Verified: yes
Solve time: 1m23s
Setup
Let keys $1,\dots,n$ have search probabilities $p_1,\dots,p_n$ and external probabilities $q_0,\dots,q_n$ as in Section 6.2.2. For a binary search tree $T$, let each successful or unsuccessful search follow a path from the root, where each edge is either a left branch or a right branch.
Fix two positive constants $a_L$ and $a_R$, representing the cost of traversing a left edge and a right edge, respectively. The cost of a successful or unsuccessful search in $T$ is the sum of edge costs along the search path.
Let $C(T)$ denote the expected cost of a successful search and $C'(T)$ the expected cost of an unsuccessful search. The objective stated in the exercise is to minimize a linear combination of these two quantities, written in the form
$a_R C(T) + a_L C'(T).$
For any subtree containing keys $i$ through $j$, write $W(i,j)$ for the total probability mass in that subtree, including external weights, so
$W(i,j)=\sum_{t=i}^j p_t + \sum_{t=i-1}^j q_t.$
Let $c(i,j)$ denote the minimum achievable value of the objective over all binary search trees containing keys $i,\dots,j$.
Solution
Consider a fixed subtree $T$ on keys $i,\dots,j$ with root $k$. Let $T_L$ and $T_R$ denote its left and right subtrees, containing keys $i,\dots,k-1$ and $k+1,\dots,j$ respectively.
Attach $T_L$ and $T_R$ under $k$. Every node in $T_L$ is reached through one additional left edge, and every node in $T_R$ is reached through one additional right edge. Hence each unit of probability mass in $T_L$ contributes an additional cost $a_L$, and each unit of probability mass in $T_R$ contributes an additional cost $a_R$.
Therefore the total cost satisfies
$c(i,j)=\min_{i \le k \le j}\Bigl(c(i,k-1)+c(k+1,j)+a_L W(i,k-1)+a_R W(k+1,j)\Bigr).$
For consistency with empty subtrees, define
$c(i,i-1)=0,\qquad W(i,i-1)=q_{i-1}.$
This recurrence yields an algorithm by dynamic programming over increasing interval length exactly as in Algorithm 6.2.2K, except that two additional weight terms are added for each split.
The algorithm is:
For all $i$, set $c(i,i-1)=0$ and $W(i,i-1)=q_{i-1}$. For $i \le j$, compute
$W(i,j)=W(i,j-1)+p_j+q_j.$
Then compute $c(i,j)$ for increasing $j-i$ by minimizing over $k$:
$c(i,j)=\min_{i \le k \le j}\Bigl(c(i,k-1)+c(k+1,j)+a_L W(i,k-1)+a_R W(k+1,j)\Bigr).$
This produces all optimal subtrees, and the final answer is $c(1,n)$.
The correctness follows from the decomposition of expected cost into contributions of left and right edges and the additivity of the weight function $W(i,j)$ across disjoint subtrees.
Verification
Each edge from a node in the left subtree of a root contributes exactly one additional left traversal relative to its position inside the subtree, and contributes no additional right traversal. Hence every probability mass element in $T_L$ increases the objective by exactly $a_L$ when the subtree is attached.
Similarly, every element in $T_R$ increases the objective by exactly $a_R$ when attached under a right edge. No other term depends on the structure of the subtree, so the decomposition separates cleanly into independent subproblems plus linear corrections depending only on total subtree weights.
Every candidate root $k$ partitions the interval $[i,j]$ uniquely into $[i,k-1]$ and $[k+1,j]$, and every binary search tree arises from exactly one such partition, so no feasible tree is omitted.
Each subproblem $c(i,k-1)$ and $c(k+1,j)$ depends only on smaller intervals, so the recurrence is well-founded over increasing interval length. Hence the dynamic programming computation evaluates all necessary values exactly once.
This completes the proof. ∎