折半查找判定树及平均查找长度.doc_第1页
折半查找判定树及平均查找长度.doc_第2页
折半查找判定树及平均查找长度.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

精品文档折半查找判定树及平均查找长度从折半查找的过程看，以有序表的中间记录作为比较对象，并以中间记录将表分割为两个子表，对子表继续上述操作。所以，对表中每个记录的查找过程，可用二叉树来描述，二叉树中的每个结点对应有序表中的一个记录，结点中的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树。长度为n的折半查找判定树的构造方法为： 当n=0时，折半查找判定树为空； 当n0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r1 rmid-1相对应的折半查找判定树，根结点的右子树是与rmid+1 rn相对应的折半查找判定树。例如，长度为10的折半查找判定树的具体生成过程为： 在长度为10的有序表中进行折半查找，不论查找哪个记录，都必须先和中间记录进行比较，而中间记录的序号为(1+10)/2=5（注意是整除即向下取整），即判定树的根结点是5，如图7-2(a)所示； 考虑判定树的左子树，即将查找区间调整到左半区，此时的查找区间是1，4，也就是说，左分支上为根结点的值减1，代表查找区间的高端high，此时，根结点的左孩子是(1+4)/2=2，如图7-2(b)所示； 考虑判定树的右子树，即将查找区间调整到右半区，此时的查找区间是6，10，也就是说，右分支上为根结点的值加1，代表查找区间的低端low，此时，根结点的右孩子是(6+10)/2=8，如图7-2(c)所示； 重复步，依次确定每个结点的左右孩子，如图7-2(d)所示。对于折半查找判定树，需要补充以下两点： 折半查找判定树是一棵二叉排序树，即每个结点的值均大于其左子树上所有结点的值，小于其右子树上所有结点的值； 折半查找判定树中的结点都是查找成功的情况，将每个结点的空指针指向一个实际上并不存在的结点称为外结点，所有外结点即是查找不成功的情况，如图7-2(e)所示。如果有序表的长度为n，则外结点一定有n+1个。在折半查找判定树中，某结点所在的层数即是查找该结点的比较次数，整个判定树代表的有序表的平均查找长度即为查找每个结点的比较次数之和除以有序表的长度。例如，长度为10的有序表的平均查找长度为：ASL=(11+22+34+43)/10=29/10在折半查找判定树中，查找不成功时的比较次数即是查找相应外结点时与内结点的比较次数。整个判定树代表的有序表在查找失败时的平均查找长度即为查找每个外结点的比较次数之和除以外结点的个数。例如，长度为10的有序表在查找失败时的平均查找长度为：ASL=(35+46)/11=39/11欢
人人文库> 全部分类> 应用文书 > 事务文书

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论