【动态规划】最优二叉搜索树——算法设计与分析-Toy模板网

这篇具有很好参考价值的文章主要介绍了【动态规划】最优二叉搜索树——算法设计与分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、问题定义

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=-\infin,x_{n+1}=+\infin$

记 $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,…,n$ ，空隙 $L_j$ 的深度为 $d(L_j),j=0,1,…,n$ ，平均比较次数为：
$m(T)=\sum_{i=1}^{n}b_i(1+d(x_i))+ \sum_{j=0}^{n}a_jd(L_j)$
例如，给定树：

最优二叉查找树,算法设计与分析,算法,动态规划,数据结构

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

则平均检索时间为：

$m (T_1)= [1×0.1+2×(0.2+0.05) +3×(0.1+0.2+0.1)]+[3×(0.04+0.01+0.05+0.02+ 0.02+0.07)+2×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}, … , 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\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$
最优二叉查找树,算法设计与分析,算法,动态规划,数据结构

（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
$\quad i=1,2,...,n$

不妨以 $m [1, 4]$ 来观察：
$m[1,4]=min\left\{\begin{matrix} 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{matrix}\right.$