《《9第九章查找》-精选课件（公开PPT）》由会员分享，可在线阅读，更多相关《《9第九章查找》-精选课件（公开PPT）（61页珍藏版）》请在金锄头文库上搜索。
1、1、静态查找表 2、动态查找表 3、哈希查找表,第9章 查找,术语： 查找(检索) 根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素 关键字 是记录某个数据项的值，它可以唯一标识 一个记录。 次关键字 不能唯一的确定一个记录，但能确定表的一个子表。子表的元素个数应远少于表中元素数。 为简化问题，将表中元素看成简单的整型数据，理解为关键字部分。,8.1 静态查找表,1、顺序表的顺序查找,应用范围：顺序表或线性链表表示的表，表内元素之间无序。 查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。,search(st,key，n) /在有n个数据的表st中找key i=n-1
2、; while(i=0 /查找成功返回下标号 ,算法主要时间在循环，为减少判定，n个数据用容量为n+1的一维数组表示。st1到stn存储数据，st0作为监视哨,search1(st,key，n) st0=key; i=n; while(sti!=key) i- -; return i; /查找返回序号，0为不成功 ,顺序查找的平均时间为表长的一半。,2、顺序有序表的查找 二分（折半）查找,查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定的待查值 初始时，令low=1,
3、high=n,mid=(low+high)/2 让k与mid指向的记录比较： 若k=rmid，查找成功，结束 若krmid，则low=mid+1 重复上述操作，直至lowhigh时，查找失败,bin_search(st,key,n) low=0; hight=n-1; mid=(low+high)/2; while(lowkey) high=mid-1; else low=mid+1; return -1; ,递归： bin_search(st,key,l,h) if(l1; if( stmid = = key) return mid; else if(stmidkey) return bin
4、_search(st,key,l,h-1); else eturn bin_search(st,key,l+1,h) else return -1; ,3、分块查找,数据组织： 将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找 （1）用数组存放待查记录, （2）建立索引表，由每块中最大（小）的关键字及所属块位置的信息组成。,当索引表较大时，可以采用二分查找 在数据量极大时，索引可能很多，可考虑建立索引表的索引，即二级索引，原则上索引不超过三级,小结： 时间：顺序查找最差，二分最好，分块介于两者之间 空间：分块最大，需要增加索引数据的空间 特点： 1）顺序查找对表没有特殊要求
5、 2）分块时数据块之间在物理上可不连续。所以可以达到插入、删除数据只涉及对应的块；另外，增加了索引的维护。 3）二分查找要求表有序，所以若表的元素的插入与删除很频繁，维持表有序的工作量极大。 4）在表不大时，一般直接使用顺序查找。,9.2 动态查找表,动态查找表 如果应用问题涉及的数据量很大，而且数据经常发生变化，如图书馆经常购进图书，每购进新书，需将新书记录插入图书表，对这类表除了提供1）、2）两种查找外，还要提供动态查找功能： 3） 查找某个“特定”元素是否在表中，若不在，则将该元素插入表中； 4） 查找某个“特定”元素是否在表中，若在，从表中删除该元素； 如何组织动态查找表？ 线性表：顺
6、序查找效率低 有序表：二分查找法须用顺序结构存储有序表，插入删除操作要移动元素； 本节介绍动态查找表的一种组织形式二叉排序树,9.2.1 二叉排序树和平衡二叉树 1.二叉排序树 二叉排序树（ Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树分别为二叉排序树；,二叉排序树,2 二叉排序树的查找 在二叉排序树中查找关键字为key的记录 基本思想 若二叉排序树为空树，查找失败，返回null或 0； 否则，将key与根结点的
7、关键字比较： 若key = 根结点的关键字,查找成功，返回该记录在二叉排序树 中的位置； 若key 根结点的关键字，继续在左子树中查找； 若key 根结点的关键字，继续在右子树中查找；,例 在如下二叉排序树中查找关键字为24的记录,2445 继续在左子树中查找,2412 继续在右子树中查找,2437 继续在左子树中查找,Key=24 查找成功！,例 在如下二叉排序树中查找关键字为60的记录,查找失败！,查找路径,左子树为空,算法 BiTree SearchBST(BiTree T, KeyType key) /二叉排序树用二叉链表存储。在根指针T所指二叉排序树中递归地查找/关键字等于key的记
8、录，若查找成功，则返回该记录结点的指针，否则 /返回空指针 if(!T)| EQ(key, T-data. key) return(T); / 若T为空或查找成功，返回 else if LT(key, T-data. key) return(SearchBST(T-1child, key); /在左子树中继续查找 return(SearchBST(T-rchild, key) /在右子树中继续查找 /SearchBST,性能分析：二叉排序树的查找效率与树的形态有关，若树的形态为“单枝”，二叉排序树的查找就“退化”为顺序查找；若树的形态比较“平衡”，二叉排序树的查找与二分查找类似；,为获得较高的
9、查找效率，需要构造“平衡”的二叉排序树。关于如何构造平衡二叉树，后面介绍。,3 二叉排序树的插入、删除 二叉排序树是动态查找表的组织形式,动态查找表要提供插入删除数据元素的操作。 在一般二叉树的基本操作中只有插入、删除子树操作，没有插入、删除结点操作。原因是；除了叶子结点外，在二叉树中插入、删除结点将破坏树的结构。 下面介绍如何在二叉排序树的插入、删除。二叉排序树是作为动态查找表的组织形式，目的是获得较高的查找效率并且能方便地进行插入删除操作。因此在二叉排序树中插入、删除结点的原则是：插入、删除结点后仍是二叉排序树。,1）二叉排序树的插入 新插入的结点为叶子结点，并且是查找不成功时，查找路径上
10、最后一个结点的左孩子或右孩子。 将新结点插入二叉排序树基本步骤： 从二叉排序树的根结点开始， 若二叉排序树为空树，新插入结点作为根结点， 否则，若当前结点为叶子结点， 若新插入结点的关键字当前结点的关键字，则将新结点 作为当前结点的左孩子，否则作为右孩子； 否则，若新插入结点的关键字 根结点的关键字，将新结点 插入左子树；否则插入右子树,例 在如下二叉排序树中插入结点 40,为查找插入位置走过的路径,插入结点40！,2）二叉排序树的删除 在二叉排序树中删除结点的原则是：删除结点后仍是二叉排序树。 对二叉排序树进行中序遍历，所得到的中序序列是一有序序列。 如对如图所示的二叉排序树进行中序遍历，其
11、中序序列为：3，12，24，37，45，53，61，78，90，100， 在二叉排序树中删除一个结点相当于在有序序列删除一个结点，只要删除结点后仍保持二叉排序树的特性。,如何在二叉排序树中 删除一个结点?,？,在二叉排序树中删除一个结点，问题可以归结为在一棵子树中删除根结点，根结点删除后，二叉排序树变成两棵子树。最后的问题是将两棵二叉排序树合成一棵新的二叉排序树。下面分三种情况讨论： (1) p仅有一个结点（被删除的结点是叶子），新树t=null (2) p仅有一棵子树。T=p-lchild 或 t=p-rchild (3) p有两棵子树，情况比较复杂， 有两种方法解决，我们分别讨论。,P既有
12、左子树PL 也有右子树PR , 如图，二叉排序树的中序序列为(FCLC QL Q SL S P PR ) S是P的直接前趋，S是P的左子树的最右下结点，S至少没有右子树。在删除P后,为保持中序序列中其它元素之间的相对位置不变，可有两种作法 (a)令P的左子树的根C作为新树的根，而P的右子树为S的右子树； （b)用P的直接前趋S代替P，然后从二叉排序树删除P的直接前趋S；,(a),(b),删除P前的二叉排序树,t=p-lchild;s=t; while (s-rchild) s=s-rchild s-rchild=p-rchild 同理，可将p的右子树的根作为新树的根，将PL 插入p的右子树 的
13、适当位置。这种方法，删除后树的深度增加了。会降低查 找效率。 (b) 找到PL 的右支末端结点s将p-data=s-data。然后删除s, s可能无左右子树，也可能有一个 左子树。S删除后，它的左 子树应连在s的双亲右子树上。但是，若PL 无右子树，可将PL 的左子树连在p的左子树上。,t=p; q=p; s=p-lchild; while (s-rchild) q=s; s=s-rchild p-data=s-data; if (q!=p) q-rchild=s-lchild else q-lchild=s-lchild 该方法，算法复杂一些，但树的深度没有增加。完整的算法参见讲义p230算
14、法9.7 和算法9.8,二叉排序树的查找效率与树的形态有关，而树的形态取决于建立二叉排序树时的输入序列。 例：8，12，3，10，18，2，7,ASL=(n+1)/nlog2(n+1)-1,8,18,7,10,2,12,3,2,3,7,8,10,12,18,ASL=(n+1)/2,由此，二叉排序树的查找效率相差比较大，平均性能ASL=1+4log2n,平衡二叉树,1.定义：平衡二叉树(Balanced Binary Tree或Hight-Balancde Tree)，是由阿德尔森一维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。
15、若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。 2.平衡因子：将该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子(balance factor)。 这就是说，一棵二叉排序树中，所有结点的平衡因子只能为0、1、-1时，则该二叉排序树就是一棵平衡二叉树，否则就不是一棵平衡二叉树。如下图 (a)所示二叉排序树，是一棵平衡二叉树，而下图(b) 所示二叉 排序树，就不是一棵平衡二叉树。,图(a),图(b),二叉排序树的查找效率与树的形态有关，而树的形态取决于建立二叉排序树时的输入序列。如果对任何的输入序列建成的二叉排序树都是AVL树。 要用建立二叉排序树的方法，建立平衡二叉树，在树不平衡时做适当的调整。 3.修改二叉排序树的插入算法 *判定树的不平衡性，每个结点增加一个表示平衡因子的数据项bf。 *平衡操作，确定平衡处理的范围并进行平衡处理。,平衡处理的范围：最小的一个不平衡子树。 4.平衡操作 (1) RR旋转（单向左旋平衡处理）：设a指向最小不平衡子树的根。 在a的右子树的右子树插入新结点，造成a子树的不平衡。a的bf由-1变为-2。 设a的左子树AL高为h-1,b子树高为h,b的左子树BL和b的右子树BR
