最优二叉搜索树

缘起

具体的缘起就是设计一款英文翻译到中文的程序软件, 希望每次输入英文搜索次数的期望是最小的. 以前介绍过的AVL、红黑树等结构未必能给出最优解是因为他们假定的是每个节点被搜的概率是相等的. 但实际上，英文单词与英文单词之间出现的概率是不一样的. 所以最优解未必长成之前的平衡二叉树的样子.

我们定义最优二叉搜索树为

1
2
1. 是一棵bst
2. 使得搜索的期望次数（不论是搜到或者没搜到）最小, 搜索期望次数的定义详见【1】的公式15.11

详细背景和算法参见【1】的15.5小节. 关于最优二叉搜索树（Optimal-BST, 下简称opt-bst）的算法，算导上已经将的异常清晰了. 不想拷贝经典.

分析

但是这里因为是动态规划（DP）的第一篇文章，我还是想提及一下动态规划的解决思路， 其实在算导的这一节的步骤中也提及了.

  1. 确定本问题是否有最优子结构特性, 该特性是使用dp的前提
  2. 如果1满足，则导出递推公式.

为了能较好的理解下面的算法，po一张算导上的图（带有5个关键词（n=5），即5个英语单词，6种搜索失败情形的二叉搜索树）

就知道 k1,…,kn （代表搜到了，即算导中讲opt-bst的背景的时候提到的英文单词）和 d0,…,dn（代表没搜到）的含义了. opt-bst 的目的就是求出bst的一种组织方式，使得每次输入英文单词，搜索次数的期望达到最小, 因为p1,..,pn和q0,…,qn 未必相等，所以未必是平衡二叉树. 换言之，平衡二叉树未必（其实一般不是）opt-bst.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include "stdafx.h"
#include <iostream>

using namespace std;
#define LOCAL
const int INF = 0x3f3f3f3f;
const int MAX_N = 7; // 英语单词的最多个数（背景参见算导）

double e[MAX_N][MAX_N], w[MAX_N][MAX_N];
int root[MAX_N][MAX_N]; // e[i][j] 是 [ki,...,kj] 形成最优二叉搜索树（以下简称opt-bst）的最小期望, w[i][j]参见算导, root[i][j] 表示关键词[ki,...,kj](j>=i才有意义)（从而会搭上d_{i-1},...,dj）形成opt-bst的根节点, 注意, 对于e[i+1][i] = qi(0<=i<=n), 即di的概率(其中内部节点是k1,...,kn(代表搜索成功), 对应概率是 p1,..,pn， 叶子节点是d0,..,dn（代表搜索失败）， 概率是q0,...,qn), w[i+1][i]=qi(0<=i<=n), 这个参见算导上对w的定义, root[i][i]=i(1<=i<=n), 这个根据root[i][j]的定义就知道了
int n = 5; // 本代码考察只有5个关键词的情形，注意，假定这5个关键词按照升序排序, 因为最优二叉搜索树的前提是一棵BST
double p[MAX_N] = {0, 0.15, 0.1, 0.05, 0.1, 0.2}, q[MAX_N] = {0.05, 0.10, 0.05, 0.05, 0.05, 0.10}; // 出现k1,..,kn(n=5)和d0,...,d5的概率

void init() // 初始化
{
	for (int i = 0; i<=n; i++)
	{
		e[i+1][i] = w[i+1][i] = q[i];
		root[i][i] =i; // ki (with d_{i-1}, d[i] 构成的树的根显然是ki)
	}

	for (int i = 1; i<=n;i++)
	{
		for (int j = i; j<=n; j++)
		{
			e[i][j] = INF; // 因为要求最小, 所以初始化都是最大
			w[i][j] = w[i][j-1]+p[j]+q[j]; // 这个是根据w[i][j]的定义（参见算导15.12公式）
		}
	}
}

void build() // dp, 基于算导 15.14 公式, 正因为此公式，所以我们的for循环会写成这个样子， 为了更好理解这里的dp，请看附录图1
{
	for (int k = 1; k<=n; k++) // 见图1中的k
	{
		for (int i = 1; i<=n-k+1; i++) // i的变化范围, 说白了就是沿着斜对角线移动(i,j), 所以k和i一定下来, j就是固定的了
		{
			int j = i+k-1; // j是固定取值， 
			for (int r = i; r<=j; r++)
			{
				double t = e[i][r-i] + e[r+1][j] +w[i][j];
				if (e[i][j] > t) // 根据 15.14 公式计算 e[i][j]
				{
					root[i][j] = r; // 更新root
					e[i][j] = t; // 更新 e[i][j]
				}
			}
		}
	}
	cout << "最小期望为" << e[1][n] << endl;
}

void print(int i, int j) // 打印 [ki,..,kj]关键词形成的opt-bst
{
	if (i>j) return;
	int r = root[i][j];
	printf("当前根节点是%d", r);
	if (i==j)
	{
		puts("");
		return;
	}
	if (r-1>=i) printf(",它的左孩子是%d", root[i][r-1]);// 因为r的范围仅仅是 [i,j] 所以可能出现越界的情况
	if (r+1<=j) printf(",它的右孩子是%d",root[r+1][j]);
	puts("");
	print(i,r-1); // 递归打印
	print(r+1,j);
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif

	init();
	build();
	print(1, n);

	return 0;
}

很显然，最优（静态）二叉搜索树的构建复杂度是O(n^3), 正因为如此比较尴尬的复杂度，所以在【2】的9.1节也说了，最优静态二叉搜索树实际用的并不多. 一般用的是 次优二叉搜索树（见我的下一篇文章）

参考

【1】算法导论第三版

【2】数据结构（C语言版） 严蔚敏 吴伟民

附录

​ 图1