最优二叉搜索树

普通二叉搜索树只要求中序顺序正确；最优二叉搜索树（OBST）还利用访问频率，让常查的关键字更靠近根，从而最小化期望比较次数。

1. 成功与失败搜索都要计入

有有序关键字

$$k_1<k_2<\cdots<k_n.$$

$p_i$ 表示成功查到 $k_i$ 的概率；$q_i$ 表示落在关键字间隙 $d_i$ 的失败搜索概率，其中 $d_0$ 在 $k_1$ 左侧，$d_n$ 在 $k_n$ 右侧。

满足

$$\sum_{i=1}^n p_i+\sum_{i=0}^n q_i=1.$$

失败搜索对应外部叶子，不能随意忽略。课件中的完整模型同时考虑 $p$ 和 $q$。

2. 期望代价

若根深度记为 1，则

$$E=\sum_{i=1}^n p_i(\operatorname{depth}(k_i)+1) +\sum_{i=0}^n q_i(\operatorname{depth}(d_i)+1).$$

不同教材对根深度的起点可能不同，但只要状态和边界前后一致，最优树不变。

3. 区间状态

定义：

• $e[i][j]$：包含 $k_i\ldots k_j$ 的最优子树期望代价；
• $w[i][j]$：该区间内全部成功与失败概率之和；
• $root[i][j]$：最佳根下标。

空区间边界为

$$e[i][i-1]=q_{i-1},\qquad w[i][i-1]=q_{i-1}.$$

逐步扩展权重：

$$w[i][j]=w[i][j-1]+p_j+q_j.$$

4. 状态转移

选择 $k_r$ 为区间根后，左右子树分别是 $[i,r-1]$ 和 $[r+1,j]$。把它们挂到新根下，区间内每个结点深度都增加 1，因此额外增加总概率 $w[i][j]$：

$$e[i][j]=\min_{i\le r\le j} \{e[i][r-1]+e[r+1][j]+w[i][j]\}.$$

按区间长度递增填表，并把最优 $r$ 记入 $root$。

5. 复杂度

标准实现有 $O(n^2)$ 个区间，每个枚举 $O(n)$ 个根：

$$T=O(n^3),\qquad S=O(n^2).$$

在满足四边形不等式等结构时，可用 Knuth 优化把时间降为 $O(n^2)$；课程基础题通常要求标准转移。

6. 为什么不能总选最高概率关键字

把全局最高频关键字放根只优化了根本身，却可能让两侧大量概率被压到很深。根的选择要同时权衡左右区间的最优结构和整体权重，局部最大概率并不必然全局最优。

7. 恢复树结构

从 $root[1][n]$ 得到整棵树的根，再递归查看左右区间的 root。空区间对应失败结点 $d_{i-1}$。这样不仅得到最小期望值，也能构造完整搜索树。

8. 与矩阵链乘法的共同模式

两者都是区间 DP，并枚举区间中的一个位置：

• 矩阵链枚举最后一次乘法的分割点；
• OBST 枚举子树根。

区别在于 OBST 左右区间挂到新根后，所有深度增加，所以转移多出 $w[i][j]$。