最优二叉搜索树（Optimal Binary Search Tree, OBST）是一个经典的动态规划问题，目标是在已知键出现的概率（或频率）的情况下，构建一棵二叉搜索树，使得查找这些键的平均代价最小。

1. 问题描述

假设有一组排好序的键 K={k1,k2,…,kn}，每个键 ki 出现的概率为 pi，希望通过构建一棵二叉搜索树，使得根据键的查找代价最小。

查找代价是指查找某个键时访问的节点次数。显然，越常访问的键应该越靠近根，以减少查找代价。

2. 动态规划求解思路

最优二叉搜索树问题本质上是一个优化问题，可以通过动态规划来求解。基本思想是：

• 对于每个子树，尝试将不同的节点作为根，计算查找代价，并选择查找代价最小的根。

关键思路：

1. 子问题划分：构建子树 T(i,j) 表示从第 i 个键到第 j 个键构成的二叉搜索树，计算其最小查找代价。
2. 递归定义：若键 kr 作为子树 T(i,j) 的根，那么该树的查找代价是左子树 T(i,r−1) 和右子树 T(r+1,j) 的查找代价加上根节点的代价。
3. 动态转移方程：计算树 T(i,j) 的查找代价为：
   
   e[i,j]=r=iminj​(e[i,r−1]+e[r+1,j]+w(i,j))
   
   其中，w(i,j) 表示从第 iii 个键到第 jjj 个键的频率和，即 w(i,j)=∑k=ij​pk​

3. 动态规划实现步骤

1. 定义状态：

   • e[i,j] 表示从键 ki​ 到 kj 构成的二叉搜索树的最小查找代价。
   • w[i,j] 表示从键 ki​ 到 kj 所有键出现的总概率。

2. 初始化：

   • e[i,i−1]=0 表示空子树的代价为 0。
   • e[i,i]=pi 表示只含有一个节点的二叉搜索树，其查找代价就是该节点的出现概率。

3. 状态转移方程： 对于每个子树 T(i,j)，尝试每个节点 kr​ 作为根，计算其查找代价，并选择最小的代价：

   e[i,j]=r=iminj​(e[i,r−1]+e[r+1,j]+w[i,j])

4. 求解：

   • 从最小的子树开始填表，逐步扩展到整个树的代价 e[1,n]。

4. 动态规划算法实现

下面是最优二叉搜索树的 Java 代码实现：

public class OptimalBST {

    // 最优二叉搜索树的动态规划算法
    public static double optimalBST(int[] keys, double[] freq, int n) {
        // e[i][j] 存储从 i 到 j 键的最小查找代价
        double[][] e = new double[n + 1][n + 1];
        // w[i][j] 存储从 i 到 j 的频率和
        double[][] w = new double[n + 1][n + 1];

        // 初始化对角线, e[i][i-1] 和 w[i][i-1] 为 0
        for (int i = 1; i <= n; i++) {
            e[i][i - 1] = 0;
            w[i][i - 1] = 0;
        }

        // 初始化单个节点的代价和频率和
        for (int i = 1; i <= n; i++) {
            e[i][i] = freq[i - 1];
            w[i][i] = freq[i - 1];
        }

        // 填表，计算从较小子树到较大子树的最优代价
        for (int l = 2; l <= n; l++) {  // l 是子树的长度
            for (int i = 1; i <= n - l + 1; i++) {
                int j = i + l - 1;
                e[i][j] = Double.MAX_VALUE;
                w[i][j] = w[i][j - 1] + freq[j - 1];  // 计算频率和

                // 尝试每个节点作为根，计算最小代价
                for (int r = i; r <= j; r++) {
                    double cost = e[i][r - 1] + e[r + 1][j] + w[i][j];
                    if (cost < e[i][j]) {
                        e[i][j] = cost;
                    }
                }
            }
        }

        return e[1][n];  // 返回整个树的最小代价
    }

    public static void main(String[] args) {
        int[] keys = {10, 12, 20};      // 键值（排好序）
        double[] freq = {0.2, 0.5, 0.3};  // 键出现的频率

        double cost = optimalBST(keys, freq, keys.length);
        System.out.println("Cost of Optimal BST: " + cost);
    }
}

5. 代码详解

5.1 输入与输出

• 输入：排好序的键数组 keys[]，以及对应的出现频率数组 freq[]。
• 输出：构造最优二叉搜索树的最小查找代价。

5.2 关键步骤

1. 初始化：

   • 对角线上的元素，即 e[i][i]，表示单个键构成的二叉树，其查找代价就是该键的频率。
   • e[i][i-1] 初始化为 0，表示空树的查找代价为 0。

2. 填表：

   • 先计算较小的子树，逐步扩展到更大的子树。
   • 对每个子树 T(i,j)，遍历所有可能的根 r，计算出以 r 为根的查找代价，并选择最小的代价。

3. 结果返回：

   • 最终结果 e[1][n] 表示从第 1 个键到第 n 个键构成的最优二叉搜索树的最小查找代价。

5.3 时间复杂度

• 时间复杂度：O(n^3)，因为我们需要遍历每个子树的可能根，并且对于每个子树，计算其频率和。
• 空间复杂度：O(n^2)，需要存储查找代价和频率和的二维数组。

6. 举例说明

假设有 3 个键：K={10,12,20}，对应的频率为 {0.2,0.5,0.3}。

1. 首先计算单个节点的最优二叉搜索树，其代价就是它本身的频率。

   • e[1][1]=0.2
   • e[2][2]=0.5
   • e[3][3]=0.3

2. 接着计算两两相邻的子树的最优代价。

   • e[1][2]=min(e[1][1]+e[2][2]+0.7,e[1][1]+e[2][2]+0.7)=0.9
   • 依此类推，计算更大的子树。

最终，构造出的最优二叉搜索树的查找代价为最小值。

7. 总结

最优二叉搜索树问题是一种通过动态规划求解的优化问题，其核心思想在于通过子问题的最优解来构建全局最优解。该问题在信息检索、编译器设计（符号表的构建）以及数据压缩等领域有广泛应用。