有序表的折半查找_徐龙伟.pptx

数据结构研讨第九周 组员： 徐龙伟 朱 伟 蒋 涛 宋雄彬 研讨题目 画出表长为20的有序表进行折半查找的判定树，并求解在等概率情况下查找成功和失败的平均查找长度。 折半查找判定树 从折半查找的过程看，以有序表的中间记录作为比较对象，并以中间记录将表分割为两个子表，对子表继续上述操作。所以，对表中每个记录的查找过程，可用二叉树来描述，二叉树中的每个结点对应有序表中的一个记录，结点中的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树。 构造方法 长度为n的折半查找判定树的构造方法为： ?⑴?当n=0时，折半查找判定树为空； ?⑵?当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1]?~?r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1]?~?r[n]相对应的折半查找判定树。 长度为20的有序表的折半查找判定树： ⑴?在长度为20的有序表中进行折半查找，不论查找哪个记录，都必须先和中间记录进行比较，而中间记录的序号为(1+20)/2=10（注意是整除即向下取整），即判定树的根结点是10 ⑵?考虑判定树的左子树，即将查找区间调整到左半区，此时的查找区间是[1，9]，也就是说，左分支上为根结点的值减1，代表查找区间的高端high，此时，根结点的左孩子是(1+9)/2=5 ⑶?考虑判定树的右子树，即将查找区间调整到右半区，此时的查找区间是[11，20]，也就是说，右分支上为根结点的值加1，代表查找区间的低端low，此时，根结点的右孩子是(11+20)/2=15 ⑷?重复⑵⑶步，依次确定每个结点的左右孩子。 折半查找判定树 3 8 11 13 1 6 16 19 2 7 12 18 5 15 10 4 9 14 17 20 查找成功与失败的平均查找长度 ⑴折半查找判定树是一棵二叉排序树，即每个结点的值均大于其左子树上所有结点的值，小于其右子树上所有结点的值；? ⑵?折半查找判定树中的结点 都是查找成功的情况，将每个 结点的空指针指向一个实际上 并不存在的结点——称为外结 点，所有外结点即是查找不成 功的情况，如图所示。如果有序表的长度为n，则外结点 一定有n+1个。 （1）在折半查找判定树中，某结点所在的层数即是查找该结点的比较次数，整个判定树代表的有序表的平均查找长度即为查找每个结点的比较次数之和除以有序表的长度。则，长度为20的有序表的平均查找长度为： ? ASL [succ]=(1×1+2×2+3×4+4×8+5×5)/20=74/20? （2）在折半查找判定树中，查找不成功时的比较次数即是查找相应外结点时与内结点的比较次数。整个判定树代表的有序表在查找失败时的平均查找长度即为查找每个外结点的比较次数之和除以外结点的个数。则，长度为20的有序表在查找失败时的平均查找长度为： ? ASL [unsucc]=(5×11+6×10)/21=115/21 谢谢~