每日算法 — 使用java实现最优二叉搜索树：动态规划与期望搜索代价最小化

问题背景

最优二叉搜索树（Optimal Binary Search Tree, OBST）是动态规划的经典应用。给定一组有序的关键字及其搜索概率，构造一棵二叉搜索树使得期望搜索代价最小。与普通的二叉搜索树不同，OBST充分考虑了各节点的访问频率，让高频节点更靠近根节点。

该问题在编译器符号表、数据库索引、字典应用等频繁查询场景中具有重要价值。例如，在编译器中，关键字if和for的使用频率远高于goto，OBST能将整体查找效率提升20%至40%。

核心算法思想

期望搜索代价定义

设关键字 k_1 < k_2 < ... < k_n，成功搜索概率为 p_i，失败搜索（虚节点）概率为 q_i。期望搜索代价为：

E = Σ(p_i × (depth(k_i) + 1)) + Σ(q_i × (depth(d_i) + 1))

区间DP状态设计

设 dp[i][j] 为只包含关键字 k_i, ..., k_j 的最优子树的期望搜索代价。状态转移方程：

dp[i][j] = min(dp[i][r-1] + dp[r+1][j] + w(i,j))  (i ≤ r ≤ j)

其中 w(i,j) 是子树 i..j 的概率总和（包含成功和失败的概率），也就是该子树中所有节点深度加1的基准增量。

更简洁的写法：

w(i,j) = w(i,j-1) + p_j + q_j
dp[i][j] = min(dp[i][r-1] + dp[r+1][j]) + w(i,j)

Java完整实现

import java.util.*;

/**
 * 最优二叉搜索树求解器
 * 使用区间动态规划最小化期望搜索代价
 */
public class OptimalBST {

    private double[] p;      // 成功搜索概率 p[1..n]
    private double[] q;      // 失败搜索概率 q[0..n]
    private int n;           // 关键字个数
    private double[][] dp;   // dp[i][j]: 关键字i到j的最优代价
    private int[][] root;    // root[i][j]: 子树i..j的最优根节点
    private double[][] w;    // w[i][j]: 子树i..j的概率总和

    public OptimalBST(double[] p, double[] q) {
        // p[1..n], q[0..n]
        this.n = p.length - 1;
        this.p = p;
        this.q = q;
        this.dp = new double[n + 2][n + 2];
        this.root = new int[n + 2][n + 2];
        this.w = new double[n + 2][n + 2];
    }

    /**
     * 求解最优二叉搜索树
     * @return 最小期望搜索代价
     */
    public double solve() {
        // 初始化：空子树的代价
        for (int i = 1; i <= n + 1; i++) {
            dp[i][i - 1] = q[i - 1];
            w[i][i - 1] = q[i - 1];
        }

        // 按区间长度从小到大枚举
        for (int len = 1; len <= n; len++) {
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1;
                dp[i][j] = Double.MAX_VALUE;

                // 计算w[i][j] = w[i][j-1] + p_j + q_j
                w[i][j] = w[i][j - 1] + p[j] + q[j];

                // 枚举根节点r
                for (int r = i; r <= j; r++) {
                    double cost = dp[i][r - 1] + dp[r + 1][j] + w[i][j];
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        root[i][j] = r;
                    }
                }
            }
        }

        return dp[1][n];
    }

    /**
     * 递归打印最优二叉搜索树的结构
     */
    public void printTree(int i, int j, int depth) {
        if (i > j) {
            String indent = "  ".repeat(depth);
            System.out.println(indent + "d" + (j) + " (失败节点, q=" + q[j] + ")");
            return;
        }
        int r = root[i][j];
        String indent = "  ".repeat(depth);
        System.out.println(indent + "k" + r + " (p=" + p[r] + ")");
        printTree(i, r - 1, depth + 1);
        printTree(r + 1, j, depth + 1);
    }

    /**
     * 打印DP表（保留4位小数）
     */
    public void printDPTable() {
        System.out.println("期望搜索代价DP表:");
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (j < i) {
                    System.out.printf("%8s ", "-");
                } else {
                    System.out.printf("%8.4f ", dp[i][j]);
                }
            }
            System.out.println();
        }
    }

    /**
     * 获取最优根节点表
     */
    public int[][] getRootTable() {
        return root;
    }

    public static void main(String[] args) {
        // 示例：5个关键字
        // 成功概率 p[1..5]
        double[] p = {0, 0.15, 0.10, 0.05, 0.10, 0.20};
        // 失败概率 q[0..5]
        double[] q = {0.05, 0.10, 0.05, 0.05, 0.05, 0.10};

        OptimalBST obst = new OptimalBST(p, q);
        double minCost = obst.solve();
        System.out.printf("最小期望搜索代价: %.4f\n", minCost);
        System.out.println("\n最优二叉搜索树结构:");
        obst.printTree(1, 5, 0);
        obst.printDPTable();

        // 验证：概率之和应为1
        double sumP = 0, sumQ = 0;
        for (int i = 1; i <= 5; i++) sumP += p[i];
        for (int i = 0; i <= 5; i++) sumQ += q[i];
        System.out.printf("\n概率验证: p总和=%.2f, q总和=%.2f, 总计=%.2f\n",
                sumP, sumQ, sumP + sumQ);
    }
}

算法复杂度分析

• 状态数量：O(n²)，共有 n(n+1)/2 个区间
• 状态转移：每个状态枚举根节点，O(n)
• 总时间复杂度：O(n³)
• 空间复杂度：O(n²)，存储dp表、根节点表和概率前缀和

Knuth优化

若概率分布满足单调性，可利用Knuth优化将复杂度降至 O(n²)。核心观察是：root[i][j-1] ≤ root[i][j] ≤ root[i+1][j]，因此枚举根节点时不需要从 i 到 j 全部扫描。

算法对比与应用

应用场景

• 静态字典：编译器保留字表，概率已知且不变
• 数据库索引：读多写少的表，可基于查询日志统计频率
• 文件系统：目录项查找，高频目录优先靠近根

最优二叉搜索树展示了动态规划如何将组合优化问题分解为可重叠的子问题。与矩阵链乘类似，它采用区间DP框架，但引入了概率权重，使状态转移更具物理意义。理解OBST的关键在于把握”子树概率和作为深度增量”这一核心直觉。