问题描述
二叉搜索树
二叉搜索树满足如下性质：假设 $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’$，则 $T’$ 必是关于关键字集合 $key[i:j]$ 子问题的最优解。这说明问题的最优解包括子问题最优解，可以运用动态规划的方法避免子问题的重复计算。
$dp[i, j]$ 表示 $key[i + 1:j]$ 构造的最优二叉树的代价（平均搜索长度），则 $dp[0, n]$ 是最后结果。$w[i, j]$ 表示权值，为 $p[i + 1:j]$ 与 $q[i:j]$ 之和。
$$ \begin{align*} w[i, j] = \sum_{k = i + 1}^{j} p[k] + \sum_{k=i}^{j} q[k] \end{align*} $$关键字 $key[i + 1:j]$ 以 $k$ 为根的最优二叉树代价为：
$$ \begin{align*} 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{align*} $$其中，$p[k]$ 为根的代价，$dp[i, k - 1]$ 为左子树的代价，$w[i, k - 1]$ 为左子树加一层的代价，$dp[k, j]$ 为右子树的代价，$w[k, j]$ 为右子树加一层的代价。
因而，关键字 $key[i + 1:j]$ 的最优二叉树代价为：
$$ \begin{align*} dp[i, j] = w[i, j] + \min\{dp[i, k - 1], dp[k, j]\}, i < k \le j \end{align*} $$其中，$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)$