二插排序数的查找.ppt

第九章查找,本章主要内容：学习本章应注意,1、常用术语,2、静态查找表,3、动态查找表,4、哈希表,相关术语,1、基本术语（P214）查找表、静态查找表(静态环境)、动态查找表(动态环境)、查找、关键字、主关键字、次关键字、查找成功、查找失败2、关键字类型、数据元素类型说明（P215）3、两关键字的比较格式约定（P215）,学习本章内容时应注意以下几点：,查找表的存储结构查找算法的基本思想具体算法效率分析评价指标优、缺点：如何改进,查找算法的评价指标查找成功:最少比较次数最多比较次数平均比较次数查找失败:最少比较次数最多比较次数平均比较次数,9.1静态查找表,本节主要内容：,二、顺序表的查找,三、有序表的查找,四、索引顺序表的查找,一、抽象数据类型静态查找表P216,一、静态查找表的顺序存储结构p216二、顺序查找的基本思想：表中记录无序,intsearch_seq(SSTableST,KeyTypekey)ST.elem0.key=key;for(i=ST.length;!EQ(ST.elemi.key,key);-i);returni;,三、具体算法及上机实现P216算法9.1,9.1.1顺序表的查找-顺序查找,四、效率分析查找成功：最好情况：比较1次，T(n)=O(1)最坏情况：比较n次，T(n)=O(n)平均情况：比较(n+1)/2次，T(n)=O(n+1)/2)=O(n)讲查找失败：比较n+1次，T(n)=O(n+1)=O(n)五、优、缺点：上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表，若以有序表表示静态查找表，则查找过程可以基于“折半”进行。,顺序查找的平均查找长度(AverageSearchLength)为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值（平均值）：,其中:n为表长，Pi为查找表中第i个记录的概率，且，Ci为找到该记录时，和给定值比较过的关键字的个数，由上述算法可知：Ci=n-i+1，假设每个记录的查找概率相等，即Pi=1/n，从而：,=,=,=,ST.elem,顺序查找过程,假设给定值key=64,要求ST.elemi.key=key,问:i=?,从前往后查找:,可从前往后查找,也可从后往前查找,若按上述的从前往后查找,其算法如下:,intSearch_Seq(SSTableST，KeyTypekey)for(i=1;i=ST.length,按上述方式查找，每次比较前都必须进行范围检查，从而导致比较所耗费的时间太多，事实上可按下述方式，从后往前查找。,ST.elem,key=64,64,ST.elem,key=60,60,查找成功,查找失败,注意讲清ST.elem0.key=key的作用（哨兵），算法P216217算法9.1,有序顺序表的折半搜索的判定树(10,20,30,40,50,60),10,50,=,=,=,=,=,=,30,20,40,60,9.1.2有序表的查找-二分查找（折半查找）,一、基本思想p218二、具体算法及上机实现p220算法9.2三、效率分析p220四、优、缺点:折半查找的效率比顺序查找快得多，且算法简单、易于理解、易于实现，但是，查找表必须是关于关键字有序。,折半查找的基本思想,设n个对象存放在一个有序顺序表中，并按其关键字从“小”到“大”排序折半查找时,先求位于查找区间正中的对象的下标mid，用其关键字与给定值key比较1.ST.elemmid.key=key查找成功2.ST.elemmid.keykey把查找区间缩小到表的前半部分，继续折半查找3.ST.elemmid.key50时，可得近似结果:,从而，平均情况下有：T(n)=O(log2n),9.1.4索引顺序表的查找-分块查找,一、存储结构-索引存储结构p225二、索引查找基本思想p225及其效率分析P226,索引顺序查找的基本思想,1）由索引确定记录所在区间,2）在顺序表的某个区间内进行查找,注意：索引可以根据查找表的特点来构造,可见:索引顺序查找的过程也是一个“缩小区间”的查找过程,索引顺序查找的平均查找长度=查找“索引”的平均查找长度+查找“顺序表”的平均查找长度,9.2动态查找表,本节主要内容：,二、二叉排序树和平衡二叉排序树,三、B_树和B+树（自学）,一、动态查找表抽象数据类型定义P226,9.2.1二叉排序树和平衡二叉排序树,一、二叉排序树的定义及其存储结构,二、二叉排序树基本操作：,1、二叉排序树的定义,2、二叉排序树的存储结构-二叉链表树结构示,三、平衡二叉排序树P233学生自学,（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；,二叉排序树（BinarySortTree）或者是一棵空树；或者是具有下列性质的二叉树：,（3）它的左、右子树也都分别是二叉排序树。,（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；,二叉排序树的定义,例1：下列树中是二叉排序树的有？,是,否,二叉排序树的存储结构-二叉链表树结构,1、数据元素（记录）类型：typedefstructKeyTypekey；OtherTypeother；ElemType；,2、二叉排序树结点结构：,typedefstructBitNodeElemTypedata；structbitnode*lchild，rchild；BitNode，*BiTree；,数据元素类型,二叉链表树结点结构,关键字域,其它信息域,左孩子域,右孩子域,数据域,二叉排序树的直观示意图,T,T,二叉排序树的基本操作,1、插入操作：目的：在二叉排序树T上插入记录e基本思想：若T中有关键字值为e.key的记录，则不再插入，否则，按如下方式插入：（1）若e.key小于T的根的关键字值，则将e插入到左子树（2）否则，将e插入到T的右子树,算法,图示,例1：在如下所示的二叉排序T中插入关键字值为55，90的二个记录,T,分析：,55,55,55,55,二叉排序树插入算法,StatusInsertSBT(BiTree,2、建树操作：,目的：给定一组记录，将其建立成一棵二叉排序树基本思想：从一棵空树T开始，依次将记录插入到T中示具体算法：示,二叉排序树建立算法,voidCreateBSTree（BiTreescanf（record）；,二叉排序树的简单性质,1、二叉排序树的状态依赖于记录的输入顺序2、中序遍历二叉排序树，则各结点被访问的次序刚好是按关键字有序的序列。从而，可以利用建立二叉排序的方法对记录进行排序。,例2：试构造如下关键字值序列的二叉排序树,（1）45，12，53，39，66，85，5，1，29，75（2）45，53，66，85，75，12，1，5，29，39（3）53，45，1，5，39，29，85，66，75，12（4）1，5，12，29，39，45，53，66，85，75示以上各组记录的特点：只有顺序不同，即是说：如果不计顺序的话，上述四组记录是完全一样的，但是，以它们所构成的二叉排序树的状态是完全不一样的,45,T1,例3：设一组记录的关键字值如下，试构造其对应的二叉排序树。45，12，53，39，66，85，5，1，29，75,例4：中序遍历以下二叉排序树,T1：1、5、12、29、39、45、53、66、75、85、99,T2：3、15、19、21、31、49、52、56、57、69、73、76、81、82、86、94,3、二叉排序树查找,目的：在二叉排序T上查找关键字值为key的记录，若查找成功则返回相应结点的指针，否则，返回空指针NULL基本思想：若T为空，则查找失败，返回空指针NULL；否则按如下方式查找（1）将key与T的根结点的关键字值进行比较，若相等则查找成功，返回根结点指针；（2）否则，若key小于T的根结点的关键字值，则在左子树上查找；（3）否则，若key大于T的根结点的关键字值，则在右子树上查找；示,具体算法：P228算法9.5(a)效率分析：P231,在查找过程中，生成了一条查找路径：从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点（查找成功）；或者，从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止（查找失败）。从而，有：,查找成功：最好情况下：比较1次，T(n)=O(1)最坏情况下：比较h次，其中h为二叉排序树的深度，T(n)=O(h),平均情况下：含n个结点的二叉排序树的平均查找长度和树的形态有关。对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL值，显然，由值相同的n个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大，如：,由关键字序列1，2，3，4，5构造而得的二叉排序树,2,1,3,4,5,ASL=（1+2+3+4+5）/5=3,如果输入序列选得不好，会建立起一棵单支树，使得二叉排序树的高度达到最大，此时平均查找长度为(n+1)/2，这是最坏情况。,由关键字序列3，1，2，5，4构造而得的二叉排序树,3,5,4,1,2,ASL=（1+2+3+2+3）/5=2.2,最好情况是二叉排序树的形态和折半查找树相同，即为完全二叉树，此时，平均查找长度为O(log2n)。在随机情况下，由值相同的n个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度为O(log2n),例5：在如下所示的二叉排序T中查找关键字值key=76的记录，若查找成功，则返回相应结点的指针，否则返回NULL,76,76,76,76,76,查找成功,4、删除操作：,目的：删除二叉排序树上关键字值为key的记录,基本思想：P229（分三种情况进行讨论）示,具体算法：P230,二叉排序树T中被删除结点的三种情况：,平衡二叉树（又称为AVL树）：或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。,非平衡二叉树,平衡二叉排序树,平衡二叉树,结点的平衡因子(Balancefactor),给二叉树每个结点附加一个数字,给出该结点左子树的深度减去右子树的深度所得的深度差,这个数字即为结点的平衡因子。则AVL树上任一结点的平衡因子只可能是-1,0,1。,如果一个结点的平衡因子的绝对值大于1,则这棵二叉排序树就失去了平衡,不再是AVL树如果一棵二叉排序树是平衡的,且有n个结点，其高度可保持在O(log2n),平均排序长度也可保持在O(log2n),5,4,8,2,5,4,8,2,1,是平衡树,不是平衡树,平衡化旋转,如果在一棵平衡的二叉排序树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化平衡化旋转有两类：单旋转(左旋和右旋)双旋转(左旋加右旋和右旋加左旋),每插入一个新结点时,AVL树中相关结点的平衡状态会发生改变。因此,在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子,如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点,如果这三个结点处于一条直线上，则采用单旋转进行平衡化单旋转可按其方向分为左单旋转和右单旋转,其中一个是另一个的镜像,其方向与不平衡的形状相关如果这三个结点处于一条折线上，则采用双旋转进行平衡化双旋转分为先左后右和先右后左两类,右单旋转LL型,左单旋转RR型,左右双旋转LR型,右左双旋转RL型,左单旋转(RotateLeft,RR型),在子树E中插入新结点，该子树深度增1导致结点A的平衡因子变成+2，产生不平衡(RR型)以结点C为旋转轴，将结点A反时针旋转,右单旋转(RotateRight,LL型),在子树D中插入新结点,该子树深度增1导致结点A的平衡因子变成-2，产生不平衡(LL型)以结点B为旋转轴，将结点A顺时针旋转,先左后右双旋转(RotationLeftRight,LR型),在子树F或G中插入新结点，该子树深度增1导致结点A的平衡因子变成-2，产生不平衡(LR型)首先以结点E为旋转轴，将结点B反时针旋转，以E代替原来B的位置，做左单旋转再以结点E为旋转轴，将结点A顺时针旋转，做右单旋转,插入,0,0,-1,-2,+1,-1,h,h,A,C,E,D,0,h-1,h-1,h,h,A,h-1,h,B,C,E,D,B,左单旋转,F,G,F,G,0,0,-2,0,0,+1,h,h,A,C,E,D,-2,h-1,h,h,h,A,h-1,h,B,C,E,D,B,右单旋转,F,G,F,G,先右后左双旋转(RotationRightLeft,RL型),在子树F或G中插入新结点，该子树深度增1导致结点A的平衡因子变成2，产生不平衡(RL型)首先以结点D为旋转轴，将结点C顺时针旋转，以D代替原来C的位置,做右单旋转再以结点D为旋转轴，将结点A反时针旋转，做左单旋转,插入,右单旋转,+1,0,0,0,-1,+1,0,h,h,A,C,E,D,h-1,B,F,G,h-1,+2,0,0,0,h,h,A,C,E,h,B,F,G,h-1,D,0,0,+2,0,-1,0,h,h,A,C,E,+2,h-1,h,h,h,A,h-1,h,B,C,E,D,B,左单旋转,F,G,F,G,D,构造二叉平衡（查找）树的方法在插入过程中，采用平衡旋转技术,依次插入的关键字为5,4,2,8,6,9,5,4,2,4,2,5,8,6,6,5,8,4,2,向右旋转一次,先向右旋转再向左旋转,4,2,6,5,8,9,6,4,2,8,9,5,向左旋转一次,继续插入关键字9,输入关键码序列为16,3,7,11,9,26,18,14,15插入和调整过程如下,1,2,2,右左双旋,左单旋,15,18,2,3,18,16,-2,左右双旋,7,3,0,0,0,11,7,14,9,-1,16,15,0,1,11,26,26,14,1,-2,9,从空树开始的建树过程,B-树和B+树,B_树一、B_树的定义P238二、B_树基本操作P239B+树一、B+树的定义P246二、B+树的基本操作P246,B-树是一种平衡的多路查找树,一、B_树的定义P238,由B-树的定义可知:,在m阶的B-树上，每个非终端结点可能含有：n个关键字Ki（1in）nmn个指向记录的指针Di（1in）n+1个指向子树的指针Ai（0in）,多叉树的特性,非叶结点中的多个关键字均自小至大有序排列，即：K1K2KnAi-1所指子树上所有关键字均小于KiAi所指子树上所有关键字均大于Ki,查找树的特性,平衡树的特性,树中所有叶子结点均不带信息，且在树中的同一层次上根结点或为叶子结点，或至少含有两棵子树其余所有非叶结点均至少含有m/2棵子树，至多含有m棵子树,从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找两个过程交叉进行,查找过程,若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置,若查找不成功，则返回插入位置,在查找不成功之后，需进行插入显然，关键字插入的位置必定在最下层的非叶结点，有下列几种情况,插入,插入后，该结点的关键字个数nm，不修改指针,插入后，该结点的关键字个数n=m，则需进行“结点分裂”，令s=m/2，在原结点中保留（A0，K1，Ks-1，As-1）；建新结点（As，Ks+1，Kn，An）；将（Ks，p）插入双亲结点,若双亲为空，则建新的根结点,下列为3阶B-树,50,2040,80,插入关键字=60,6080,90,608090,90,5080,60,30,40,20,305080,30,50,80,和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于m/2-1，否则，要从其左(或右)兄弟结点“借调”关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字)，则必须进行结点的“合并”,删除,在含N个关键字的B-树上进行一次查找，需访问的结点个数不超过logm/2(N+1)/2)+1,查找性能,由定义可知，是B-树的一种变型,B+树,一、B+树的定义P246,每个叶子结点中含有n个关键字和n个指向记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点,每个非叶结点中的关键字Ki即为其相应指针Ai所指子树中关键字的最大值,所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于m/2和m之间,查找过程,在B+树上，既可以进行缩小范围的查找，也可以进行顺序查找,在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束,若在结点内查找时，给定值Ki，则应继续在Ai所指子树中进行查找,插入和删除,类似于B-树进行，即必要时，也需要进行结点的“分裂”或“归并1”,5096,1550,627896,7178,848996,5662,20264350,3815,sq,root,9.3哈希表,9.3.2哈希函数的构造方法,9.3.3处理冲突的方法,9.3.4哈希表的查找及其效率分析,本节主要内容,9.3.1哈希表的定义P251,前面讨论的表示查找表的各种结构（静态查找表：顺序表、线性链表，动态查找表：二叉排序树、平衡二叉排序树、B树等）的共同特点：记录在结构（表）中的相对位置是随机的，和记录的关键字之间不存在一个确定的关系。查找的过程为给定值依次和关键字集合中各个关键字进行比较（查找方法建立在“比较”的基础上），查找的效率取决于和给定值进行比较的比较次数，用这类方法表示的查找表，其平均查找长度都不为零，不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。,对于频繁使用的查找表，希望ASL=0。只有一个办法：预先知道所查关键字在表中的位置。这就要求：记录在表中的存储位置和其关键字之间存在一种确定的对应关系f，使每个关键字和结构中的唯一的存储位置相对应。在查找时，只要根据这个对应关系f找到给定值k的像f(k)（称为哈希地址）。若结构中存在关键字和k相等的记录，则必在f(k)的存储位置上，由此，不需要进行比较便可直接取得所查记录。我们称这个对应关系f为哈希函数，按这个思想建立的表为哈希表。以例示之,简单结论:P252（1）哈希函数是一个映象（映射），即：将关键字的集合映射到某个地址集合上，因此，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可（即，只要使得任何关键字由此所得的哈希函数值都落在表长允许范围之内即可）；（2）对于不同的关键字可能得到同一哈希地址，即：key1key2，而f(key1)=f(key2)，这种现象称为“冲突”，key1、key2称为同义词。,（3）很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少。因此，在构造这种特殊的“查找表”时，除了需要选择一个好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”的方法。综上所述可对哈希表做一个比较准确的描述,根据设定的哈希函数H(key)和所选处理冲突的方法，将一组关键字映象到一个有限的、连续的地址集(区间)上，并以关键字在地址集中的“像”作为相应记录在表中的存储位置，如此构造所得的查找表称为“哈希表”，这一映象过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。,对数字的关键字可有下列构造方法,若是非数字关键字，则需先对其进行数字化处理,直接定址法,平方取中法,除留余数法,折叠法,随机数法,数字分析法,9.3.2哈希函数的构造方法,对同一实际问题构造哈希表的方法很多，从而可以构造出很多的哈希函数，什么是好的哈希函数?P253均匀分布,数字分析法,此方法适合于：能预先估计出全体关键字的每一位上各种数字出现的频度,假设关键字是以r为基数的数，并且事先知道所有可能出现的关键字，每个关键字都是由s位数字组成(u1,u2,us)，则可取关键字的若干位数组成哈希地址。讲解P254的例,平方取中法,取关键字平方后的中间几位为哈希地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。,此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象,折叠法,将关键字分割成位数相同的若干部分（最后一部分的位数可能不同），然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加（舍去进位）,此方法适合于:关键字的数字位数特别多,直接定址法,取关键字或关键字的某个线性函数值为哈希地址。即：H(key)=key或者H(key)=akey+b其中a和b为常数。,直接定址法的优点：无冲突此法适合于以下情形：地址集合的大小=关键字集合的大小,除留余数法,取关键字被某个不大于哈希表表长m的数p除后所得的余数为哈希地址。即，设定哈希函数为:H(key)=keyMODp其中，pm(表长)一般要求：讲清为什么p为不大于m的素数（避免同义词）或是不含20以下的质因子（减少同义词）,随机数法,选择一个随机函数，取关键字的随机函数值为它的哈希地址，即，设定哈希函数为:H(key)=Random(key)其中，Random为伪随机函数,通常，此方法用于对长度不等的关键字构造哈希函数,实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。,通常，考虑的因素有：P256（1）计算哈希函数所需时间；（2）关键字的长度；（3）哈希表的大小；（4）关键字的分布情况；（5）记录的查找频率；,“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。常见的方法有：,1.开放定址法,3.链地址法,9.3.3处理冲突的方法,2.再哈希法,4.建立一个公共溢出区P258,为产生冲突的地址H(key)求得一个可能的存储地址，具体方式如下：Hi=(H(key)+di)MODmi=1,2,k便得到一地址序列：H0,H1,H2,Hk1km-1，其中：H0=H(key),1.开放定址法(闭域法),其中：H(key)为哈希函数，m为表长，di称为增量序列。,1）di=1,2,3,m-1，称为线性探测再散列示本质：若冲突则考查下一位置。但容易产生再“二次聚集”。2）di=12,-12,22,-22,32,-32,称为二次探测再散列示3）di=伪随机数列，称为随机探测再散列,一般情况下,增量di有三种取法:,19,01,23,14,55,68,11,82,36,H(key)=keyMOD11,19,01,23,14,55,68,19,01,23,14,68,若采用线性探测再散列处理冲突,若采用二次探测再散列处理冲突,11,82,36,55,11,82,36,112136251,Hi=(H(key)+di)MODm,di=12,-12,22,-22,32,-32,即：产生的Hi均不相同，且所产生的(m-1)个Hi值能覆盖哈希表中所有地址。且要求：,增量di应具有“完备性”P257,随机探测散列取决于伪随机数列,二次探测时的表长m必为形如4j+3的素数（如:7,11,19,23,等）,2.再哈希法P258,Hi=RHi(key)i=1,2,3,k,RHi均是不同的哈希函数,即在同义词产生地址冲突时用另一个哈希函数计算另一个哈希地址，直到冲突不再发生。这种方法不易产生“聚集”，但增加了计算时间,将所有哈希地址相同的记录都链接在同一链表中。假设某哈希函数产生的哈希地址在区间0，m-1上，则可设立一指针型向量（一维数组）ChainHashm，其中ChainHashi用于记录哈希地址为i的同义词所构成的单向线性链表的首结点的指针,为便于查找，在建表时可保持每个单链表按关键字有序。示,3.链地址法(开域法),思考题:已知一组关键字为19,14,23,01,68,20,84,27,55,11,10,79，试构造按哈希函数H(key)=keyM