7-第七章.ppt
第九章 查找n查找也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素n关键字是数据元素中某个数据项的值，它可以标识一个数据元素n查找方法评价o查找速度o占用存储空间多少o算法本身复杂程度o平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的o9.1 顺序查找n查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较n算法描述Ch7_1.ci例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2.查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1n顺序查找方法的ASLo9.2 折半查找n查找过程：每次将待查记录所在区间缩小一半n适用条件：采用顺序存储结构的有序表n算法实现o设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值o初始时，令low=1,high=n,mid=(low+high)/2o让k与mid指向的记录比较n若k=rmid.key，查找成功n若krmid.key，则low=mid+1o重复上述操作，直至lowhigh时，查找失败n算法描述lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmidCh7_2.c例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1185210741936判定树：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92n算法评价o判定树：描述查找过程的二叉树叫o有n个结点的判定树的深度为log2n+1o折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度o折半查找的ASLo9.3 分块查找n查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找n适用条件：分块有序表n算法实现o用数组存放待查记录,每个数据元素至少含有关键字域o建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针n算法描述Ch7_3.c1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38查找过程：（1）先确定待查记录所在的块（子表）（2）然后在块中顺序查找n分块查找方法评价ASL最大最小两者之间表结构有序表、无序表 有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构 顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找9.4 二叉排序树o定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：n若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值n若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值n它的左、右子树也分别为二叉排序树o二叉排序树的插入n插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子n二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树n插入算法例 10，18，3，8，12，2，7，310101810183101838101838 12101838 122101838 1227101838 12273中序遍历二叉排序树可得到一个关键字的有序序列相等的时候走右边!Ch5_9.co二叉排序树的删除要删除二叉排序树中的p结点，分三种情况：np为叶子结点np只有左子树或右子树np左、右子树均非空SQPLP中序遍历：Q S PL PSQPL中序遍历：Q S PL(2)SPPLQ中序遍历：PL P S QSPLQ中序遍历：PL S Q(1)中序遍历：P PR S QSPRQ中序遍历：PR S Q(3)SPPRQ中序遍历：Q S P PRSQPR中序遍历：Q S PR(4)SQPRPFPCPRCLQQLSSL中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：CL C QL Q SL S PR F(5)FPCPRCL中序遍历：CL C P PR FFCPRCL中序遍历：CL C PR F(6)n删除算法例805012060110150557053删除508060120110150557053删除60805512011015053701042581354删除1084255134删除58425413Ch5_10.c二叉排序树查找的性能分析二叉排序树查找的性能分析 在二叉排序树查找中，成功的查找次数不会超过二叉树的深度，而具有n个结点的二叉排序树的深度，最好为log2n，最坏为n。因此，二叉排序树查找的最好时间复杂度为O(log2n)，最坏的时间复杂度为O(n)，一般情形下，其时间复杂度大致可看成O(log2n)，比顺序查找效率要好，但比二分查找要差。平衡二叉树平衡二叉树1平衡二叉树的概念平衡二叉树的概念 平衡二叉树(balanced binary tree)是由阿德尔森一维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。将该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子(balance factor)。也就是说，一棵二叉排序树中，所有结点的平衡因子只能为0、1、-1时，则该二叉排序树就是一棵平衡二叉树，否则就不是一棵平衡二叉树。2.非平衡二叉树的平衡处理 若一棵二叉排序树是平衡二叉树，插入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平衡因子又比1大或比-1小的结点。下面将分四种情况讨论平衡处理。（1）LL型型 的处理的处理(左左型左左型)如图8-10所示，在A的左孩子B上插入一个左孩子结点C，使A的平衡因子由1变成了2，成为不平衡的二叉树序树。这时的平衡处理为：将A顺时针旋转，成为B的右子树，而原来B的右子树则变成A的左子树，待插入结点C作为B的左子树。(注：图中结点旁边的数字表示该 结点的平衡因子)（2）LR型的处理型的处理(左右型左右型)如图8-11所示，在A的左孩子B上插入一个右孩子C，使的A的平衡因子由1变成了2，成为不平衡的二叉排序树。这是的平衡处理为：将C变到B与A 之间，使之成为LL型，然后按第(1)种情形LL型处理。（3）RR型的处理型的处理(右右型右右型)如图8-12所示，在A的右孩子B上插入一个右孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将A逆时针旋转，成为B的左子树，而原来B的左子树则变成A的右子树，待插入结点C成为B的右子树。（4）RL型的处理型的处理(右左型右左型)如 图8-13所示，在A的右孩子B上插入一个左孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将C变到A与B之间，使之成为RR型，然后按第(3)种情形RR型处理。例8-2，给定一个关键字序列4,5,7,2,1,3,6，试生成一棵平衡二叉树。分析：平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。具体生成过程见图8-14。3平衡二叉树的查找及性能分析 平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找 性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树的最好时间复杂相同，都为O(log2n)。例8-3，对例8-2给定的关键字序列4,5,7,2,1,3,6，试用二叉排序树和平衡二叉树两种方法查找，给出查找6的次数及成功的平均查找长度。分析：由于关键字序列的顺序己经确定，故得到的二叉排序树和平衡二叉树都是唯一的。得到的平衡二叉树见图8-14，得到的二叉排序树见图8-15。从图8-15的二叉排序树可知，查找6需4次，平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/72.57。从图8-14的平衡二叉树可知，查找6需2次，平均查找长度ASL=(1+2+2+3+3+3+3)=17/72.43。从结果可知，平衡二叉树的查找性能优于二叉排序树。o9.5 哈希查找n基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法n定义o哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫n哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象n哈希函数可写成：addr(ai)=H(ki)ai是表中的一个元素addr(ai)是ai的存储地址ki是ai的关键字关键字集合存储地址集合hasho哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫o哈希查找又叫散列查找，利用哈希函数进行查找的过程叫例 30个地区的各民族人口统计表编号 地区别 总人口 汉族 回族.1 北京2 上海.以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19从例子可见：n哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可n冲突：key1key2，但H(key1)=H(key2)的现象叫n同义词：具有相同函数值的两个关键字，叫该哈希函数的n哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法n哈希函数的构造方法o直接定址法n构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=akey+bn特点直接定址法所得地址集合与关键字集合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少o数字分析法n构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址n适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5.分析：只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机所以：取任意两位或两位 与另两位的叠加作哈希地址o平方取中法n构造：取关键字平方后中间几位作哈希地址n适于不知道全部关键字情况o折叠法n构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址n种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加n适于关键字位数很多，且每一位上数字分布大致均匀情况例 关键字为：0442205864，哈希地址位数为45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加o除留余数法n构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，pmn特点简单、常用，可与上述几种方法结合使用p的选取很重要；p选的不好，容易产生同义词,选p为小于或等于哈希表表长m的某个最大质数为好o随机数法n构造：取关键字的随机函数值作哈希地址，即H(key)=random(key)n适于关键字长度不等的情况o选取哈希函数，考虑以下因素：n计算哈希函数所需时间n关键字长度n哈希表长度（哈希地址范围）n关键字分布情况n记录的查找频率n处理冲突的方法o开放定址法n方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MOD m，i=1,2,k(km-1)其中：H(key)哈希函数 m哈希表表长 di增量序列n分类线性探测再散列：di=1,2,3,m-1二次探测再散列：di=1,-1,2,-2,3,k(km/2)伪随机探测再散列：di=伪随机数序列例 表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=key MOD 11,现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中0 1 2 3 4 5 6 7 8 9 1060 17 29(1)H(38)=38 MOD 11=5 冲突 H1=(5+1)MOD 11=6 冲突 H2=(5+2)MOD 11=7 冲突 H3=(5+3)MOD 11=8 不冲突 38(2)H(38)=38 MOD 11=5 冲突 H1=(5+1)MOD 11=6 冲突 H2=(5-1)MOD 11=4 不冲突38(3)H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，则：H1=(5+9)MOD 11=3 不冲突38o再哈希法n方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key)i=1,2,k其中：Rhi不同的哈希函数n特点：计算时间增加o链地址法n方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=key MOD 13,用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011n哈希查找过程及分析o哈希查找过程给定k值计算H(k)此地址为空关键字=k查找失败查找成功按处理冲突方法计算HiYNYNo哈希查找分析n哈希查找过程仍是一个给定值与关键字进行比较的过程n评价哈希查找效率仍要用ASLn哈希查找过程与给定值进行比较的关键字的个数取决于：哈希函数处理冲突的方法哈希表的填满因子=表中填入的记录数/哈希表长度例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=key MOD 13,哈希表长为m=16，设每个记录的查找概率相等(1)用线性探测再散列处理冲突，即Hi=(H(key)+di)MOD mH(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5H(79)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(1+4)MOD16=5 冲突，H5=(1+5)MOD16=6 冲突，H6=(1+6)MOD16=7 冲突，H7=(1+7)MOD16=8 冲突，H8=(1+8)MOD16=90 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ASL=(1*6+2+3*3+4+9)/12=2.514 1 68 27 55 19 20 84 79 23 11 10H(19)=6H(14)=1H(23)=10H(1)=1 冲突，H1=(1+1)MOD16=2H(68)=3H(20)=7H(84)=6 冲突，H1=(6+1)MOD16=7 冲突，H2=(6+2)MOD16=8H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4H(11)=11H(10)=10 冲突，H1=(10+1)MOD16=11 冲突，H2=(10+2)MOD16=12(2)用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011ASL=(1*6+2*4+3+4)/12=1.75关键字(19,14,23,1,68,20,84,27,55,11,10,79)n哈希查找算法实现o用线性探测再散列法处理冲突n实现查找过程：同前删除：只能作标记，不能真正删除插入：遇到空位置或有删除标记的位置就可以插入n算法描述：o用外链表处理冲突算法Ch7_4.cCh7_5.c
