最优二叉搜索树问题（Java）

1、前置介绍

设S={x₁, x₂, … , x_n} 是有序集， 且x₁ < x₂ < … < x_n, 表示有序集S的二叉搜索树利用二叉树的结点存储有序集中的元素。

它具有下述性质：存储于每个结点中的元素x_i大于其左子树中任一结点所存储的元素，小于其右子树中任一结点所存储的元素。 二叉搜索树的叶结点是形如(x_i，x_i+1）的开区间。在表示S的二叉搜索树中搜索元素x, 返回的结果有以下两种情形：

• 在二叉搜索树的内结点中找到 x=x_i;
• 在二叉搜索树的叶结点中确定x属于 (x_i, x_i+1）。

最优二叉搜索树的形式化定义如下：给定一个n个不同关键字的已排序的序列K={k₁, k₂, …, k_n}(因此k₁ < k₂ < … < k_n)，通过这些关键字来构建最优二叉搜索树。对于每个关键字k_i作为「实节点」，都有一个概率 p_i 与之对应(n个)，表示其搜素频率「概率p下标从1开始对于每个关键字」。

但是有些要搜索的值可能不在K序列中， 因此我们还需要使用n+1个「伪关键字」d₀, d₁， d₂, … , d_n. 表示不在序列K中的值。d₀表示所有小于k₁如的值，d_n表示所有大于k_n的值，对i=l, 2, … , n—1, 伪关键字d_i 表示所有在k_i和k_i+1之间的值。对每个伪关键字d_i, 也都有一个概率 q_i 表示对应的搜索频率「概率q下标从0开始对于每个伪关键字」。

下图中，显示了对一个n=5个关键字的集合构造的两棵二叉搜索树。每个关键字k_i是一个内部结点， 而每个伪关键字d_i是一个叶结点。每次搜索要么成功（找到某个关键字k_i)要么失败（找到某个伪关键字d_i），因此有以下公式：

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

对一个n=5的关键字集合及如下的搜索概率，构造的两棵二叉搜索树：

搜索代价如下公式②：

$$E[T中搜索代价] = \sum_{i=1}^{n}(depth_T(k_i) + 1)• P_i + \sum_{i=0}^{n}(depth_T(d_i) + 1)• q_i\\ = 1 + \sum_{i=1}^{n}depth_T(k_i)• p_i + \sum_{i=1}^{n}depth_T(d_i)• q_i)$$

2、算法设计思路

2.1 最优二叉搜索树的结构

2.2 一个递归算法

求解包含关键字k_i, …，k_j的最优二叉搜索树， 其中 i <= 1 ，j <=n 且 $j \geq i一1$ (当 j = i - 1 时， 子树不包含实际关键字，只包
含伪关键字d_i-1)。定义e[i,j] 为在包含关键字k_i, …，k_j的最优二叉搜索树中进行一次搜索的期望代价。最终，我们希望计算出e[1, n]。

以下分为两种情况；

• j=i-1时最简单，因为子树只包含伪关键字d_i-1，此时的期望搜索代价为e[i, i—1]=q_i-1

• j>=i 时，我们需要从从k_i, … ，k_j中选择一个根结点k_r, 然后构造一棵包含关键字k_i, …, k_r-1的最优二叉搜索树作为其左子树，以及一棵包含关键字k_r+1, …, k_j的二叉搜索树作为其右子树。

当一棵子树成为一个结点的子树时，由于每个结点的深度都增加了1, 根据公式②, 这棵子树的期望搜索代价的增加值应为所有概率之和。对于包含关键字k_i, … , k_j的子树， 所有概率之和为以下公式③：

$$w(i,j) = \sum_{l=i}^{j}p_i + \sum_{l=i-1}^{j}q_i$$

因此，若k_i, … , k_j 的最优二叉搜索树的根结点，我们有如下公式④：

$$w(i,j) = w(i,r-1) + p_r + w(r+1,j)$$

因此e[i,j]可重写为:如下公式⑤

$$e[i,j] = e[i,r-1] + e[r+1,j] + w(i,j)$$

递归公式⑤假定我们知道哪个结点k应该作为根结点。如果选取期望搜索代价最低者
作为根结点，可得最终递归公式⑥：

$$e[i,j] = \begin{cases} q_i-1& \text{j = i - 1}\\ min_{i<=1<=j}\{e[i, r-1] + e[r+1,j]+w(i,j)\}& \text{i<=j} \end{cases}$$

e[i,j]的值给出了最优二叉搜索树的期望搜索代价。

2.3 计算最优二叉搜索树的期望搜索代价

伪代码如下：

根据前文的描述，以及与算法MATRIX-CHAIN-ORDER的相似性，很容易理解此算法。第2-4行的for循环初始化e[i, i —1]和w[i, i —1]的值。第5-14行的for循环利用
递归式⑥和递归式(15. 15)来对所有 $1 \leq i \leq j \leq n$计算e[i, j]和w [i, j]。

在第一个循环步中，l= l, 循环对所有i = 1, 2, …, n计算e[i, j]和w[i, i]。第二个循环步中， l = 2, 对所有i = 1, 2, …, n — 1 计算e[i, i+l]和w[i, i+l], 依此类推。第10-14行的内层for循环，逐个尝试下标r, 确定哪个关键字k, 作为根结点可以得到包含关键字k_i, …，k_j的最优二叉搜索树。这个for循环在找到更好的关键字作为根结点时，会将其下标r保存在root[i, j]中。

下图给出了OPTIMAL-EST输入图1中的关键字分布后计算出的表e[i, j]、w[i, j]和
写root[i, j]。本图中的表进行了旋转，对角线旋转到了水平方向。OPTIMAL-EST按自底向上的顺序逐行计算，在每行中由左至右计算每个表项。

3、代码实现

动态规划解决最优二叉搜索树

/**
 * TODO 实现最优二叉树算法
 */
public class t4 {

    public static void main(String[] args) {
        // TODO p[1, 5]是 5个实节点的概率 p[0]不存在，对应每一个关键字的搜索频率
        double[] p = {0, 0.15, 0.1, 0.05, 0.1, 0.2};
        // TODO q[0, 5]是 6个伪节点的概率
        double[] q = {0.05, 0.1, 0.05, 0.05, 0.05, 0.1};
        // TODO 一共5个关键字（可以搜索得到的，即实节点）
        int n = p.length - 1;

        // TODO root[i][j]记录的是最终得出的[i,j]这个子段里的根节点
        int[][] root = optimalBinarySearchTree(p, q, n);
        // TODO root的 length 是 n+2, i 和 j 只需要循环到 n
        int temp = root.length - 1;
        // TODO 输出一下这个root矩阵，直接根据这个矩阵也可以画出来最优二叉搜索树
        //  root矩阵将对角线旋转到水平方向更直观地看到最优二叉搜索树
        for (int i = 1; i < temp; i++) {
            for (int j = 1; j < temp; j++) {
                System.out.print(root[i][j] + "-");
            }
            System.out.println();
        }
    }

    private static int[][] optimalBinarySearchTree(double[] p, double[] q, int n) {
        // TODO e[i][j]表示 i 到 j 这段的代价
        //  e[1][0]为左边只包含伪节点d0的代价...e[n+1][n]为左边只包含伪节点dn的代价
        double[][] e = new double[n + 2][n + 2];
        // TODO i 到 j 这一段的总概率，在加一层根节点时需要用到
        //  为避免每次计算e[i, j]都重新计算w(i,j)的值，直接将这些值存放在w数组中
        double[][] w = new double[n + 2][n + 2];
        // TODO root[i][j]记录的是最终得出的[i,j]这个子段里的根节点
        int[][] root = new int[n + 2][n + 2];

        // TODO 初始化
        for(int i = 1; i < n + 1; i++) {
            e[i][i - 1] = q[i - 1];
            w[i][i - 1] = q[i - 1];     // 1 <= i <= n + 1的情况
        }
        // TODO ：l是 [i, j]区间的长度，相当于一个固定l长度的小节从最左边循环到最右边。
        //  然后再把l逐渐加大，重复从左到右。
        //  这样就使得小长度的都先计算过，为大长度的片段分解为左右两个字片段计算时提供了已经计算好的值，这也是动态规划的精髓之一。
        //  这样做是为了从小到大积累动态规划的能量
        for (int l = 1; l <= n; l++) {
            for (int i = 1; i <= n - l + 1; i++) {
                int j = i + l - 1;
                // TODO 初始化为最大值，最后才能找出真正最小的，从而找到最优解
                e[i][j] = Double.MAX_VALUE;
                // TODO j >= i的情况
                w[i][j] = w[i][j-1] + p[j] + q[j];
                // TODO 从 i 到 j 找到最优的根节点（选择以 r 为根节点）
                for(int r = i; r <= j; r++) {
                    // TODO 加了一层，相当于下面的左子树右子树都加了一布，其实就是最终比没加一层根节点比多了一个w[i][j]
                    double t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                    // TODO 不断的使e[i][j]保持最小，同时记录下使代价最小的位置为最终的最优的根节点
                    if(t < e[i][j]) {
                        e[i][j] = t;
                        root[i][j] = r;
                    }
                }
            }

        }
        System.out.println("当前最小代价：" + e[1][n]);
        return root;
    }
}

4、复杂度分析

与MATRIX-CHAIN-ORDER 一样，OPTIMAL-BST的时间复杂度也是O(n³ )。由于它包含三重for循环，而每层循环的下标最多取n个值， 因此很容易得出其运行时间为O(n³)。

OPTIMAL-EST的循环下标的范围与MATRIX-CHAIN-ORDER不完全一样，但每个方向最多相
差1。因此，与MATRIX-CHAIN -ORDER 一样，OPTIMAL-EST的运行时间为O(n³) (从而得出运行时间为O(n³))。

5、参考资料

• 算法分析与设计（第四版）
• 算法导论第三版

全文结束！