---

一、问题定义

1.1 二叉搜索树

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。

规定树根为第0层，圆结点为数据，方结点为数据之间的空隙。

1.2 概率分布

实际上每个数据出现的概率是不同的，给定序列$S=<x_1,x_2,...,x_n>$，构造二叉搜索树，形成了$n$个结点$x_1,x_2,...,x_n$，和$n+1$个空隙$(x_0,x_1),(x_1,x_2),...,(x_{n-1},x_n),(x_n,x_{n+1})$，其中$x_0=-\infty ,x_{n+1}=+\infty$

记$x$在$x_i$出现的概率为$b_i$，在空隙$(x_i,x_{i+1})$的概率为$a_i$，则$S$的存取概率分布为$P=<a_0,b_1,a_1,b_2,a_2,...,b_n,a_n>$

1.3 检索数据的平均时间

对于数据集$S=<x_1,x_2,...,x_n>$和存取概率分布$P=<a_0,b_1,a_1,b_2,a_2,...,b_n,a_n>$：

规定树根为第0层，结点$x_i$在$T$中的深度是$d(x_i),i=1,2,\dots ,n$，空隙$L_j$的深度为$d(L_j),j=0,1,\dots ,n$，平均比较次数为：
$$m(T)=\sum _{i=1}^n{b}_i(1+d(x_i))+\sum _{j=0}^n{a}_{j}d(L_j)$$
例如，给定树：

$S=<1,2,3,4,5,6>$，$P=<0.04,\ast 0.1\ast ,0.01,\ast 0.2\ast ,0.05,\ast 0.2\ast ,0.02,\ast 0.1\ast ,0.02,\ast 0.1\ast ,0.07,\ast 0.05\ast ,0.04>$（$p_{x_i}$用**包围）

则平均检索时间为：

$m(T_1)=[1\times 0.1+2\times (0.2+0.05)+3\times (0.1+0.2+0.1)]+[3\times (0.04+0.01+0.05+0.02+0.02+0.07)+2\times 0.04]=2.51$

1.4 最优二叉搜索树问题

对于数据集$S=<x_1,x_2,...,x_n>$和存取概率分布$P=<a_0,b_1,a_1,b_2,a_2,...,b_n,a_n>$，不同的树的组织形式会产生不同的平均检索时间，如何求一棵平均比较次数最少的二叉搜索树？

---

二、算法

2.1 分析问题结构

以$(i,j)$为界划分子问题：

令$S[i,j]=<x_i,x_{i+1},\dots ,x_j>$，存取概率分布：$P=<a_{i-},b_i,a_i,b_{i+1},...,b_j,a_j>$

2.2 建立递推关系

假设以$x_k$作为树的根，则树被划分为三部分：

左子树：$S[i,k-1],P[i,k-1]$

根：$x_k$

右子树：$S[k+1,j],P[k+1,j]$

令$w[i,j]={\sum }_{p=i-1}^j{a}_p+{\sum }_{q=i}^j{b}_q$，表示$x_i$到$x_j$之间所有概率（数据和空隙）之和；设$m[i,j]$是相对于输入$S[i,j]$和$P[i,j]$的最优二叉搜索树的平均比较次数

则可建立递推方程：
m [ i , j ] = min ⁡ i ≤ k ≤ j { m [ i , k − 1 ] + m [ k + 1 , j ] + w [ i , j ] } 1 ≤ i ≤ j ≤ n m [ i , i − 1 ] = 0 , i = 1 , 2 , . . . , n m[i,j]=\min_{i\leq k\leq j}\left \{ m[i,k-1]+m[k+1,j]+w[i,j] \right \} \quad 1\leq i\leq j\leq n \\ m[i,i-1]=0, \quad i=1,2,...,n m[i,j]=i≤k≤jmin​{m[i,k−1]+m[k+1,j]+w[i,j]}1≤i≤j≤nm[i,i−1]=0,i=1,2,...,n

（1）为了不遗漏最优解，所以需要从$x_1$到$x_k$依次选取做根尝试，选出最小值

（2）$m[i,k-1]$表示以$x_k$做根的最优左子树的比较次数

（3）$m[k+1,j]$表示以$x_k$做根的最优右子树的比较次数

（4）对于给定的数据$x$，需要先与根$x_k$进行比较后才可以进入到左子树或右子树；而由于使用根$x_k$将左子树和右子树连接起来，子树的每个结点高度均增加了一层，所以在比较次数上也要加1，所以$w[i,j]$是由增加的左子树的比较次数、增加的右子树的比较次数、和根的比较次数之和

$w[i,j]$的证明：

由根$x_k$引起的比较次数增加为：

2.3 自底向上计算

初始化：当左子树或右子树为空时，其平均查找数为0
$$m[i,i-1]=0,i=1,2,...,n$$

不妨以$m[1,4]$来观察：
$$m[1,4]=min\{\begin{array}{cc}m[1,0]+m[2,4]+w[1,4]& k=1\\ m[1,1]+m[3,4]+w[1,4]& k=2\\ m[1,2]+m[4,4]+w[1,4]& k=3\\ m[1,3]+m[5,4]+w[1,4]& k=4\end{array}$$

	0	1	2	3	4
0	NULL	NULL	NULL	NULL	NULL
1	0 √	√	√	√	※
2	NULL	0			√
3	NULL	NULL	0		√
4	NULL	NULL	NULL	0	√
5	NULL	NULL	NULL	NULL	√

显然，要计算一个值，我们需要计算它一行一列的数据，因此确定计算顺序：

2.4 追踪最优方案

构造追踪数组$Rec[\mathrm{1..}n,\mathrm{1..}n]$，$Rec[i,j]$表示$S[i,j]$的根节点$x_k$。

在计算$m[i,j]$的过程中，选出最小的$k$，记录$Rec[i,j]=k$

追踪时，从$Rec[1,n]$出发，假设$Rec[1,n]=k$，则说明在$x_k$处进行了分割，分为子树$m[1,k]$和$m[k+1,n]$，再分别查看$Rec[1,k]$和$Rec[k+1,n]$…

如此寻找直至对角线部分。

2.5 复杂度分析

时间复杂度$O(n^3)$

空间复杂度$O(n^2)$