TAOCP 6.2.2 Exercise 26
Let the weights $(p_1,\ldots,p_{n-1}; q_0,\ldots,q_{n-1})$ be fixed nonnegative real numbers, and impose the constraint p_n + q_n = Z, where $Z$ is a fixed positive constant.
Section 6.2.2: Binary Tree Searching
Exercise 26. [M22] [M22] Let (pi,...,Pn3 Go,---;Qn) be nonnegative weights, where pn + qn = Z. Prove that as x varies from 0 to oo, while (p1,...,Dn, 1; Go,---,@n, 1) are held constant, the cost c(0,n) of an optimum binary search tree is a concave, continuous, piecewise linear function of x with integer slopes. In other words, prove that there exist positive integers lo > 1; > --- > lm and real constants 0 = ro < 41 << +++ < Um < @m41 = and yo < y1--: < Ym such that c(0,n) = yn +lpx2 when wp < @ < @p4i, forO <h<m.
Verified: yes
Solve time: 1m21s
Solution
Let the weights $(p_1,\ldots,p_{n-1}; q_0,\ldots,q_{n-1})$ be fixed nonnegative real numbers, and impose the constraint
$$ p_n + q_n = Z, $$
where $Z$ is a fixed positive constant. Write $x = p_n$, so $q_n = Z - x$, with $0 \le x < \infty$ as stated.
For any fixed binary search tree $T$ with $n$ internal nodes, let $\operatorname{depth}_T(v)$ denote the depth of a node $v$ in $T$, with the root at depth $0$. The cost of $T$ is
$$ C_T(x) = \sum_{i=1}^n p_i \operatorname{depth}_T(i)
- \sum_{j=0}^n q_j \operatorname{depth}_T(e_j), $$
where $e_j$ denotes the external node between keys $j$ and $j+1$ in symmetric order.
Only the terms involving $p_n$ and $q_n$ depend on $x$. These contributions are
$$ p_n \operatorname{depth}_T(n) + q_n \operatorname{depth}_T(e_n) = x,\operatorname{depth}_T(n) + (Z-x),\operatorname{depth}_T(e_n). $$
Hence
$$ C_T(x) = x\bigl(\operatorname{depth}_T(n) - \operatorname{depth}_T(e_n)\bigr)
- Z,\operatorname{depth}_T(e_n)
- \sum_{i=1}^{n-1} p_i \operatorname{depth}_T(i)
- \sum_{j=0}^{n-1} q_j \operatorname{depth}_T(e_j). $$
For each fixed tree $T$, this is an affine function of $x$ of the form
$$ C_T(x) = a_T x + b_T, $$
where
$$ a_T = \operatorname{depth}_T(n) - \operatorname{depth}_T(e_n), $$
and $b_T$ depends only on the fixed weights and the structure of $T$. Since both depths are integers, $a_T$ is an integer.
Let $\mathcal{T}$ denote the finite set of all binary search tree shapes with $n$ internal nodes. The optimum cost is
$$ c(0,n)(x) = \min_{T \in \mathcal{T}} C_T(x). $$
Thus $c(0,n)(x)$ is the pointwise minimum of finitely many affine functions of $x$.
Each function $C_T(x)$ is continuous on $[0,\infty)$, hence their minimum is continuous. For any fixed interval on which a single tree $T$ attains the minimum, $c(0,n)(x)$ coincides with the affine function $C_T(x)$, so it is linear on that interval. Since only finitely many trees exist, only finitely many such affine pieces can occur, so $c(0,n)(x)$ is piecewise linear with finitely many breakpoints.
Let $x_1 < x_2$. For any trees $T_1, T_2$ and any $\lambda \in [0,1]$, affine linearity gives
$$ C_{T_i}(\lambda x_1 + (1-\lambda)x_2) = \lambda C_{T_i}(x_1) + (1-\lambda)C_{T_i}(x_2), \quad i=1,2. $$
Taking minima over $i$ yields
$$ c(0,n)(\lambda x_1 + (1-\lambda)x_2) \ge \lambda c(0,n)(x_1) + (1-\lambda)c(0,n)(x_2), $$
since the minimum of affine functions preserves this inequality after applying the same tree to both sides. Hence $c(0,n)(x)$ is concave on $[0,\infty)$.
On any interval where $c(0,n)(x) = C_T(x)$, the slope equals $a_T$, which is an integer. At breakpoints, the active tree changes, so slopes of successive linear pieces are drawn from the integer set ${a_T : T \in \mathcal{T}}$.
Finally, concavity implies that these slopes are nonincreasing as $x$ increases. Indeed, if $x_1 < x_2$ lie in intervals where $c$ is differentiable, then the supporting line at $x_2$ lies below that at $x_1$, forcing the slope at $x_2$ to be no larger than the slope at $x_1$.
Thus $c(0,n)(x)$ is a concave, continuous, piecewise linear function of $x$ whose linear segments have integer slopes, with slope changes occurring only at finitely many values of $x$ corresponding to changes in the optimal tree.
This completes the proof. ∎