Exercise 24. [M25] [M25] Given that pn = gn = 0 and that the other weights are nonnegative, prove that an optimum tree for (p1,...,Pn; Go,---;Qn) may be obtained by replacing

n-1

in any optimum tree for (pi,...,DPn, 1; Go,--+-,@n, 1)-

Verified: no
Solve time: 4m32s

Let $T$ be a binary search tree with cost

$$ C(T)=\sum_{i=1}^n p_i,\mathrm{depth}(k_i)+\sum_{i=0}^n q_i,\mathrm{depth}(d_i), $$

where all $p_i,q_i\ge 0$ and $p_n=q_n=0$.

The goal is to show that an optimal tree for $(p_1,\dots,p_n;q_0,\dots,q_n)$ is obtained from an optimal tree for $(p_1,\dots,p_{n-1};q_0,\dots,q_{n-1})$ by replacing $d_{n-1}$ with an internal node $k_n$ whose children are $d_{n-1}$ and $d_n$.

1. Structural restriction on the location of $k_n$

In any BST on keys $k_1<\cdots<k_n$, the key $k_n$ is the largest key. Hence it has no right internal child; its right child must be the external node $d_n$.

Thus, in any tree, $k_n$ lies on the unique search path to $d_n$.

2. Key exchange lemma along a search path

Consider a parent-child pair $v\to x$ in a BST. Let $T_v$ be the subtree rooted at $v$, and $T_x\subseteq T_v$ the subtree rooted at $x$. If we swap $v$ and $x$ (a single rotation), then:

every node in $T_v\setminus T_x$ increases depth by $1$,
every node in $T_x$ decreases depth by $1$.

Hence the cost change is

$$ \Delta C

\bigl(W(T_v)-W(T_x)\bigr)

W(T_x)

W(T_v)-2W(T_x), $$

where $W(S)$ denotes the total weight of nodes in a subtree $S$.

Now apply this to the case where $x=k_n$. Since $p_n=q_n=0$, the node $k_n$ has zero weight, but its subtree consists only of $k_n$ and possibly external node $d_n$, both with total weight $0$. Thus

$$ W(T_x)=0. $$

Therefore

$$ \Delta C = W(T_v)\ge 0. $$

So swapping $k_n$ with its parent never decreases cost; it weakly increases cost. This implies:

Conclusion. In every optimal tree, $k_n$ cannot be moved upward along the path to $d_n$ without increasing cost, hence it must already be as low as possible on that path.

Therefore, there exists an optimal tree in which $k_n$ is the parent of $d_n$.

3. Identification of the second child of $k_n$

Once $k_n$ is the parent of $d_n$, its left subtree contains exactly the keys $k_1,\dots,k_{n-1}$.

In inorder traversal, the external node immediately preceding $k_n$ is $d_{n-1}$. In a BST, this node must be the rightmost external node of the left subtree of $k_n$.

Hence the left child of $k_n$ must be exactly $d_{n-1}$. Therefore, in an optimal tree we may assume:

right child of $k_n$ is $d_n$,
left child of $k_n$ is $d_{n-1}$,
$k_n$ has no other children.

So $k_n$ is an internal node whose two children are external nodes $d_{n-1}$ and $d_n$.

4. Reduction from $n$ to $n-1$

Let $T$ be an optimal tree with the above structure at $k_n$. Remove $k_n$ and its incident edges, and identify its left external child $d_{n-1}$ as the attachment point.

No remaining node changes depth:

$k_n$ has weight $0$,
$d_n$ has weight $0$,
all other nodes lie outside the removed leaf configuration.

Thus the cost is preserved:

$$ C(T)=C(T'). $$

The resulting tree $T'$ is a valid BST for $(p_1,\dots,p_{n-1};q_0,\dots,q_{n-1})$. If $T'$ were not optimal, we could improve $T$, contradicting optimality. Hence $T'$ is optimal.

5. Construction in the opposite direction

Conversely, let $T'$ be optimal for $(p_1,\dots,p_{n-1};q_0,\dots,q_{n-1})$. Replace the external node $d_{n-1}$ by an internal node $k_n$, and attach two external children $d_{n-1}$ and $d_n$.

All added nodes have weight $0$, and all existing node depths are unchanged. Hence