基于C++实现的最优二分查找树

Pubertyly

发布日期: 2019-03-12 21:12:49 浏览量: 460
评分:
star star star star star star star star star_border star_border
*转载请注明来自write-bug.com

1、实验题目

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

  • k2为根

  • k1为k2的左孩子

  • d0为k1的左孩子

  • ……

表3-1 搜索概率表

i 0 1 2 3 4 5
pi 0.15 0.10 0.05 0.10 0.20
qi 0.05 0.10 0.05 0.05 0.05 0.10

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矩阵。

最优二叉搜索树测试

最优二叉搜索树测试

上传的附件 cloud_download 基于C++实现的最优二分查找树.7z ( 81.60kb, 1次下载 )
error_outline 下载需要5点积分

发送私信

走在一起是缘分,一起在走是幸福

17
文章数
16
评论数
最近文章
eject