1、实验题目

设计算法，输入如表3-1，输出是最优二叉搜索树的结构，形如：

• k2为根

• k1为k2的左孩子

• d0为k1的左孩子

• ……

表3-1 搜索概率表

2、设计思路

用动态规划思想求解最优二分查找树问题。

2.1 最优子结构

如果一棵最优二叉搜索树T有一棵包含关键字ki,…,kj的子树T’，则T’必然是包含关键字ki,…,kj和伪关键字di-1,…,dj的子问题的最优解。

用剪切-粘贴法证明：

对关键字ki,…,kj和伪关键字di-1,…,dj，如果存在子树T’’，其期望搜索代价比T’低，那么将T’从T中删除，将T’’粘贴到相应位置，则可以得到一棵比T期望搜索代价更低的二叉搜索树，与T是最优的假设矛盾。

2.2 递归解

利用最优二叉搜索树的最优子结构性来构造最优二叉搜索树。

对给定的关键字ki,…,kj，若其最优二叉搜索树的根结点是kr（i≤r≤j），则kr的左子树中包含关键字ki,…,kr-1及伪关键字di-1 ,…,dr-1，右子树中将含关键字ki+1,…,kj及伪关键字dr,…,dj。

检查所有可能的根结点kr（i≤r≤j），如果事先分别求出含关键字ki,…,kr-1和关键字kr+1,…,kj的最优二叉搜索子树，则可保证找到原问题的最优解。

求解包含关键字ki,…,kj的最优二叉搜索树，其中， i≥1，j≤n 且 j≥i-1。定义e[i,j]：为包含关键字ki,…,kj的最优二叉搜索树的期望搜索代价。

e[1,n]为问题的最终解。

当j≥i时，我们需要从ki,…,kj中选择一个根结点kr，其左子树包含关键字ki,…,kr-1且是最优二叉搜索子树，其右子树包含关键字kr+1,…, kj且为最优二叉搜索子树。

子树的每个结点的深度增加1，根据二叉搜索树的期望搜索代价计算公式，这棵子树对根为kr的树的期望搜索代价的贡献是其期望搜索代价+其所含所有结点的概率之和：

若kr为包含关键字ki,…,kj的最优二叉搜索树(树根)，则其期望搜索代价与左、右子树的期望搜索代价e[i,r-1]和e[r+1,j]有如下递推关系：

其中，

故有：

求kr的递归公式为：

3、运行演示

测试用例已经在代码中写入，运行程序，结果如图3-1和图3-2，先输出最优二叉搜索树的结构，再输出搜索代价、根节点矩阵、e矩阵和w矩阵。

最优二叉搜索树测试

最优二叉搜索树测试