CSCI3160 Special 8：最优与最差二叉搜索树

原件：Sp08 题目（本地课件） p.1。 每题先题解后解析。目标采用课堂递推的加权比较次数：根深度计1；若要平均值，再除总权重。

Problem 1：四个键的全部区间最优值

题解

权重W=(10,20,30,40)。按题给递推，区间最优值如下：

强制根为3的值也是180。一棵最优BST为根3，左孩子2，2的左孩子1，根的右孩子4。若把权重归一成概率，总平均比较次数为180/100=1.8。

具体解析

根r确定后，所有区间内键都至少访问根一次，贡献区间总权重；左右子树再付各自内部代价。因此D[a,b]=区间权重和+min(D[a,r−1]+D[r+1,b])。

单点只访问一次，分别10、20、30、40。两点区间：[1,2]权重和30，根1候选30+20=50，根2候选30+10=40；[2,3]候选80、70；[3,4]候选110、100。

三点[1,3]总和60，各根候选130、100、100，根2和3平局，表取2；[2,4]总和90，各根候选190、150、160。四点总和100，各根候选250、210、180、200，所以根3唯一最优。

树形验算：10×3+20×2+30×1+40×2=180。不要把键的数值1、2、3、4当频率，也不要把根深度计0，否则会整体少一次权重和。

Problem 2：三次方计算区间最优值

题解

先求权重前缀和H。空区间D[a,a−1]=0；按区间长度1,…,n，枚举左端a及全部候选根r，取最小左右子树之和再加H[b]−H[a−1]。时间O(n³)、空间O(n²)。

具体解析

根只能取区间内键，否则不满足BST；左子树键必须是连续编号[a,r−1]，右边必须[r+1,b]，不能自由分配。两侧严格更短，因此长度序确保已完成。

O(n²)个区间，每区间O(n)个根，每个候选只查两格并加常数项。前缀和预处理O(n)，让每次区间求和O(1)。空区间不要拿未初始化内存当零。比较与加法按课堂字长模型处理。

Problem 3：构造树而不只输出最优值

题解

在Q2更新最小值时，同时记录bestroot[a,b]=r。恢复Build(a,b)：空区间返回空；否则创建根r，左孩子Build(a,r−1)，右孩子Build(r+1,b)。填表O(n³)，恢复O(n)。

具体解析

恢复访问每个键一次，区间在每个根处分成不相交的左右两部分，不会重建重复节点。Q1从bestroot[1,4]=3开始，查[1,2]得到2，再查[1,1]得到1，右边[4,4]得到4，正好生成所示最优树。

若存在平局，保存任意一个达到最小的根即可；不能只保存最小数值后在恢复时随便选根，否则树的实际代价可能不等于DP值。即使恢复时重新扫描根，整体仍可满足O(n³)，但顺手保存指针更清楚且更快。

Problem 4：最大频率作根的贪心反例

题解

取三个键1、2、3，权重3、2、2。贪心唯一先选根1，右侧2、3任选根，总代价都是13；改用根2、左右叶1和3，代价12，更优。

具体解析

贪心树中频率3的键深度1，另两个键深度2、3，成本3+4+6=13。根2方案成本2+6+4=12。根3方案的最好代价为14，所以12确实最优。

频率最大的键放浅处当然有局部好处，但若它在有序键的边缘，就把其余全部挤进同一侧，加深很多访问。最佳根是在自身收益与两边总深度之间权衡，不是单看最大频率。反例根的选择无平局，后续平局也不影响失败。

Problem 5：最差BST

题解

把最优递推中的min换成max：

空区间为0。按长度求值，同时保存最大根，恢复树即可。时间O(n³)、空间O(n²)。

具体解析

固定根后，两子树访问代价互不干扰；要让总和最大，左右都必须选各自最差树，否则替换某侧可进一步增大总代价。枚举根覆盖所有合法BST，所以得到真正全局最大，不是随意造一条链就结束证明。

自取权重3、2、2：根1可得13，根2得12，根3可得15（右端3为根、左孩子2、2的左孩子1），成本2+4+9=15。它与Q4的最优值12形成对照。根3的左子树必须取最大代价，而不是沿用最优表；两种DP不可混用。

同一根的 min 子树和 max 子树不是同一笔账。 对 Q4–5 的权重 $(3,2,2)$，先只看键 1、2：根 1 的成本 $3+2\cdot2=7$，根 2 的成本 $2+2\cdot3=8$。现在固定全树根为 3，左子树所有深度增加 1，需额外支付总权重 $3+2=5$，再加根权重 2。因此以 3 为根的最优成本是 $7+5+2=14$，最差成本是 $8+5+2=15$。后一个候选不能误用前一个的最优子表。

来源与证据

Sp08 p.1。原题将加权成本称为average，本文按所给递推保存数值180，并单独注明归一后的1.8，避免量纲混淆。