最优二叉搜索树

问题描述

二叉搜索树

二叉搜索树满足如下性质：假设 $x$ 是二叉搜索树中的一个结点。如果 $l$ 是 $x$ 的左子树的一个结点，那么 $l.key\le x.key$。如果 $r$ 是 $x$ 的右子树的一个结点，那么 $r.key\ge x.key$。

也就是说，二叉搜索树中的任意一个结点，它的左子树中的所有结点都不大于它，它的右子树中的所有结点都不小于它。

最优二叉搜索树

假设有 $n$ 个有序的 $key$，每个 $key$ 搜索概率不同，除 $key$ 之外的值（即搜索不成功情况）搜索概率也不同，构造平均搜索长度最小的二叉树。

$i$	0	1	2	3
$key$		10	20	30
$p$		$0.5$	$0.1$	$0.05$
$q$	$0.15$	$0.1$	$0.05$	$0.05$

上表给出了此问题的一个输入样例。$p$ 表示搜索成功的概率，例如搜索到 10 的概率为 $0.5$。$q$ 表示搜索失败的概率，落在了某两个 $key$ 之间或者某个 $key$ 之外。例如，小于 10 的元素的搜索概率为 $0.15$，大于 10 而小于 20 的元素的搜索概率为 $0.1$，以此类推。

问题分析

如果优化二叉搜索树 $T$ 具有包含关键字集合 $key[i:j]$ 子树 $T^{\prime }$，则 $T^{\prime }$ 必是关于关键字集合 $key[i:j]$ 子问题的最优解。这说明问题的最优解包括子问题最优解，可以运用动态规划的方法避免子问题的重复计算。

$dp[i,j]$ 表示 $key[i+1:j]$ 构造的最优二叉树的代价（平均搜索长度），则 $dp[0,n]$ 是最后结果。$w[i,j]$ 表示权值，为 $p[i+1:j]$ 与 $q[i:j]$ 之和。

$$\begin{array}{r}w[i,j]=\sum _{k=i+1}^{j}p[k]+\sum _{k=i}^{j}q[k]\end{array}$$

关键字 $key[i+1:j]$ 以 $k$ 为根的最优二叉树代价为：

$$\begin{array}{rl}dp[i,j{]}_k& =p[k]+dp[i,k-1]+w[i,k-1]+dp[k,j]+w[k,j]\\ & =w[i,j]+dp[i,k-1]+dp[k,j]\end{array}$$

其中，$p[k]$ 为根的代价，$dp[i,k-1]$ 为左子树的代价，$w[i,k-1]$ 为左子树加一层的代价，$dp[k,j]$ 为右子树的代价，$w[k,j]$ 为右子树加一层的代价。

因而，关键字 $key[i+1:j]$ 的最优二叉树代价为：

$$\begin{array}{r}dp[i,j]=w[i,j]+min\{dp[i,k-1],dp[k,j]\},i<k\le j\end{array}$$

其中，$w[i,j]$ 为树上权值和。上述方程即为本题的状态转移方程。

问题求解

首先各 $key$ 自成二叉搜索树，计算平均搜索长度，保留最小值。代价数组 $dp$ 的主对角线初始化。

接下来，计算相邻 2 个、3 个 $key$ 的平均搜索长度，保留最小值，直至计算到第 $n$ 个 $key$。代价数组 $dp$ 开始向右上角发展，最终右上角的结果即为解。

算法代码

double Optimal_BST(double *p, double *q, int n)
{
    // 初始化
    double **c = new double *[n + 1];
    double **w = new double *[n + 1];
    for (int i = 0; i < n + 1; i++)
    {
        c[i] = new double[n + 1];
        w[i] = new double[n + 1];
        c[i][i] = 0;
        w[i][i] = q[i];
    }
    // 计算
    for (int x = 1; x < n + 1; x++) // x 表示计算相邻的 x+1 个子树
    {
        for (int i = 0; i < n - x; ++i)
        {
            int j = i + x;
            c[i][j] = 65535; // 初始化为无穷大
            w[i][j] = w[i][j - 1] + p[j] + q[j];
            for (int k = i; k < j + 1; ++k) // 以 k 为根
            {
                double t = w[i][j];
                if (k - 1 >= i) // 注意边界，下同
                {
                    t += c[i][k - 1];
                }
                if (k + 1 <= j)
                {
                    t += c[k + 1][j];
                }
                if (t < c[i][j]) // 保留最小值
                {
                    c[i][j] = t;
                }
            }
        }
    }
    double res = c[0][n];
    // 释放堆空间
    for (int i = 0; i < n + 1; i++)
    {
        delete c[i];
        delete w[i];
    }
    delete c;
    delete w;
    return res;
}

算法分析

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(n^2)$