CSCI3160 L10 最优二叉搜索树

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L10 最优二叉搜索树 · 原件 L10-DP-05-Optimal-BST-未核-隐藏.pdf（本地课件） p.1–14 定位：把搜索频率纳入成本，证明根节点的附加费用为何是整个区间的权重和，并恢复最优树。承接：#L07-02 最优方案恢复；#L08-02 依赖顺序

p.1 标题页。

搜索树与查找代价（p.2–3）【新】

p.2 The key of an internal node u is larger than any key in the left subtree of u, and smaller than any key in the right subtree of u.

二叉搜索树（binary search tree，BST）的顺序约束作用于整棵子树，不只是两个孩子。查找时比较根，较小去左、较大去右；因此每个节点存的是有序键，而非 Huffman 的频率。

图（p.2–3）：四个键的搜索树。元素：根 20，左孩子 10，右孩子 40；40 的左孩子 30。看什么：30 虽小于父节点 40，却仍大于根 20，符合右子树整体约束。

p.3 把根的层数设为 0，访问节点数为层数加 1：找 20 访问一次；找 10 或 40 访问两次；找 30 经 20→40→30，访问三次。树深度为最大层数 2，不能把搜索 30 的成本也写成 2。

频率让平衡之外的目标出现（p.4–5）

p.4 some are searched more often than others.

p.4 平衡树控制最坏高度，但最小平均成本还需考虑各键出现频率。p.5 给 10、20、30、40 的频率 40%、15%、35%、10%。

算一遍：原树平均成本 $0.4\cdot2+0.15\cdot1+0.35\cdot3+0.1\cdot2=2.2$ 。高频的 30 位于深处，贡献 1.05，已超过其余三个里任一项，因此调整结构可能降低平均代价。

区间子问题与权重口径（p.6–7）【新】

p.6 An array W where W[i] ( $1\le i\le n$ ) stores a positive integer weight.

p.6 把键按排序秩重命名为 1 到 n，W[i] 是整数权重。讲义称目标为 avgcost，但实际式子是未归一化的加权和 $\sum_i W[i](1+\mathrm{level}(i))$ 。若权重总和为 100，除以 100 才是按百分比计算的平均访问次数；固定输入下除不除这个常数不会改变哪棵树最优。

p.7 将子问题定义为连续键区间 [a,b]。为什么是连续区间？固定某个根后，所有更小键都必须在左子树，所有更大键都在右子树，不能任意选一堆键作为子问题。

固定根后的费用分解（p.8–10）

图（p.8）：根 r 与左右子树。元素：左子树 T1 存 a 到 r−1，右子树 T2 存 r+1 到 b；二者都挂在 r 下方一层。看什么：接上根后，子树中每个键都多访问一次根；根 r 自己也需访问一次。

p.8 所以总成本是左子树成本、右子树成本，再加区间全部键的权重和。p.9 先将每项 $W[i](1+\mathrm{level}_T(i))$ 拆成 W[i] 与深度项；根的深度为 0，深度项只剩左右两组。p.10 对左组使用 $\mathrm{level}_T(i)=1+\mathrm{level}_{T_1}(i)$ ，右组也一样，深度项就分别变成两个子树的查找成本。

把 p.9–10 的整条等式写出，C 代表讲义的 avgcost：

\begin{aligned} C(T)&=\sum_{i=a}^{b}W[i](1+\mathrm{level}_T(i)),\\ &=\sum_{i=a}^{b}W[i]+\sum_{i=a}^{r-1}W[i]\mathrm{level}_T(i) +\sum_{i=r+1}^{b}W[i]\mathrm{level}_T(i),\\ &=\sum_{i=a}^{b}W[i]+\sum_{i=a}^{r-1}W[i](1+\mathrm{level}_{T_1}(i)) +\sum_{i=r+1}^{b}W[i](1+\mathrm{level}_{T_2}(i)),\\ &=\sum_{i=a}^{b}W[i]+C(T_1)+C(T_2). \end{aligned}

第二行没写根 r 的深度项，因为它为零；第三行对子树中每个键都减去挂到总根下面增加的那一层。这是原页的层数分解，并非额外假设。

因此不是只加根的权重 W[r]。只加它会漏掉所有子树键因整体下移产生的额外访问。

固定根最优值与原例（p.11–12）

p.11 Define optavg(a,b) as 0, if a > b;

p.11 的空区间成本为 0；固定根 r 后左右子树应各自最优，否则可替换改进。所以条件最优值为区间权重和加左右 optavg。

题面（L10-DP-05-Optimal-BST-未核-隐藏.pdf · Example · p.12）

p.12 Example: S = {1, 2, 3, 4}; W = (40, 15, 35, 10). Consider choosing 2 as the root key.

区间总权重 100。左侧只键 1，成本 40；右侧键 3、4，以 3 为根的成本为 $35+2\cdot10=55$ ，以 4 为根则为 $10+2\cdot35=80$ ，故右侧最优 55。固定根 2 总成本 $100+40+55=195$ 。这只在“根为 2”的条件下最优，还没比较其他根。

按区间长度枚举所有根（p.13）

p.13 With dynamic programming, we can compute optavg(1,n) in $O(n^3)$ time (left as a special exercise).

公式按讲义重排。令 D(a,b)=optavg(a,b)， $W(a,b)=\sum_{i=a}^bW[i]$ ，则

D(a,b)=W(a,b)+\min_{a\le r\le b}\{D(a,r-1)+D(r+1,b)\}.

按区间长度 1、2、…、n 填表，因为两个依赖区间都更短。前缀和使每个 W(a,b) 可常数时间取得； $O(n^2)$ 个状态各试 $O(n)$ 个根，得到三次时间、二次表空间。

算一遍：讲义权重下，长度 1 的值为 40、15、35、10。长度 2：D(1,2)=55+min(15,40)=70；D(2,3)=50+min(35,15)=65；D(3,4)=45+min(10,35)=55。长度 3：D(1,3)=90+min(65,75,70)=155；D(2,4)=60+min(55,25,65)=85。最后四个根的成本依次为 185、195、180、255，最优是根 3，值 180。

补充：把最顶层四个根的账本列开。 原权重前缀和为 0,40,55,90,100，所以例如区间 [2,4] 权重为 $100-40=60$ ，查一次差即可，无须为每个候选根重算和。

根 r	左子树最优成本	右子树最优成本	全区间多比较一次	合计
1	0	85	100	185
2	40	55	100	195
3	70	10	100	180
4	155	0	100	255

选 r=3 不意味着直接把第 3 个键置顶就完成：还要沿保存的子区间最优根递归建左右树。子树相对深度从 0 开始计费，挂到上层时统一加一；若在子问题里已用全局深度计费，又在合并时加区间和，就会重复收费。

自测：为何最高频的键不必成为最优根？

本例键 1 权重 40 最高，但作为根总代价 185；权重 35 的键 3 作根只需 180。根的位置还决定哪些键被迫落入哪一侧，以及它们的后续深度。只把最大权放根忽略了有序约束。主讲只考虑成功查询的键权重；若题目给键间失败查询概率，需新增相应空隙状态和成本，不能直接套此表。

恢复树并验算（p.14）【延伸 L07 p.6–8】

p.14 the piggyback technique allows you to build the tree in the same time complexity as computing opt(1,n).

每个区间同时保存达到 min 的根。原例 [1,4] 的根为 3；左区间 [1,2] 根为 1，其右孩子为 2；右区间只剩 4。换回 p.5 的真实键，根 30，左孩子 10，10 的右孩子 20，根右孩子 40。

验算加权访问成本为 $35\cdot1+40\cdot2+15\cdot3+10\cdot2=180$ ，除以 100 得 1.8，比初始树的 2.2 小，也比固定根 20 的 1.95 小。恢复时每个键创建一个节点，共 O(n)，不会改变 O(n³) 总时间。

恢复树的完整伪代码：

在计算 D(a,b) 的最小候选时，同时保存 root[a,b]=r
Build(a,b):
  若 a>b：返回空树
  r = root[a,b]
  创建存键 r 的节点
  节点左孩子 = Build(a,r-1)
  节点右孩子 = Build(r+1,b)
  返回该节点
最终返回 Build(1,n)

空区间返回空树，与其成本为 0 完全对应。每个非空调用输出一个不同的键，故创建 n 个节点就结束，不再枚举全部根。

考试角度：（C 级通识）常见考法是解释为何根带来的新增成本是整个区间权重和，并给出合法填表顺序；不要将缺题干的 Midterm-A-2025T1 Q10 反向补成原题。

本讲核心考点

搜索访问次数为层数加1，根成本不是0（p.3，C 级）。
整数权重的加权和不等于已归一化平均值（p.6，C 级）。
固定根后加整个区间权重和（p.8–12，C 级）。
按区间长度填表，枚举根得到O(n³)（p.13–14，C 级）。

附录

本讲所需过程已在正文展开。

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：L10-DP-05-Optimal-BST-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。