查找PPT课件.ppt

查找查找v基本概念基本概念查找表：由同一类型的数据元素（或记录）构成的集合。静态查找表：只进行查询某个数据元素是否在查找表中，或检索某个数据元素的各种属性的查找表。动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或从查找表中删除已存在的某个数据元素。关键字(key)：是数据元素(或记录)中某个数据项的值，用它可以标识(或识别)一个数据元素。主关键字：能唯一标识一个数据元素的关键字。次关键字：用以识别若干记录的关键字。查找：就是根据给定的值，在一个表中查找出其关键字等于给定值的数据元素。若表中有这样的元素，则称查找成功，此时查找的信息为给定整个数据元素的输出或指出该元素在表中的位置；若表中不存在这样的记录，则称查找不成功，或称查找失败查找方法评价v查找速度v占用存储空间多少v算法本身复杂程度v平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的9.1 静态查找表9.1.1 顺序表的查找顺序表的查找顺序查找的基本思想顺序查找的基本思想 顺序查找是一种最简单的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于的元素，则查找失败。顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。i例 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+1算法描述类型定义与算法实现类型定义与算法实现 typedef struct keytype key;/*关键字类型关键字类型*/elemtype other;/*其他的域其他的域*/sqlist;sqlist Rn+1;/*顺序表顺序表*/顺序检索算法：顺序检索算法：int seqsrch(sqlist R ，keytype k)int i;R0.key=k;/*将将R0作为监视哨作为监视哨*/i=n;/*从第从第n个记录起向前扫描个记录起向前扫描*/while(Ri.key!=k)i-;if(i=0)return(0);else return i;/*seqsrch*/顺序查找方法的ASLn n顺序查找的缺点：顺序查找的缺点：n n平均查找长度较大，特别是当待查找集合中元素较多时，查平均查找长度较大，特别是当待查找集合中元素较多时，查平均查找长度较大，特别是当待查找集合中元素较多时，查平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。找效率较低。找效率较低。找效率较低。n n顺序查找的优点：顺序查找的优点：n n算法简单而且使用面广。算法简单而且使用面广。算法简单而且使用面广。算法简单而且使用面广。n n对表中记录的存储没有任何要求，顺序存储和链接存储均可；对表中记录的存储没有任何要求，顺序存储和链接存储均可；对表中记录的存储没有任何要求，顺序存储和链接存储均可；对表中记录的存储没有任何要求，顺序存储和链接存储均可；n n对表中记录的有序性也没有要求，无论记录是否按关键码有对表中记录的有序性也没有要求，无论记录是否按关键码有对表中记录的有序性也没有要求，无论记录是否按关键码有对表中记录的有序性也没有要求，无论记录是否按关键码有序均可。序均可。序均可。序均可。9.1.2 有序表的查找有序表的查找折半查找折半查找折半查找的基本思想折半查找的基本思想 折半查找，是一种高效率的查找方法。但要求表中元素必须按关键字有序(升序或降序)。不妨假设表中元素为升序排列。折半查找的基本思想是：首先将待查值K与有序表array1到arrayn的中点mid上的关键字arraymid.key进行比较，若相等，则查找成功；否则，若arraymid.keyk ，则在array1到arraymid-1中继续查找，若有arraymid.key1418147221822low=4mid=4 21high算法实现v设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值v初始时，令low=1,high=n,mid=(low+high)/2v让k与mid指向的记录比较l若k=rmid.key，查找成功l若krmid.key，则low=mid+1v重复上述操作，直至lowhigh时，查找失败算法描述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 92lowhighmid例 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 92lowhigh折半查找算法折半查找算法int bin_search(NODE array,int n,int k)int low=1,high=n,mid;while(lowk)high=mid-1;/在在左左子子区区间间中中查查找找 else low=mid+1;/在右子区间中查找在右子区间中查找 return(0);/查找失败查找失败折半查找的性能分析折半查找的性能分析 为了分析折半查找的性能，可以用二叉树来描述折半查找过程。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为折半查找的判定树。1185210741936判定树：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92例：n n判定树的构造方法判定树的构造方法n n 当当当当n n=0=0时，折半查找判定树为空；时，折半查找判定树为空；时，折半查找判定树为空；时，折半查找判定树为空；n n 当当当当n n0 0时，折半查找判定树的根结点是时，折半查找判定树的根结点是时，折半查找判定树的根结点是时，折半查找判定树的根结点是有序表中序号为有序表中序号为有序表中序号为有序表中序号为mid=(n+1)/2mid=(n+1)/2的记录，根的记录，根的记录，根的记录，根结点的左子树是与有序表结点的左子树是与有序表结点的左子树是与有序表结点的左子树是与有序表r1 rmid1r1 rmid1相对应的折半查找判定树，根结点的右子树相对应的折半查找判定树，根结点的右子树相对应的折半查找判定树，根结点的右子树相对应的折半查找判定树，根结点的右子树是与是与是与是与rmid+1 rnrmid+1 rn相对应的折半查找判相对应的折半查找判相对应的折半查找判相对应的折半查找判定树。定树。定树。定树。11223344510111191089785667内部结点内部结点外部结点外部结点3691011784512具有具有具有具有n n个结个结个结个结点的折半查找判定树的深度为点的折半查找判定树的深度为点的折半查找判定树的深度为点的折半查找判定树的深度为 查查查查找找找找成成成成功功功功：在在在在表表表表中中中中查查查查找找找找任任任任一一一一记记记记录录录录的的的的过过过过程程程程，即即即即是是是是折折折折半半半半查查查查找找找找判判判判定定定定树树树树中中中中从从从从根根根根结结结结点点点点到到到到该该该该记记记记录录录录结结结结点点点点的的的的路路路路径径径径，和和和和给给给给定定定定值值值值的比较次数等于该记录结点在树中的层数。的比较次数等于该记录结点在树中的层数。的比较次数等于该记录结点在树中的层数。的比较次数等于该记录结点在树中的层数。查查查查找找找找不不不不成成成成功功功功：查查查查找找找找失失失失败败败败的的的的过过过过程程程程就就就就是是是是走走走走了了了了一一一一条条条条从从从从根根根根结结结结点点点点到到到到外外外外部部部部结结结结点点点点的的的的路路路路径径径径，和和和和给给给给定定定定值值值值进进进进行行行行的的的的关关关关键键键键码码码码的的的的比比比比较次数等于该路径上内部结点的个数。较次数等于该路径上内部结点的个数。较次数等于该路径上内部结点的个数。较次数等于该路径上内部结点的个数。1log2+n折半查找的性能分析折半查找的性能分析v有n个结点的判定树的深度为log2n+1v折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度v折半查找的时间复杂度为O(log2n)v折半查找的ASL 设设设设有有有有序序序序顺顺顺顺序序序序表表表表中中中中的的的的元元元元素素素素依依依依次次次次为为为为017,017,094,094,154,154,170,170,275,275,503,503,509,509,512,512,553,553,612,612,677,677,765,765,897,897,908908。试试试试画画画画出出出出对对对对其其其其进进进进行行行行折折折折半半半半搜搜搜搜索索索索时时时时的的的的二二二二叉叉叉叉判判判判定定定定树树树树,并并并并计计计计算算算算搜搜搜搜索索索索成成成成功功功功的的的的平平平平均均均均搜搜搜搜索索索索长长长长度度度度和和和和搜搜搜搜索索索索不不不不成成成成功功功功的的的的平平平平均均均均搜搜搜搜索索索索长度。长度。长度。长度。练习练习 设设设设有有有有序序序序顺顺顺顺序序序序表表表表中中中中的的的的元元元元素素素素依依依依次次次次为为为为017,017,094,094,154,154,170,170,275,275,503,503,509,509,512,512,553,553,612,612,677,677,765,765,897,897,908908。试试试试画画画画出出出出对对对对其其其其进进进进行行行行折折折折半半半半搜搜搜搜索索索索时时时时的的的的二二二二叉叉叉叉判判判判定定定定树树树树,并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。练习练习 9.1.4 索引顺序表的查找索引顺序表的查找 索引顺序表查找索引顺序表查找 的思想的思想 索引顺序表查找，是顺序查找的一种改进方法，又称分块查找。具体实现如下：将一个主表分成n个子表，要求子表之间元素是按关键字有序排列的，而子表中元素可以无序的，用每个子表最大关键字和指示块中第一个记录在表中位置建立索引表。typedef struct int key;NODE;typedef struct int key,pos;INDEX;例 如，给 定 关 键 字 序 列 如 下：22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53,假设n=3，即将该序列分成3个子表，每个子表有6个元素，则得到的主表和索引表如图所 示。1 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 索引查找的过程是先确定待查记录所在的块，然后在块中顺序查找。假设给定k=38,则先在索引表中按顺序比较，因为22k48，则可确定38应该在第二块中，从第二块的第一个记录 array7 顺序查起.索引查找的时间复杂度是O（m+n)m是块长度，n是索引表长度。查找38分块查找方法的ASL分块检索算法分块检索算法 （1）当顺序检索索引表时：）当顺序检索索引表时：#define M 99typedef struct keytype key;int stadr;int len;indexlist;/*索引表的类型定义索引表的类型定义*/indexlist IDM;/*ID为具有为具有indexlist类型的类型的R上的一个索引表上的一个索引表*/int Blocksrch(R，ID，m，k)sqlist R ;indexlist ID ;/*索引表索引表ID*/keytype k;int m;int i,j i=0;while(i IDi.key)/*顺序检索索引表顺序检索索引表*/i+;if(im-1)retutn(0)/*检索失败检索失败*/else j=Ri.stadr；/*待检索块的第一个记录的下标待检索块的第一个记录的下标*/while(j IDi.stadr+IDi.len)&(k!=Rj.key)j+;/*第第i块中顺序检索给定值为块中顺序检索给定值为K的记录元素的记录元素*/if(j=IDi.stadr+IDi.len)retutn(0)/*块中检索失败块中检索失败*/else return(j);/*检索成功检索成功*/*Blocksrch*/（2）当折半检索索引表时：indexlist IDM;/*ID为具有indexlist类型的R上的一个索引表*/int Blocksrch(sqlist R，indexlist ID，int m，keytype k)int i，j，low1，low2，mid，high1，high2；low1=0;high1=m-1;/*置折半检索区间的下、上界的初值*/while(low1=high1)/*在索引表中检索*/mid=(low1+high1)/2;/*求当前区间的中间位置*/if(k=IDmid.key)high1=mid-1;/*在左区间上检索*/else low1=mid+1;/*在右区间上检索*/*检索结束，low1为块号*/if(low1m)low2=IDlow1.stadr;/*块起始地址*/if(low1=m-1)high2=n-1;/*块末地址*/else high2=IDlow1+1.stadr-1;for(i=low2；ikey=k)return(p);/查找成功 else if(p-keyk)p=p-lch;/进入左子树查找 else p=p-rch;/进入右子树查找 return(NULL);二叉排序树的插入二叉排序树的插入在一棵二叉排序树中插入值为在一棵二叉排序树中插入值为在一棵二叉排序树中插入值为在一棵二叉排序树中插入值为k k的结点，步骤如下：的结点，步骤如下：的结点，步骤如下：的结点，步骤如下：若二叉排序树为空，则生成值为若二叉排序树为空，则生成值为若二叉排序树为空，则生成值为若二叉排序树为空，则生成值为k k的新结点的新结点的新结点的新结点s s，同时将新结，同时将新结，同时将新结，同时将新结点点点点s s作为根结点插入。作为根结点插入。作为根结点插入。作为根结点插入。若若若若k k小于根结点的值，则在根的左子树中插入值为小于根结点的值，则在根的左子树中插入值为小于根结点的值，则在根的左子树中插入值为小于根结点的值，则在根的左子树中插入值为k k的结点。的结点。的结点。的结点。若若若若k k大于根结点的值，则在根的右子树中插入值为大于根结点的值，则在根的右子树中插入值为大于根结点的值，则在根的右子树中插入值为大于根结点的值，则在根的右子树中插入值为k k的结点。的结点。的结点。的结点。若若若若k k等于根结点的值，表明二叉排序树中已有此关键字，等于根结点的值，表明二叉排序树中已有此关键字，等于根结点的值，表明二叉排序树中已有此关键字，等于根结点的值，表明二叉排序树中已有此关键字，则无须插入。则无须插入。则无须插入。则无须插入。P228 P228 算法算法算法算法9.69.6。例：插入值为例：插入值为例：插入值为例：插入值为9898的结点的结点的结点的结点63559058 7098root sroot二叉排序树的构造二叉排序树的构造从空的二叉排序树开始，依次插入一个个结点从空的二叉排序树开始，依次插入一个个结点从空的二叉排序树开始，依次插入一个个结点从空的二叉排序树开始，依次插入一个个结点 。例：关键码集合为例：关键码集合为例：关键码集合为例：关键码集合为6363，9090，7070，5555，5858，二二二二叉排序树的构造过程为：叉排序树的构造过程为：叉排序树的构造过程为：叉排序树的构造过程为：63559058 70n n一个无序序列可以通过构造一棵二叉排序树而一个无序序列可以通过构造一棵二叉排序树而一个无序序列可以通过构造一棵二叉排序树而一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列变成一个有序序列变成一个有序序列变成一个有序序列;n n每次插入的新结点都是二叉排序树上新的叶子每次插入的新结点都是二叉排序树上新的叶子每次插入的新结点都是二叉排序树上新的叶子每次插入的新结点都是二叉排序树上新的叶子结点结点结点结点;n n找到插入位置后，不必移动其它结点，仅需修找到插入位置后，不必移动其它结点，仅需修找到插入位置后，不必移动其它结点，仅需修找到插入位置后，不必移动其它结点，仅需修改某个结点的指针；改某个结点的指针；改某个结点的指针；改某个结点的指针；n n在左子树在左子树在左子树在左子树/右子树的查找过程与在整棵树上查右子树的查找过程与在整棵树上查右子树的查找过程与在整棵树上查右子树的查找过程与在整棵树上查找过程相同；找过程相同；找过程相同；找过程相同；n n新插入的结点没有破坏原有结点之间的关系。新插入的结点没有破坏原有结点之间的关系。新插入的结点没有破坏原有结点之间的关系。新插入的结点没有破坏原有结点之间的关系。n n在二叉排序树中查找给定值在二叉排序树中查找给定值k的过程是：的过程是：n n 若二叉排序树为空，则表明查找失败，返若二叉排序树为空，则表明查找失败，返若二叉排序树为空，则表明查找失败，返若二叉排序树为空，则表明查找失败，返回空指针；否则，若给定值回空指针；否则，若给定值回空指针；否则，若给定值回空指针；否则，若给定值k k等于根结点的等于根结点的等于根结点的等于根结点的值，则表明查找成功，返回根结点；值，则表明查找成功，返回根结点；值，则表明查找成功，返回根结点；值，则表明查找成功，返回根结点；n n 若给定值若给定值若给定值若给定值k k小于根结点的值，则继续在根小于根结点的值，则继续在根小于根结点的值，则继续在根小于根结点的值，则继续在根的左子树中查找；的左子树中查找；的左子树中查找；的左子树中查找；n n 若给定值若给定值若给定值若给定值k k大于根结点的值，则继续在根大于根结点的值，则继续在根大于根结点的值，则继续在根大于根结点的值，则继续在根的右子树中查找。的右子树中查找。的右子树中查找。的右子树中查找。n n这是一个递归查找过程。这是一个递归查找过程。P228算法算法9.5二叉排序树的查找二叉排序树的查找例：在二叉排序树中查找关键字值为例：在二叉排序树中查找关键字值为例：在二叉排序树中查找关键字值为例：在二叉排序树中查找关键字值为3535，9595的过程：的过程：的过程：的过程：50302080908588403532二叉排序树的查找二叉排序树的查找50302080908588403532二叉排序树的查找性能分析二叉排序树的查找性能分析由序列由序列由序列由序列3,1,2,5,43,1,2,5,4得到二叉排序树：得到二叉排序树：得到二叉排序树：得到二叉排序树：由序列由序列由序列由序列1,2,3,4,51,2,3,4,5得到二叉排序树：得到二叉排序树：得到二叉排序树：得到二叉排序树：ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2二叉排序树的查找性能取决于二叉排序树的形状，二叉排序树的查找性能取决于二叉排序树的形状，二叉排序树的查找性能取决于二叉排序树的形状，二叉排序树的查找性能取决于二叉排序树的形状，在在在在O O(loglog2 2n n)和和和和O O(n n)之间。之间。之间。之间。1234531254二叉排序树查找的性能分析二叉排序树查找的性能分析 在二叉排序树查找中，成功的查找次数不会超过二叉树的深度。具有n个结点的二叉排序树的深度，最好为log2n，最坏为n（一个序列的二叉排序树是不唯一的，折半查找的判定树是唯一的）。二叉排序树查找的最好时间复杂度为O(log2n)，最好的平均查找长度和log2n成正比；二叉排序树查找的最坏时间复杂度为O(n)，最坏的平均查找长度为(n+1)/2，与顺序查找相同。一般情形下，二叉排序树查找的时间复杂度大致可看成O(log2n)，比顺序查找效率要好，但比折半查找要差。二叉排序树的删除二叉排序树的删除n n在二叉排序树上删除某个结点之后，仍在二叉排序树上删除某个结点之后，仍然保持二叉排序树的特性。然保持二叉排序树的特性。n n分三种情况讨论：分三种情况讨论：n n被删除的结点是叶子；被删除的结点是叶子；被删除的结点是叶子；被删除的结点是叶子；n n被删除的结点只有左子树或者只有右子树；被删除的结点只有左子树或者只有右子树；被删除的结点只有左子树或者只有右子树；被删除的结点只有左子树或者只有右子树；n n被删除的结点既有左子树，也有右子树。被删除的结点既有左子树，也有右子树。被删除的结点既有左子树，也有右子树。被删除的结点既有左子树，也有右子树。情况情况1被删除的结点是叶子结点被删除的结点是叶子结点50302080908588403532503020809085403532操作：操作：将双亲结点中相应指针域的值改为空。将双亲结点中相应指针域的值改为空。情况情况2被删除的结点只有左子树或者只被删除的结点只有左子树或者只有右子树有右子树操作：操作：将双亲结点的相应指针域的值指向被删除将双亲结点的相应指针域的值指向被删除结点的左子树（或右子树）。结点的左子树（或右子树）。50302080908588403532503020908588403532情况情况3被删除的结点既有左子树也有被删除的结点既有左子树也有右子树右子树操作：操作：以其前驱（左子树中的最大值）替代以其前驱（左子树中的最大值）替代之，然后再删除该前驱结点。之，然后再删除该前驱结点。50302080908588403532403020809085883532status DeleteBST(BiTree&T,KeyType key)if(!T)return FALSE;else if(EQ(key,T-data.key)return Delete(T);else if(LT(key,T-data.key)return DeleteBST(T-lchild,key);else ruturn DeleteBST(T-rchild,key);Status Delete(BiTree&p)if(!p-rchild)q=p;p=p-lchild;free(q);else if(!p-lchild)q=p;p=p-rchild;free(q);else 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;delete s;return TRUE;9.2.2 平衡二叉树查找平衡二叉树查找平衡二叉树的概念平衡二叉树的概念 平衡二叉树(balanced binary tree)是由阿德尔森一维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。将该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子(balance factor)。也就是说，一棵二叉排序树中，所有结点的平衡因子只能为0、1、-1时，则该二叉排序树就是一棵平衡二叉树，否则就不是一棵平衡二叉树。若一棵二叉排序树是一棵平衡二叉树，则它将具有较好的平均查找长度。如图9-4所示二叉排序树，是一棵平衡二叉树，而如图9-5所示二叉 排序树，就不是一棵平衡二叉树。n n基本思想基本思想：在构造二叉排序树的过程中，：在构造二叉排序树的过程中，每插入一个结点时，首先检查是否因插每插入一个结点时，首先检查是否因插入而破坏了树的平衡性，若是，在保持入而破坏了树的平衡性，若是，在保持二叉排序树特性的前提下，调整各结点二叉排序树特性的前提下，调整各结点之间的链接关系，进行相应的旋转，使之间的链接关系，进行相应的旋转，使之成为新的平衡子树。之成为新的平衡子树。平衡二叉树的构造平衡二叉树的构造平衡二叉树的构造平衡二叉树的构造n n设结点设结点A为为最小不平衡子树最小不平衡子树的根结点，对的根结点，对该子树进行平衡调整归纳起来有以下四该子树进行平衡调整归纳起来有以下四种情况：种情况：n n1.LL1.LL型型型型n n2.RR2.RR型型型型n n3.LR3.LR型型型型n n4.RL4.RL型型型型二叉检索树的调整二叉检索树的调整 AdelsonVelskii和和Landis提出了一个动态地提出了一个动态地保持二叉检索树平衡的方法。其基本思想是：在构保持二叉检索树平衡的方法。其基本思想是：在构造二叉检索树的过程中，每当插入一个新结点时，造二叉检索树的过程中，每当插入一个新结点时，首先检查是否由于新结点的插入而破坏了二叉树的首先检查是否由于新结点的插入而破坏了二叉树的平衡性。若是，则找出其中最小的不平衡树，在保平衡性。若是，则找出其中最小的不平衡树，在保持检索树特性的前提下，通过调整最小不平衡子树持检索树特性的前提下，通过调整最小不平衡子树中结点之间的关系，使它满足平衡树的特性，达到中结点之间的关系，使它满足平衡树的特性，达到新的平衡。所谓最小不平衡子树即指离插入结点最新的平衡。所谓最小不平衡子树即指离插入结点最近，且以平衡因子绝对值超过近，且以平衡因子绝对值超过1的结点为根的子树。的结点为根的子树。设在插入结点的过程中，使二叉树失去平衡设在插入结点的过程中，使二叉树失去平衡的最小不平衡子树的根结点为的最小不平衡子树的根结点为a点，则可依据插入点，则可依据插入结点位置的不同情形一般有以下四种：结点位置的不同情形一般有以下四种：（1）LL型平衡旋转型平衡旋转 在结点在结点a的左孩子的左子树上插入结点，使一的左孩子的左子树上插入结点，使一棵二叉树上结点棵二叉树上结点a的平衡因子由的平衡因子由1增至增至2而失去平衡，而失去平衡，此时须进行一次顺时针旋转操作。如下图所示。此时须进行一次顺时针旋转操作。如下图所示。（2）RR型平衡旋转型平衡旋转 由于在由于在a的右孩子的右子树上插入新结点，使的右孩子的右子树上插入新结点，使a的平衡因子由的平衡因子由1增到增到2而失去平衡。此时应以而失去平衡。此时应以b为轴心作逆时针旋转，使结点为轴心作逆时针旋转，使结点a作为结点作为结点b的左孩子，的左孩子，如下图所示。如下图所示。（3）LR型平衡旋转型平衡旋转 在结点在结点a的左孩子的右子树上插入新结点的左孩子的右子树上插入新结点c，使，使a的平衡因子由的平衡因子由1增到增到2而失去平衡。此时需进行两而失去平衡。此时需进行两次旋转。首先以新结点次旋转。首先以新结点c为轴心作逆时针旋转，使为轴心作逆时针旋转，使得结点得结点a的左孩子变为新结点的左孩子变为新结点c的左孩子，然后再以的左孩子，然后再以新结点新结点c为轴心作顺时针旋转，使得结点为轴心作顺时针旋转，使得结点a变为新结变为新结点点c的右孩子。如下图所示。的右孩子。如下图所示。（4）RL型平衡旋转型平衡旋转 由于在由于在a的右孩子的左子树中插入新结点的右孩子的左子树中插入新结点c，使，使a的平衡因子由的平衡因子由1增到增到2而失去平衡。此时首先应以而失去平衡。此时首先应以新结点新结点c为轴心作顺时针旋转，使得结点为轴心作顺时针旋转，使得结点a右孩子变右孩子变为新结点为新结点c的右孩子，然后再以新结点的右孩子，然后再以新结点c为轴心作逆为轴心作逆时针旋转，使得结点时针旋转，使得结点a变为新结点变为新结点c的左孩子，如下的左孩子，如下图所示。图所示。练习：设有关键码序列练习：设有关键码序列练习：设有关键码序列练习：设有关键码序列4444，5 5 5 5，7 7 7 7，2 2 2 2，1 1 1 1，3 3 3 3，6 6 6 6，构造平衡二叉树构造平衡二叉树构造平衡二叉树构造平衡二叉树练习：设有关键码序列练习：设有关键码序列练习：设有关键码序列练习：设有关键码序列4444，5 5 5 5，7 7 7 7，2 2 2 2，1 1 1 1，3 3 3 3，6 6 6 6，构造平衡二叉树构造平衡二叉树构造平衡二叉树构造平衡二叉树练习：设有关键码序列练习：设有关键码序列练习：设有关键码序列练习：设有关键码序列4444，5 5 5 5，7 7 7 7，2 2 2 2，1 1 1 1，3 3 3 3，6 6 6 6，构造平衡二叉树构造平衡二叉树构造平衡二叉树构造平衡二叉树 索引文件的树型索引表结构通常采用索引文件的树型索引表结构通常采用B树结构。树结构。B树又包含树又包含B树和树和B+树两种，它们都是一种适用于树两种，它们都是一种适用于外检索的树型结构，是一种平衡的多路检索树。外检索的树型结构，是一种平衡的多路检索树。B树树B树的定义树的定义 一棵一棵m阶的阶的B树是一种平衡的多路检索树，它或者是一棵空树，树是一种平衡的多路检索树，它或者是一棵空树，或者是一棵满足下列特性的或者是一棵满足下列特性的m叉树：叉树：（1）树中每个结点至多有）树中每个结点至多有m棵子树；棵子树；（2）除非根结点为叶子结点，否则它至少有两棵子树；）除非根结点为叶子结点，否则它至少有两棵子树；（3）除根结点之外的所有非终端结点至少有）除根结点之外的所有非终端结点至少有 棵子树；棵子树；（4）所有的叶子结点均保持在同一层上，且不包含任何信息；）所有的叶子结点均保持在同一层上，且不包含任何信息；B树树 （5）所有的非终端结点中包含有下列信息：）所有的非终端结点中包含有下列信息：（n，A0，K1，A1，K2，A2，Kn，An）其中，其中，K1，K2，Kn为为n个按从小到大顺序排列的关键字，个按从小到大顺序排列的关键字，A0，A1，A2，An为为n+1个指向子树根结点的指针，用于指向该结个指向子树根结点的指针，用于指向该结点的点的n+1个子树或孩子，其中个子树或孩子，其中A0所指向孩子中的所有关键字均小于所指向孩子中的所有关键字均小于K1，An所指向孩子中的所有关键字均大于所指向孩子中的所有关键字均大于Kn，Ai（0in）所）所指向孩子中的所有关键字均小于指向孩子中的所有关键字均小于Ki+1，但大于，但大于Ki。例如，下图为一棵由例如，下图为一棵由11个关键字生成的个关键字生成的3阶阶B树的示意图。树的示意图。B树的检索树的检索 在在B树上进行检索的过程类似于二叉检索树，都是走了一条从树树上进行检索的过程类似于二叉检索树，都是走了一条从树根结点到待检索关键字所在结点的检索路径，不过通常需要经过同多个根结点到待检索关键字所在结点的检索路径，不过通常需要经过同多个关键字比较后才能确定一个结点。需要先在关键字比较后才能确定一个结点。需要先在B树中检索结点，而后在结树中检索结点，而后在结点中检索关键字，从而判断是否检索成功或失败。点中检索关键字，从而判断是否检索成功或失败。检索检索B-B-树所需比较的树所需比较的结点结点要比在二叉检索树上检索所需比较的结点数要少得多。要比在二叉检索树上检索所需比较的结点数要少得多。例如，对于上图，若要检索关键字值等于例如，对于上图，若要检索关键字值等于70的结点，其具体过程的结点，其具体过程为：由于树不空，首先从根结点开始，找到结点为：由于树不空，首先从根结点开始，找到结点a，由于，由于a中只有一个中只有一个关键字，且给定值关键字，且给定值7050，所以由指针，所以由指针A1可找到结点可找到结点c，该结点有两，该结点有两个关键字（个关键字（55和和80），由于），由于557080，若待检索关键字，若待检索关键字70存在，存在，则必在则必在c结点中指针结点中指针A1所指的子树中，然后由指针所指的子树中，然后由指针A1找到结点找到结点g，在结，在结点点g中顺序检索，可检索到关键字中顺序检索，可检索到关键字70，此时检索成功。，此时检索成功。B树结点的插入树结点的插入 在在B树上插入一个数据元素首先要检索出关树上插入一个数据元素首先要检索出关键字的正确插入位置，然后再进行插入。在键字的正确插入位置，然后再进行插入。在B树中树中插入新元素不是添加新的叶子结点，而是需要先判插入新元素不是添加新的叶子结点，而是需要先判断该结点是否已有断该结点是否已有m1个键字，若不是个键字，若不是m1个关键个关键字，则按关键字（设为字，则按关键字（设为k）的大小有序地插入到适当）的大小有序地插入到适当的位置，否则，由于结点的关键字个数为的位置，否则，由于结点的关键字个数为m，超过，超过了结点所规定的范围，需要进行结点的了结点所规定的范围，需要进行结点的“分裂分裂”。例如，对一组关键字（例如，对一组关键字（25，80，40，45，56，75，85，20），从），从3阶的空的阶的空的B树开始，依树开始，依次插入关键字。其具体过程如下图（次插入关键字。其具体过程如下图（a）到（）到（k）图。）图。8.4.2 B树树 B+树是应用于文件系统中的树是应用于文件系统中的B树的一种变形树，一树的一种变形树，一棵棵m阶的阶的B+树与相应的树与相应的B树的差异主要在于：树的差异主要在于：有有n棵子树的结点中含有棵子树的结点中含有n个关键字；个关键字；所有叶子结点中包含了全部关键字的信息及指向相所有叶子结点中包含了全部关键字的信息及指向相应记录的指针，且叶子结点以关键字值递增顺序链接；应记录的指针，且叶子结点以关键字值递增顺序链接；所有的非终端结点可以看成是索引部分，结点中仅所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大（或最小）关键字。含有其子树中的最大（或最小）关键字。如下图给出了一棵如下图给出了一棵3阶阶B+树。树。t50 8023 5060 70 8010 2328 5058 60sqt图8.21 一棵3阶B+树示例65 7076 8093 哈希表（散列查找哈希表（散列查找）9.3.1 基本概念基本概念哈希表的基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法注：它与前面介绍的查找方法完全不同，前面介绍的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方法，而散列查找是通过构造哈希函数来得到待查关键字的地址，按理论分析，真正不需要用到比较的一种查找方法。例如：要找关键字为k的元素，则只需求出哈希函数值H（k），（H（k）为给定的哈希函数，代表关键字k在存贮区中的地址。）然后直接到该地址找到该记录。定