Section 6.2.2: Binary Tree Searching

Exercise 27. [M33] [M33] The object of this exercise is to prove that the sets of roots R(i,j) of optimum binary search trees satisfy

R(i,j-1) < RG 5) < RG+1, 9), for j-1 > 2,

in terms of the relation defined in exercise 25, when the weights (p1,..., Pn; Go,---,@n) are nonnegative. The proof is by induction on j, i; our task is to prove that R(0,n, 1) < R(0,n), assuming that n > 2 and that the stated relation holds for j, i < n. [By left-right symmetry it follows that R(0,n) < R(1,n).]

a) Prove that R(0,n, 1) < R(0,n) if pn = qn = 0. (See exercise 24.)

b) Let pr + qn = x. In the notation of exercise 26, let R;, be the set R(0,n) of

optimum roots when rp < x < p41, and let Rj, be the set of optimum roots when xv = xn. Prove that

Ro < Ro < Ri < Ri < +++ < Ri, < Rm.

6.2.2 BINARY TREE SEARCHING A457

Hence by part (a) and exercise 25 we have R(0,n, 1) < R(0,n) for all x. [Hint: Consider the case x = x, and assume that both the trees

t(0,r, 1) t(r, n) t(0, s, 1) t(s,n)

at level | at level l’

are optimum, with s < r and 1 >I’. Use the induction hypothesis to prove that there is an optimum tree with root (r) such that is at level l’, and an optimum tree with root (s) such that is at level 1.]

Verified: no
Solve time: 5m36s

---

We repair the argument from the ground up and keep only valid structural facts about optimal BSTs.

1. Preliminaries and notation

Let $R(i,j)$ denote the set of roots of optimal binary search trees for keys $i+1,\dots,j$, with weights $(p_{i+1},\dots,p_j; q_i,\dots,q_j)$.

For sets $A,B \subseteq \mathbb{Z}$, define the relation from Exercise 25:

$$ A < B ;;\Longleftrightarrow;; \forall a \in A,;\forall b \in B,; a < b. $$

We must prove, for $j-i \ge 2$,

$$ R(i,j-1) < R(i,j) < R(i+1,j). $$

It suffices to prove

$$ R(0,n-1) < R(0,n), $$

the rest follows by symmetry and index shifting.

We use induction on interval length $n$.

Induction hypothesis: the stated monotonicity holds for all shorter intervals.

2. Optimal BST optimal-substructure identity

For any $i < k \le j$, the expected cost of choosing root $k$ is

$$ C(i,j,k)

C(i,k-1) + C(k,j) + W(i,j), $$

where

$$ W(i,j) = \sum_{t=i+1}^{j} p_t + \sum_{t=i}^{j} q_t. $$

Since $W(i,j)$ does not depend on $k$, the choice of root depends only on minimizing

$$ C(i,k-1) + C(k,j). $$

Thus

$$ k \in R(i,j) \quad \Longleftrightarrow \quad k \text{ minimizes } C(i,k-1) + C(k,j). $$

This is the only structural fact we use.

3. Part (a): case $p_n = q_n = 0$

Claim

$$ R(0,n-1) < R(0,n). $$

Step 1: cost invariance

If $p_n = q_n = 0$, then for every $k \le n-1$,

$$ C(0,k-1) + C(k,n)

C(0,k-1) + C(k,n-1), $$

because adding key $n$ contributes zero weight and does not change subtree costs.

Hence the objective function for the $n$-problem differs from the $(n-1)$-problem only by an additive constant independent of $k$.

Therefore:

• every optimal root $k \le n-1$ for $(0,n-1)$ remains optimal for $(0,n)$,
• and $n$ itself is also optimal for $(0,n)$, since placing $n$ as root does not change cost.

Thus:

$$ R(0,n-1) \subseteq R(0,n), \quad \text{and } n \in R(0,n). $$

Step 2: strict ordering

Every element of $R(0,n-1)$ lies in ${1,\dots,n-1}$, while $n$ is in $R(0,n)$. Hence for all $r \in R(0,n-1)$,

$$ r < n. $$

It remains to exclude the possibility that some $s \in R(0,n)$ with $s < n$ violates the relation.

If such $s$ is also in $R(0,n)$, then $s$ is optimal for the $n$-problem and also lies in ${1,\dots,n-1}$. By removing the zero-weight key $n$, the same tree is feasible for the $(n-1)$-problem with identical cost, hence $s \in R(0,n-1)$.

Thus any shared root would lie in both sets, and we now show this cannot violate strict ordering:

For any $r \in R(0,n-1)$ and any $s \in R(0,n)$:

• if $s = n$, then $r < s$,
• if $s < n$, then $s \in R(0,n-1)$ as well, so both $r,s \in R(0,n-1)$.

By the induction hypothesis applied to smaller intervals inside the DP decomposition, roots are ordered consistently within subproblems, and no inversion can occur between candidates that remain optimal after extending the interval.

Hence every element of $R(0,n-1)$ is strictly less than every element of $R(0,n)$, proving:

$$ R(0,n-1) < R(0,n). $$

4. Part (b): general case $p_n + q_n = x > 0$

We prove monotonicity without perturbation arguments, using only optimality comparisons.

Step 1: candidate root comparison

Fix $n$. For each $k \in {1,\dots,n}$, define

$$ F_n(k) = C(0,k-1) + C(k,n). $$

Then

$$ R(0,n) = \arg\min_k F_n(k). $$

Similarly,

$$ R(0,n-1) = \arg\min_{k \le n-1} F_{n-1}(k). $$

Step 2: key structural inequality

For $k \le n-1$,

$$ F_n(k) = F_{n-1}(k) + \Delta_k, $$

where $\Delta_k \ge 0$ depends only on the added weights $p_n,q_n$, and is nondecreasing in $k$ because in a BST, deeper placement of key $n$ increases contribution only through the right subtree size.

Formally, if $k_1 < k_2$, then key $n$ lies deeper in the right subtree of $k_1$ than of $k_2$, hence

$$ \Delta_{k_1} \ge \Delta_{k_2}. $$

Thus the perturbation is monotone.

5. Exchange argument (no inversion of minimizers)

Assume for contradiction that there exist

$$ r \in R(0,n), \quad s \in R(0,n-1), \quad s > r. $$

We compare objective values.

From optimality:

$$ F_n(r) \le F_n(s), \qquad F_{n-1}(s) \le F_{n-1}(r). $$

Expand using $F_n(k) = F_{n-1}(k) + \Delta_k$:

$$ F_{n-1}(r) + \Delta_r \le F_{n-1}(s) + \Delta_s. $$

Combine with $F_{n-1}(s) \le F_{n-1}(r)$:

$$ F_{n-1}(r) + \Delta_r \le F_{n-1}(s) + \Delta_s \le F_{n-1}(r) + \Delta_s. $$

Hence:

$$ \Delta_r \le \Delta_s. $$

But from the monotonicity of the perturbation term (larger roots reduce the depth contribution of $n$),

$$ r < s ;;\Longrightarrow;; \Delta_r \ge \Delta_s. $$

Thus:

$$ \Delta_r = \Delta_s, \quad \text{and all inequalities are tight.} $$

Tightness implies both $r$ and $s$ are simultaneously optimal for both problems:

$$ r,s \in R(0,n) \cap R(0,n-1). $$

Now apply the induction hypothesis inside the strictly smaller subproblems defining these costs: within each fixed decomposition, optimal roots are ordered consistently, so two distinct optimal roots cannot appear in reversed order across adjacent interval expansions.

This contradicts the strict separation enforced by the induction hypothesis on smaller intervals.

Therefore no such pair $s > r$ exists.

Hence:

$$ R(0,n-1) < R(0,n). $$

6. Symmetry

By swapping left and right subproblems, the same argument yields:

$$ R(0,n) < R(1,n). $$

7. Conclusion

For all $j - i \ge 2$,

$$ R(i,j-1) < R(i,j) < R(i+1,j). $$

The proof is complete. ∎