2)若查找关键字等于给定值K=79的结点 先确定第四块,然后在该块中查找。因该 块中查找不成功,故说明表中不存在关键字为 79的结点 具体过程为: 先查索引表,将K与s[i](1<=i<=4) 看k是否小于等于S若是则块号为,图 不是将1继续查找块号;当块号为i 确定后,再定该块的起止下标,即起 始下标为s[iJow终止下标为sgh最 后按顺序查找的方法在该范围内查找 <心心 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 （2）若查找关键字等于给定值K=79的结点 先确定第四块，然后在该块中查找。因该 块中查找不成功，故说明表中不存在关键字为 79的结点。 具体过程为： 先查索引表，将K与s[i]（1<=i<=4） 看k是否小于等于s[i],若是则块号为i， 不是将i加1继续查找块号；当块号为i 确定后，再定该块的起止下标，即起 始下标为s[i].low 终止下标为s[i].gigh最 后按顺序查找的方法在该范围内查找
4、算法分析 (1)平均查找长度ASL 分块查找是两次查找过程。整个查找过程的 平均查找长度是两次查找的平均查找长度之和。 佥①以二分査找来确定块,分块查找成功时的平均 查找长度 ASL ASLh tASLs lg(b+1)1+(s+1)/2alg(n/s+1)+s/2 ②以顺序查找确定块,分块查找成功时的平 均查找长度 ASLb=(b+1)/2+(s+1)/2=(s2+2s+n)(2s) 注意:分块查找算法的效率介于顺序查找和二分查找之间 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 4、算法分析 （1）平均查找长度ASL 分块查找是两次查找过程。整个查找过程的 平均查找长度是两次查找的平均查找长度之和。 ①以二分查找来确定块,分块查找成功时的平均 查找长度 ASLblk=ASLbn+ASLsq≈lg(b+1)1+(s+1)/2≈lg(n/s+1)+s/2 ②以顺序查找确定块，分块查找成功时的平 均查找长度 ASL'blk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s) 注意：分块查找算法的效率介于顺序查找和二分查找之间
(2)块的大小 在实际应用中,分块查找不一定要将线性表分成大小相 等的若干块,可根据表的特征进行分块。 【例)一个学校的学生登记表,可按系号或班号分块。 (3)结点的存储结构 各块可放在不同的向量中,也可将每一块存放在 个单链表中。 (4)分块查找的优点 分块查找的优点是 ①在表中插入或删除一个记录时,只要找到该记录所属的块, 就在该块内进行插入和删除运算。 ②因块内记录的存放是任意的,所以插入或删除比较容易, 无须移动大量记录。 分块查找的主要代价是增加一个辅助数组的存储空间和将初 始表分块排序的运算武汉理工大学华夏学院信息工程 系
武汉理工大学华夏学院-信息工程 系 （2）块的大小 在实际应用中，分块查找不一定要将线性表分成大小相 等的若干块，可根据表的特征进行分块。 【例】一个学校的学生登记表，可按系号或班号分块。 （3） 结点的存储结构 各块可放在不同的向量中，也可将每一块存放在一 个单链表中。 分块查找的优点是： ①在表中插入或删除一个记录时，只要找到该记录所属的块， 就在该块内进行插入和删除运算。 ②因块内记录的存放是任意的, 所以插入或删除比较容易， 无须移动大量记录。 分块查找的主要代价是增加一个辅助数组的存储空间和将初 始表分块排序的运算。 （4）分块查找的优点
7.3动态查找 当用线性表作为表的组织形式时,可以有三种查找 法。其中以二分查找效率最高。但由于二分查找要求表 中结点按关键字有序,且不能用链表作存储结构,因此 →当表的插入或删除操作频繁时,为维护表的有序性,势 必要移动表中很多结点。这种由移动结点引起的额外时 间开销,就会抵消二分查找的优点。也就是说,二分查 找只适用于静态査找表。若要对动态查找表进行高效率 ●的查找,可采用下面介绍的几种特殊的二叉树或树作为 ●表的组织形式。不妨将它们统称为树表。下面将分别讨 论在这些树表上进行查找和修改操作的方法。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 7.3 动态查找 当用线性表作为表的组织形式时，可以有三种查找 法。其中以二分查找效率最高。但由于二分查找要求表 中结点按关键字有序，且不能用链表作存储结构，因此， 当表的插入或删除操作频繁时，为维护表的有序性，势 必要移动表中很多结点。这种由移动结点引起的额外时 间开销，就会抵消二分查找的优点。也就是说，二分查 找只适用于静态查找表。若要对动态查找表进行高效率 的查找，可采用下面介绍的几种特殊的二叉树或树作为 表的组织形式。不妨将它们统称为树表。下面将分别讨 论在这些树表上进行查找和修改操作的方法
(一)二叉排序树 、二叉排序树的定义 二叉排序树( Binary Sort Tree)又称二叉查找 (搜索)树( Binary Search Tree)。其定义为:二 叉排序树或者是空树,或者是满足如下性质的 二叉树: ①若它的左子树非空,则左子树上所有结点的 值均小于根结点的值; ②若它的右子树非空,则右子树上所有结点的 值均大于根结点的值; ③左、右子树本身又各是一棵二叉排序树。 上述性质简称二叉排序树性质BST性质) 故二叉排序树实际上是满足BST性质的二叉树
武汉理工大学华夏学院-信息工程 系 （一）二叉排序树 1、二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找 (搜索 )树(Binary Search Tree)。其定义为：二 叉排序树或者是空树，或者是满足如下性质的 二叉树： ①若它的左子树非空，则左子树上所有结点的 值均小于根结点的值； ②若它的右子树非空，则右子树上所有结点的 值均大于根结点的值； ③左、右子树本身又各是一棵二叉排序树。 上述性质简称二叉排序树性质(BST性质)， 故二叉排序树实际上是满足BST性质的二叉树