最优二叉搜索树

概述

最优二叉搜索树问题是在给定关键字搜索频率的情况下，构造一棵期望搜索代价最小的BST。与普通BST不同，该问题同时考虑了成功搜索（找到关键字）和失败搜索（搜索伪关键字）的频率，是一个经典的动态规划应用。

定义

最优二叉搜索树（Optimal Binary Search Tree）

输入：

• $n$ 个排序关键字 $k_1<k_2<\cdots <k_n$
• 成功搜索概率 $p_1,p_2,\dots ,p_n$（搜索 $k_i$ 的概率）
• 失败搜索概率 $q_0,q_1,\dots ,q_n$（搜索值落在 $k_i$ 和 $k_{i+1}$ 之间的概率）
• 满足 $\sum _{i=1}^n{p}_i+\sum _{j=0}^n{q}_j=1$

输出：一棵包含 $k_1,\dots ,k_n$ 作为内部节点、$d_0,\dots ,d_n$ 作为叶子的二叉搜索树，使得期望搜索代价最小。

设 $e[i,j]$ 为包含关键字 $k_i,\dots ,k_j$ 的最优BST的期望搜索代价，$w(i,j)=\sum _{l=i}^j{p}_l+\sum _{l=i-1}^j{q}_l$，则： $e[i,j]=\{\begin{array}{ll}{q}_{i-1}& \text{若 }j=i-1\\ \underset{i\le r\le j}{\min }\{e[i,r-1]+e[r+1,j]+w(i,j)\}& \text{若 }i\le j\end{array}$

核心性质

1. 最优子结构

若最优BST的根为 $k_r$（$i\le r\le j$），则：

• 左子树必须是由 $k_i,\dots ,k_{r-1}$ 构成的最优BST（否则替换后代价更小）
• 右子树必须是由 $k_{r+1},\dots ,k_j$ 构成的最优BST

证明（反证法）：若左子树存在代价更小的BST，将其替换后，整棵树的期望搜索代价减小——与最优性矛盾。

2. 子树深度增加的代价

当一棵子树成为另一棵树的子树时，子树中所有节点的深度增加1。因此，子树的期望搜索代价需要加上 $w(i,j)$（子树中所有节点的概率之和）来补偿深度增加。

这正是递推公式中 $e[i,r-1]+e[r+1,j]+w(i,j)$ 的含义。

3. 自底向上算法

OPTIMAL-BST(p, q, n):
    let e[1..n+1, 0..n], w[1..n+1, 0..n], root[1..n, 1..n] be new tables
    for i = 1 to n+1:
        e[i, i-1] = q[i-1]
        w[i, i-1] = q[i-1]
    for l = 1 to n:                    // l 为子树中关键字的个数
        for i = 1 to n - l + 1:
            j = i + l - 1
            e[i,j] = ∞
            w[i,j] = w[i,j-1] + p[j] + q[j]  // 利用前缀和高效计算
            for r = i to j:
                t = e[i,r-1] + e[r+1,j] + w[i,j]
                if t < e[i,j]:
                    e[i,j] = t
                    root[i,j] = r
    return e and root

4. 构造最优解

CONSTRUCT-OPTIMAL-BST(root):
    // root[i,j] 记录了包含 k_i..k_j 的最优BST的根
    // 递归构造整棵树
    return BUILD-TREE(root, 1, n)

BUILD-TREE(root, i, j):
    if j < i:
        return leaf node d[j]
    r = root[i,j]
    left = BUILD-TREE(root, i, r-1)
    right = BUILD-TREE(root, r+1, j)
    return tree node k_r with left and right children

5. 与普通BST的区别

特征	普通BST	最优BST
构造依据	插入顺序	搜索频率
目标	支持动态操作	最小化期望搜索代价
是否平衡	不保证	不一定平衡
适用场景	动态数据集	静态数据集（关键字和频率已知）

最优BST适用于关键字集合和搜索频率已知且不频繁变化的场景，例如编译器的符号表、字典的索引结构等。

复杂度分析

指标	值
时间复杂度	$O(n^3)$
空间复杂度	$O(n^2)$
子问题数量	$\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)+n=O(n^2)$
每个子问题的选择数	$O(n)$

章节扩展

• 14.5 最优二叉搜索树 — 最优BST的完整求解过程
• 动态规划 — 动态规划完整方法论
• 最优子结构 — 最优子结构性质的详细说明

参见

• 矩阵链乘法 — 同为 $O(n^3)$ 的动态规划问题
• 钢条切割 — 动态规划的入门问题
• 最长公共子序列 — 另一个经典动态规划问题