《数据结构》课件(C语言)第09章.ppt

数据结构,第九章 查找,第2页,第九章 查 找,内容和要求 查找的概念，顺序查找、二分法查找、分块查找的概念和方法，二叉排序树、平衡二叉树的查找，哈希表查找。要求获得有关静态和动态环境下几种基本的查找方法和技术知识。掌握顺序、二分法和分块查找的方法；了解哈希表是一种基本的存储结构、哈希表的背景和基本思路。掌握哈希表处理冲突的方法。 重点 二分法查找方法；哈希表的动态查找。,第3页,查找表 由同一类型的数据元素（或记录）构成 的集合,基本概念,静态查找表 仅作查询与检索（统称为查找）工作的查找表。 动态查找表 除作查询与检索之外，还需作诸如插入、删除之类更新操作的查找表。,查找 在一个含有众多数据元素（或记录）的查找表中找出某个“特定的”数据元素（或记录）的过程。,关键字 能够标识一个数据元素（或记录）的某个数据项的值。当数据元素只有一个数据项时，其关键字即为该数据元素的值。 主关键字 能唯一地标识一个记录的关键字。,给定一个值k，在含有n个记录(或数据元素)的表中找出关键字等于给定值k的记录，若找到，则查找成功，查找结果为给出整个记录的信息，或指示该记录在查找表中的位置；若找不到，则查找不成功，查找结果为NULL值或值0。,第4页,查找操作主要是关键字的比较，故通常把查找过程中对关键字需要执行的平均比较次数（亦称平均查找长度）作为衡量一个查找算法效率优劣的标准。,基本概念,平均查找长度 为了确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值(平均值)称为查找算法在查找成功时的平均查找长度(Average Search Length)。,对于含有n个记录的表，查找成功时的平均查找长度为 (9-1) 其中 Pi：表中第i个记录被查找的概率，有 ； Ci：找到表中其关键字与给定值相等的第i个记录时，所需要的比较次数。 若无特别声明，均认为表中每个记录的概率均相等，即,第5页,约定和宏定义,宏定义 #define EQ( a, b ) (a) = (b) #define LT( a, b ) (a) (b) #define LQ( a, b ) (a) = (b) 注：宏定义随不同的数据类型，有所不同。,第6页,1、静 态 查 找 表,静态查找表的ADT 静态查找表是一种最简单的查找表。 Specification ADT Static_Search_Table Elements：查找表中的数据元素类型相同，每一数据元素 都存在一个能唯一标识该元素的关键字 Structure：查找表中的n个数据元素具有相同类型，属于 同一集合。数据元素之间不存在结构关系 Operation： Create(ST,n) 生成操作：产生一个含用户给定的n个数据元素的表ST。 Search(ST,K) 查找函数: 若表ST中存在其关键字等于给定值K的数据元素，则函数值为该元素在表中的位置；否则函数值为“空”。 Traverse(ST) 输出操作：按某种次序输出表ST中所有数据元素。,第7页,顺序(线性)表的查找顺序查找,顺序（线性）表的查找是一种最简单的查找方法。它的算法基本思想是：,从表的一端开始，顺序地扫描线性表，依次将扫描到的关键字和给定值相比较，若当前扫描到的记录的关键字与给定值相等，则查找成功，找到所查记录；若直至扫描结束，仍未找到其关键字与给定值相等的记录，则查找不成功。,既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。若使用单链表作存储结构时，扫描必须从第一个结点开始。若以向量作存储结构，则可从前往后或从后往前进行扫描。,第8页,顺序表的查找算法描述,typedef struct ElemType elem; int Length; SSTable;,顺序（线性）表的查找,int seqsearch( SSTable st, keytype k ) /*K为给定值，返回i为关键字等于K的记录在表st中的序号，i值为零表明查找不成功*/ st.elem0.key = K; /设置监视哨 for( i = st.length; !EQ( st.elemi.key, key ); i-) /从表尾开始向前扫描 return i; /返回找到的位置 /算法 9.1,第9页,算法性能分析,若查找每个记录时是等概率，则有 ASLss=(n+1)/2,顺序（线性）表的查找,(9-2),第10页,如果考虑到不成功的查找，则查找算法的平均查找长度应是查找成功时的平均长度与查找不成功时的平均查找长度之和。若假设查找成功与不成功的可能性相同，对每个记录的查找概率也相等，即 。由于查找不成 功的比较次数总是n+1，故顺序查找的平均查找长度为,顺序（线性）表的查找,第11页,(2) 当表中各个记录的查找概率互不相等时，为了提高查找效率，宜将诸记录先按查找概率由小到大进行排列（式(9-2)在P1P2Pn-1Pn时达到极小值）；,说明： (1) 顺序查找算法简单，且对表的结构无任何要求（无论按向量还是链表结构，无论记录间是否按关键字有序排列），故此算法适应面广。但当n1时，查找效率随n越大而越低。,顺序（线性）表的查找,(3) 在很多实际应用的情况下，各记录的查找概率无法事先确定，则可以采用“自组织”形式的顺序查找表。,第12页,有序表的查找折半查找,折半查找又称二分查找（Binary Search），它是一种效率高的查找方法。 折半查找的前提是静态查找表是有序表，即表中记录按关键字有序排列，且需使用向量作为表的存储结构。不妨设有序表是递增有序的。,折半查找的算法思想： 先确定待查记录所在的范围（区间），然后以处于区间中间位置记录的关键字和给定值K相比较，（1）若相等，则查找成功；（2）若不等，则缩小范围，继续按此法查找，直至新的区间位置记录的关键字等于给定值K，或者查找区间的大小等于零（表明查找不成功）时为止。,猜数游戏的方法,第13页,有序表的折半算法描述,int Search_Bin( SSTable st, KeyType key ) /在有序表st中折半查找关健字等于给定值key的记录 int mid; low = 1; hig = st.Length; /置区间初值 while( low hig ) /判别查找区间大小 mid = ( low + hig ) / 2; switch case K st.elemmid.key: low = mid+1; case K = st.elemmid.key: return mid; case K st.elemmid.key: hig = mid-1; return( 0 ); /查找不成功 / 算法 9.2,有序表的查找折半查找,第14页,算法性能分析,这棵二叉树并非完全二叉树，但其叶结点所在层次之差至多为1。因此，该二叉树深度与一根完全二叉树相同， 为 。这里n是二叉树结点的个数，亦即有序表中数据元素的个数。,折半查找过程中可用二叉树来描述（判定树）。树根为表的中间记录。根的左子树关键字均小于根的关键字，根的右子树关键字均大于根的关键字。,有序表的查找折半查找,第15页,结论：折半查找法在查找成功时进行比较的关键字个数最多不超过树的深度，即 问题：查找不成功的情况如何？,示例2 对于如示例1所给数据，描述折半查找过程加上外部结点的判定树和查找关健字为85的结点，示意如下,结论：折半查找在查找不成功时和给定值进行比较的关健字个数最多不超过,有序表的查找折半查找,第16页,折半查找的平均查找长度的计算： 记 h=log2(n+1) ，即有 n=2h-1，则描述折半查找的判定树是深度为h的满二叉树。设表中每个记录的查找概率均相等（Pi=1/n），则查找成功时折半查找的平均查找长度,其中j为层数，2j-1为该层结点数。,记 ，则,故有,因为,当n1时，有,有序表的查找折半查找,第17页,说明： 折半查找的效率比顺序查找高。,有序表的查找折半查找,而排序本身是一种很费时的操作，即使采用高效率的排序方法也要花费 O(nlog2n) 的时间代价。,另外，折半查找仅适用于顺序存储结构，为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。故折半查找特别适用于那些一经建立就很少改动，而又经常需要查找的线性表，而对那此查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找；,第18页,索引顺序表的查找分块查找,以索引顺序表表示静态查找表时，可采用分块查找（Blocking Search）方法来进行查找。 分块查找又称索引顺序查找，它是一种性能介于顺序查找和折半查找之间的方法。,分块查找法要求按如下的索引方式来存储一个线性表： 将表 R1n 均分为b块，前b-1块中结点个数为 ，第b块的结点数小于或等于S。每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即要求表是 “分块有序”的。抽取各块中的最大关键字及起始位置，构成一个索引表 ID1b。由于表R是分块有序的，所以索引表应是一个递增有序表。,第19页,示例3 分块有序表的索引存储表示,分块查找的算法思想： (1) 查找索引表，确定待查关键字所在的块（子表）。由于索引表是按记录关健字有序，故宜采用折半查找法； (2) 在所确定的块中查找是否存在关键字与给定值相同的记录。此时需采用顺序查找法。 故分块查找的算法实际上是折半查找算法和顺序查找算法的简单合成。,索引顺序表的查找分块查找,图9.6 表及其索引表,第20页,分块查找的算法分析 分块查找实际上是两次查找过程，故整个算法的平均查找长度是两次查找的平均查找长度之和，即 ASLbs=Lb+Lw， 其中 Lb：查找索引表所在子表的平均查找长度 Lw：在子表中顺序查找记录的平均查找长度 设将表均匀分布成b个子表，每个子表包含s个记录（最后一个子表可能不足s个记录），并设表中每个记录的查找概率均相等，即每个子表的查找概率为1/b，子表中每个记录的查找概率为1/s。,(1) 若用顺序查找确定所在块，则,索引顺序表的查找分块查找,与表长n有关， 与块中记录个数s有关,第21页,(2) 若用折半查找法确定所在块，则,示例4 若表中有n=10000个记录，取 即将该表分成100块，每块中含100个记录。则用顺序查找确定块的分块查找平均需要做101次比较，而若用折半查找确定所在块，则最多需做约57次比较。 若使用顺序查找，平均需做约5000次比较，而使用折半查找，则最多需做约14次比较。 故分块查找算法的效率介于顺序查找和折半查找算法之间。,索引顺序表的查找分块查找,第22页,说明： (1) 分块查找的优点是，在表中插入或删除一个记录时，只要找到该记录应当所属的块，然后在块内进行插入和删除运算。因为块内记录的存放是任意的，所以插入或删除比较容易，不需要移动大量记录。分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的操作；,索引顺序表的查找分块查找,(2) 在实用中，分块查找不一定要将线性表分成大小相等的若干块，而应该根据表的特征进行分块。例如，一个学校的学生登记表，可按系号或班号分块。此外，各块中的记录也不一定要存放在同一个向量中，可将各块放在不同的向量中，也可将每一块存放在同一个单链表中。,第23页,动 态 查 找 表,当用线性表作为表的组织形式时，可采用顺序查找、折半查找、分块查找等查找方法，其中以折半查找效率最高。但折半查找要求表中结点按关健字有序，且不能使用链表作存储结构。因此，当表的插入或删除操作频繁时，为了维护表的有序性，势必要移动表中很多结点，引起额外的时间开销，从而抵消了折半查找的优点。 希望采用既具有如折半查找那样的查找效率、又易于进行诸如插入、删除结点操作的表的组织方式。这就是动态查找表。,动态查找表的ADT,第24页,动态查找表既具有顺序表那样较高的检索效率，又具有链表那样插入、删除的灵活性。它可有不同的表示方法，但较典型的是采用特殊的树或二叉树作为动态查找表的一种组织方式，可统称为树表。,动态查找表的特点：表结构本身是在查找过程中动态生成的，即对于给定值K，若表中存在其关健字等于K的结点（记录），则查找成功返回，否则插入关健字等于K的结点（记录）。 在动态查找表中亦允许删除表中结点。,动 态 查 找 表,动态查找表的ADT,第25页,Specification ADT Dynamic_Search_Table Elements：表中各结点都含有一个类型相同的关健字，并且 该关健字可唯一地识别结点 Structure：n个结点具有查同属性，同属一个集合,动态查找表的ADT,Operation： Initialize(DT) 初始化操作： 设置一个空的动态查找表DT。 Search(DT,K) 查找函数： 若表DT中存在其关键字等于给定值K的结点，则函数值为该结点或它在表中的位置；否则函数值为“空”。 Insert(DT,K) 插入操作： 若表DT中存在其关键字等于给定值K的结点，则空操作；否则插入其关键字等于K的结点。 Delete(DT,K) 删除操作： 若表中存在其关键字等于给定值K的结点，则删除之；否则空操作。 Traverse(DT) 输出操作 按某种次序输出表DT中所有结点。,第26页,二叉排序树及其查找过程,二叉排序树（Binary Sort Tree） 又称为二叉查找树或二叉搜索树（Binary Search Tree）。它是一种特殊结构的二叉树。,动 态 查 找 表,定义 ： 二叉排序树或者是一棵空树，或者是具有如下性质的二叉树： (1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； (2) 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； (3) 它的左、右子树也分别为二叉排序树。 显见。关于二叉树排序树的这一定义是递归的。,第27页,示例1 如下是两棵二叉排序树,(a) 图9.7 二叉排序树示例 (b),二叉排序树的一个重要性质： 性质 对二叉排序树按中序遍历该树所得到的中序序列是一个递增有序序列。 故一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。,二叉排序树及其查找过程,第28页,二叉排序树的查找算法描述,BiTree bstsrch( BiTree t, KeyType K ) /在指针t所指的二叉排序树上查找其关健字等于给定值K的记录，当查找成功时，返回指向该记录结点的指针，否则返回空指针 if( t = NULL )|(t-data.key = K ) return t; else if( t-data.key rchild, k ); else return bstsrch( t-lchild, k ); /算 法 9.4(a),第29页,二叉排序树的插入和生成,二叉排序树是一种动态树表。其特点是，树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。,动 态 查 找 表,在二叉排序树中插入新结点，需保证插入后仍符合二叉排序树的定义。,在二叉排序树中插入新结点，需保证插入后仍符合二叉排序树的定义。 插入的前提：查找不成功 插入的位置：若二叉排序树为空，则插入结点成为新的根结点；否则，沿左子树或右子树继续查找，直至某结点的左子树或右子树为空为止，插入结点作为一个新的叶结点并成为该结点的左孩子或右孩子结点。,第30页,二叉排序树查找算法的修正算法,Status SearchBST( BiTree t, KeyType K, BiTree f, BiTree ,else if( Kdata.key ) /继续在左子树上进行查找 SearchBST(t-lchild, key, t, p ) else /继续在右子树上进行查找 SearchBST(t-rchild, key, t, p ) /算 法 9.4(b),参数f的作用？,第31页,二叉排序树的插入算法,Status ins_bstree( BiTree /算 法 9.5,第32页,从二叉排序树的生成过程可以看到，它经历了若干次插入新结点的操作。每次插入的新结点都是二叉排序树上新的叶子结点，则在进行插入操作时，不必移动其它结点，仅需改动某个结点的指针，由空变为非空即可。它表明，二叉排序树既有类似于折半查找的特性，又采用了链表作存储结构，因此是动态查找表的一种适宜表示。,示例2 设从空树出发，对于输入关键字序列45,24,53,12,37,93，经过一序列的查找、插入操作，可陆续生成一棵二叉排序树：,45,24,53,12,37,93,图9.8 二叉排序树的构造过程,二叉排序树的插入,初始,问题：如何实现在一 个二叉排序树上删除 某个结点？,第33页,二叉排序树的删除,从二叉排序树上删除一个结点，不能把以该结点为根的子树都删去，而只能删掉该结点自身，并且还要保证删除后所得的二叉树仍然满足二叉排序树的性质。也就是说，在二叉排序树中删去一个结点，相当于删去有序序列中的一个结点。 删除操作必须进行查找，以确定被删结点是否在二叉排序树中。若不在，则不做任何事情；若在，则设法删除之。,动 态 查 找 表,第34页,(3) p结点既有左子树又有右子树，即p结点的左、右子树均不空。 此时不能作简单处理，而需对p结点的左、右子树进行细化，目的是将p的左、右子树链接到合适的位置，并保持二叉排序树的特性。,假设在二叉排序树上被删结点为 p，其双亲结点为 f，且不失一般性，可设 p 是 f 的左指针,(2) p结点只有左子树pL或右子树pR，则令pL或pR直接成为 f结点的左子树即可;,二叉排序树的删除,分三种情况进行讨论删除操作,第35页,设删除结点 p之前二叉排序树的形状如下（细化PL）,按中序遍历所得序列为 CLCQLQSLSPPRF ,若欲删去结点 p，且保持二叉排序树的特性，则所指指针改变而获得的新二叉树排序树，经按中序遍历所得序列应为 CLCQLQSLSPRF ,P,C,CL,PR,p,c,F,f,Q,S,QL,SL,q,s,可采用两种做法实现之,做法一 令 p的左子树为 f的左子树，而 p的右子树为 s的右子树,做法二 令 p的直接前驱（或者接后继）替代 p，然后再从二叉排序树中删去它的直接前驱（或直接后继）,二叉排序树的删除,第36页,做法一 令 p 的左子树为 f 的左子树，而 p 的右子树为 s 的右子树,f-lchild = p-lchild; s-rchild = p-rchild;,P,C,CL,PR,p,c,F,f,Q,S,QL,SL,q,s,二叉排序树的删除,第37页,做法二 令 p 的直接前驱（或者接后继）替代 p，然后再从二叉排序树中删去它的直接前驱（或直接后继）,q = p; s = p-lchild; while( s-rchild NULL ) q = s; s = s-rchild ; p-data = s-data; /替代 if( q p ) q-rchild = s-lchild; else q-lchild = s-lchild; /删s free(s);,qp情形,q=p情形,P,C,CL,PR,p,c,F,f,Q,S,QL,SL,q,s,S,P,PR,p,F,f,S,SL,s,q,S,SL,首先查找s与q,s即为 p 的左孩子结点,二叉排序树的删除,第38页,二叉排序树的查找分析,示例3 设输入关键字序列分别为45,24,53,12,37,93以及12,24,37,45,53,93，则将生成两棵不同形态的二叉排序树,图9.10不同形态的二叉查找树 (a) 关键字序列为45,24,53,12,37,93的二叉排序树 (b) 关键字序列为12,24,37,45,53,93的单支树 当先后插入的关键字有序时，所构成的二叉排序树蜕变为单支树。,(a),(b),含有n个结点的二叉排序树的平均查找长度和树的形态有关。,第39页,二叉排序树的平均查找长度,(1) 最佳情况 二叉排序树的形态和折半查找的判定树相同 ASL=log2(n+1)-1 (2) 最差情况 二叉排序树蜕变为单支树 ASL=（n+1）/2 (3) 随机情况 ASL1+4log2n,二叉排序树的查找分析,就平均性能而言，二叉排序树上的查找和折半查找相差不大，并且二叉排序树的插入和删除结点十分方便，无需移动大量结点。因此，对于需要经常做插入、删除和查找操作的表，拟采用二叉排序树结构。,第40页,平衡二叉树,二叉排序树的查找效率取决于树的形态，而构造一棵形态匀称的二叉排序树与插入的先后次序往往不是随人的意志而定的，这就要求找到一种动态平衡的方法，对于任意给定的关健字序列都能构造一棵形态匀称的二叉排序树。也就是说，需在构成二叉排序树的过程中进行“平衡化”处理，成为平衡的二叉排序树。 把形态匀称的二叉树称为平衡二叉树（Balanced Binary Tree）,定义 平衡二叉树或者是一棵空树，或者是任何结点的左子树和右子树深度最多相差1的二叉树。 定义 二叉树上任一结点的左子树深度减去右子树深度之差称为该结点的平衡因子（Balance Factor）,问题：如何构造出一棵平衡的二叉排序树？,Adelson_Velskii和Landis提出了一个方法。 所以平衡的二叉排序树也简称为AVL树。,第41页,示例4 平衡二叉树、不平衡二叉树以及树中诸结点的平衡因子示例如下,1,1,(a),-1,-1,1,1,0,(b),0,0,0,0,图9.11 平衡与不平衡的二叉树及结点的平衡因子 (a)(b) 平衡二叉树； (c)(d) 不平衡的二叉树,2,-1,1,(c),-1,-2,1,0,0,(d),0,0,0,0,0,平衡二叉树,第42页,如何使构成的二叉树成为平衡树,平衡调整规律：假设由于在二叉排序树上插入结点而失去平衡的最小子树的根结点指针为a（即a是离插入结点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后进行调整规律可归纳为下列四种情况：,LL,插入前 插入20 调整后,(1) LL型平衡旋转 原因：在A的左子树的左子树上插入结点使A的平衡因子由1增至2 调整：进行一次顺时针旋转操作,示例：,第43页,(2) RR型平衡旋转 原因：在A的右子树的右子树上插入结点，使A的平衡因子由 -1减至-2 调整：进行一次逆时针旋转操作,RR型： b = a-rchild; a-rchild = b-lchild; a-bf = 0; b-lchild = a; b-bf = 0; /b为子树新根,如何使构成的二叉树成为平衡树,示例：,第44页,(3) LR型平衡旋转 原因：在A的左子树的右子树上插入结点，使A的平衡因子由 1增至2 调整：进行先逆时针、后顺时针共两次旋转操作,如何使构成的二叉树成为平衡树,插入19,先逆时针旋转,再顺时针旋转,第45页,LR 型：b = a-lchild; c = b-rchild; a-lchild = c-rchild; b-rchild = c-lchild; c-rchild = a; c-lchild = b; /c为子树新根 switch /插入之前 c-bf 为零，插入之后有三种情况 case c-bf = 1: a-bf = -1; b-bf = 0; case c-bf = -1: a-bf = 0; b-bf = 1 ; case c-bf = 0: a-bf = 0; b-bf = 0 ; ; c-bf = 0; b = c; /旋转变换以后，用c指向新树根,如何使构成的二叉树成为平衡树,第46页,(4) RL 型平衡旋转 原因：在A的右子树的左子树上插入结点，使A的平衡因子 由-1减至-2 调整：进行先顺时针、后逆时针共两次旋转操作,如何使构成的二叉树成为平衡树,24,70,37,13,-1,0,0,0,示例：,53,0,a,b,c,24,70,90,13,-2,1,0,0,70,0,a,b,c,24,37,90,13,-2,-2,0,0,90,0,c,a,b,37,70,53,24,0,0,0,1,90,0,37,-1,53,0,13,0,第47页,RL 型：b = a-rchild; c = b-lchild; a-rchild = c-lchild; b-lchild = c-rchild; c-rchild = b; c-lchild = a; switch case c-bf = 1: a-bf = 0; b-bf = -1; case c-bf = -1: a-bf = 1; b-bf = 0 ; case c-bf = 0: a-bf = 0; b-bf = 0 ; ; c-bf = 0; b = c;,如何使构成的二叉树成为平衡树,53,0,a,b,c,24,70,90,13,-2,1,0,0,90,0,c,a,b,37,70,53,24,0,0,0,1,37,-1,13,0,第48页,在平衡树上插入一个结点的算法描述,平衡旋转是当二叉排序树在插入结点后产生不平衡时进行的。为了使得到的二叉排序树为平衡树，需对插入算法 ins_bstree(t,k,s)作如下修改,为此，需要做到 (1) 在查找 s 结点的插入位置的过程中，记下离 s 结点最近且平衡因子不等于零的结点，令指针 a 指向该结点；,(1) 判别插入结点之后是否产生不平衡； (2) 找到失去平衡的最小子树； (3) 判别旋转类型并作相应调整处理。,(2) 修改自 a 至 s 路径上所有结点的平衡因子值；,(3) 判别树是否失去平衡，即在插入结点之后，a 结点的平衡因子绝对值是否大于1。若是，则需判别旋转类型并作相应处理，否则插入过程结束。,第49页,平衡树查找的分析,(1) 在平衡树的查找过程中，与给定值进行比较的关键字个数不超过树的深度，这与排序树相同,(2) 含有 n 个结点的AVL树其最大深度与 log2n 同数量级（最大深度 ）；,(3) 由于在 AVL 树上查找时，和关键字比较的次数不超过树的深度，且不再出现蜕变为单支树的情形，因此 AVL 树上查找的时间复杂度是 O(log2n),(4) 因为动态平衡过程仍需花费不少时间，故在实际应用中，是否采用 AVL 树要根据具体情况而定。一般情况下，项结点关键字是随机分布的，并且系统对平均查找长度没有苛求，则使用二叉排序树即可。,第50页,B- 树和 B+ 树,以前所讨论的算法都是内查找算法，被查找的数据都保存在内存中。它们适用于组织较小的、内存中记录的文件。对于较大的、存放在外存储器上的文件，它们就不合适了。,1972年，R.Bayer 和 E.McCreight 提出了一种适用于外查找的树，它是一种平衡的多叉树，其特点是插入、删除时易于平衡，外查找效率高，适用于组织磁盘文件的动态索引结构。这就是 B- 树。,例如：当用平衡二叉树作为磁盘文件的索引组织时，若以结点作为内、外存交换的单位，则查找到需要的关键字之前，平均要对磁盘进行 log2n 次访问，这是很费时间的。,B- 树定义,第51页,B-树 致力于解决实现基于磁盘的检索树时遇到的所有问题：,B- 树和 B+ 树,B- 树定义,(1) B- 树总是高度平衡的，所有叶结点都在同一层；,(2) 更新和检索操作只影响一些磁盘页，因此性能很好；,(3) B- 树把相关的记录放在同一个磁盘页中，从而利用了访问局部性原理；,(4) B- 树保证树中至少有一定比例的结点是满的。这样能够改进空间的利用率，同时在检索和更新期间减少需要的磁盘读取数目。,第52页,定义(B- 树)： 一棵 m 阶的 B- 树，或为空树，或为满足下列特性的 m 叉树：,B- 树定义,(1) 树中每个结点至多有 m 棵子树；,(3) 根结点至少有两棵子树（唯一例外的是只包含一个根结点的 B- 树）；,(4) 所有的叶结点均在同一层，且叶结点不包含任何关键字信息；,(5) 有 j 棵子树的非叶结点恰好包含 j-1 个关键字。,且指针 Ai-1 所指子树中所有结点的关键字均小于 Ki(i=1,2,j) ， Aj 所指子树中所有结点的关键字均大于 Kj；j 为关键字个数（或 j+1 为子树个数）。,(2) 除根结点和叶结点外，其它每个结点至少有 棵子树；,第53页,b,c,d,e,f,g,h,t,图9.14 一棵4阶的 B- 树,在 B- 树中每个结点的关键字从小到大排列。因为叶结点不包含关键字，故可把叶结点看成在树中实际上并不存在的外部结点。叶结点的总数正好等于树中所包含的关键字总个数加1。,B- 树定义,a,F,F,F,F,F,F,F,F,F,F,F,F,示例1,第54页,示例2 下图为一棵6阶的 B- 树（简化形式）,375,045 112 236,392 490 560 631 670,注. m=6。每个非叶结点的子树个数在6/2(=3)和6之间， 从而它们所包含的关键字个数可以不等，取2,3,4或5。,008 040,052 110,135 142 212,237 240 279,378 381 388,393 396 400 435 471,492 502 553,562 587 626,633 652 666,671 673 678,B- 树定义,第55页,B- 树的查找,在 B- 树上进行查找的过程和二叉树的查找类似。 在 B- 树上查找给定的关键字的方法是：,首先取根结点，在根结点所包含的关键字 K1,K2,Kj 中查找给定值，若找到等于给定值的关键字，则查找成功;,否则，可以确定要查的关键字是在某个 Ki 和 Ki+1 之间（因为在结点内部的关键字是排序的），故可取 Ai 所指向的结点继续查找 如此重复下去，直至找到，或指针 Ai 为 NULL 时，查找失败。,可见，在 B- 树上进行查找的过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程。,第56页,示例3： 承示例1，在一棵4阶 B- 树上查找,图9.14 一棵4阶的 B- 树,b,c,d,e,f,g,h,t,a,F,F,F,F,F,F,F,F,F,F,B- 树的查找,47,(1) 查找关键字47,(2) 查找关键字23,查找成功,F,F,查找失败,在 B- 树中查找与所给关键字相等的结点的算法思想： (1) 在 B- 树中根据关键字找结点； (2) 在结点中找关键字。,第57页,B- 树结点类型说明,#define m 3 typedef struct BTNode int keynum; struct BTNode *parent; /父结点指针 KeyType keym+1; /关键字，m 个(0未用) struct BTNode *ptrm+1; /指向子树的指针，m+1个 Record *recptrm+1; /指向记录的指针(0未用) BTNode, *BTree; typedef struct BTNode *pt; int i; /关键字序号 int tag; /0-查找不成功，1-查找成功 Result;,B- 树的查找,第58页,Result SearchBTree( Btree T, KeyType K) /*在根结点指针为 T 的 m阶 B- 树上查找关键字 K，返回记录 (pt,i,tag)。若查找成功，则特征位 tag=1，等于 K 的关键字即为指针 pt 所指结点的第 i个关键字；若查找不成功，则特征位 tag=0，等于 K 的关键字应插入到指针 pt 所指结点第 i 个和第 i+1 个关键字之间*/ p = T; q = NULL; found = false; i = 0; /初始化，p 指向待查结点，q 指向 p 的双亲结点,while( pNULL /while if( found ) return(p,i,1) /查找成功 else return(q,i,0) /查找不成功，返回插入位置信息 /算法 9.7,第59页,性能分析：通常 B- 树 存储在外存上。在 B- 树中查找结点涉及内、外存交换，而结点中查找关键字是在内存进行的，后者可采用折半查找，效率很高。因此，B- 树的查找效率主要取决于如何在树中找结点，即需与磁盘交换，而这一操作又与 B- 树的层次数（深度）有关，所以，算法的效率取决于树的高度，（最大层次数）。,B- 树的查找分析,第60页,假设 B- 树有 N 个关键字，因此共有 N+1 个树叶，且设树叶均在 l+1 层。 根据 B- 树定义， 第一层有一个结点（根）， 第二层至少有2个结点， 第三层至少有 个结点， 第 l+1 层至少有 个结点。 由于叶结点 数为 N+1，因此，有 即,B- 树的查找分析,2*（ ）,2*（ ）l-1,l,这意味着若 N=1,999,998, m=199，则 l 至多等于4。显然其查找效率非常之高。,第61页,B- 树的插入,B- 树的生成也是从空树起，逐个插入关键字而得。但 B- 树的插入与一般树的插入有所不同。一般树的插入是将树往下延伸，而 B- 树的插入却是往上“蔓延”的。,对于叶结点处于第 L+1 层的 B- 树，插入的关键字总是进入第 L 层的结点。,在 m阶B- 树中插入一个关键字：,由于 m阶B- 树结点中的关键字个数必须 ， 因此，每次插入一个关键字不是在树中添加一个叶结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过 m-1，则插入完成； 否则（关键字个数等于m）要对结点进行 “分裂”。,第62页,B- 树的插入,怎样对结点进行 “分裂”？,? m-f =,把关键字Kf+1和指针p一起插入到P的双亲结点中，当然这有可能会导致双亲结点的“分裂”，甚至产生连锁反应。,第63页,示例4：下列图示给出了一棵3阶 B- 树依次插入关键字30，26，85和7时，整个 B- 树和结点的变化过程,(a) 一棵 2-3 树,45,24,53 90,3 12,61 70,37,50,100,b,c,d,f,g,h,e,bt,B- 树的插入,a,(1) 插入关键字30：首先查找插入位置(37之前)；,45,24,37,进行插入，并检查,第64页,45,24,53 90,3 12,61 70,30 37,50,100,b,c,d,f,g,h,e,bt,插入26之后，结点d需分裂，30向上插入到双亲结点中。,B- 树的插入,a,(2) 继续插入关键字26：首先查找插入位置(30之前)；,45,24,进行插入，并检查插入后结点关键字数目大于2。,c,30 37,第65页,插入85之后，结点g需分裂，70向上插入到双亲结点e中。,B- 树的插入,(3) 继续插入关键字85：首先查找插入位置(70之后)；,进行插入，并检查插入后结点关键字数目大于2。,c,bt,45,24 30,53 90,3 12,61 70,50,100,b,d,f,g,h,e,a,26,37,d,45,53 90,61 70,第66页,插入85之后，结点g需分裂，70向上插入到双亲结点e中。,B- 树的插入,c,bt,45,24 30,53 90,3 12,50,100,b,d,f,g,h,e,a,26,37,d,61 70 85,e分裂,70上插,第67页,B- 树的插入,bt,45 70,24 30,3 12,50,100,b,d,f,g,h,e,a,26,37,d,61,c,85,g,c分裂,7上插,e,(4) 继续插入关键字7：首先查找插入位置(3之后)；,进行插入，并检查插入后结点关键字数目大于2。,53,90,第68页,B- 树的插入,bt,45 70,7 24 30,3,50,100,b,d,f,g,h,e,a,26,37,d,61,c,85,g,e,c分裂，7上插,53,90,12,c,a分裂，45上插,第69页,B- 树的插入,a分裂，45上插,24 45 70,3,50,100,b,d,f,g,h,e,26,37,d,61,c,85,g,e,53,90,12,c,7,30,bt,a,第70页,Status InsertBtree( BTree /将 x 和 ap 分别插入在 q-keyi+1 和 q-ptri+1 的位置上 if( q-keynum m ) finished = true /插入完成 else /分裂结点 q,S = ; split(q , ap); /生成新结点， 且将 q-keys+1m 和 q-ptrsm 移至结点 ap中 x = q-keys; /组成一对新的插入信息 q = q-parent; if( qNULL ) i = Search( q, x ) /继续在双亲结点 q中查找 x 的插入位置 ; /else ; /while,在 B- 树一插入关键字的算法描述,第71页,续上页 if( !finished ) Newroot(t,t,x,ap) /生成新的含信息(t,x,ap)的根 t，其中 t 和 ap 为指向其子树根的指针 / 算法 9.8,在 B- 树一插入关键字的算法描述,第72页,删除操作过程与插入操作相类似，但要稍复杂些。若欲在 B- 树上删除一个关键字，则首先应找到该关键字所在结点，并从中删除之。若该结点为最下层的非终端结点，且其中的关键字数目不小于 ，则删除完成；,B- 树的删除,否则要进行“合并”结点的操作。这里可能发生多种情况，甚至合并会一直往上蔓延，传到根结点。更有甚者，还有可能发生根结点与它两个孩子进行合并，形成新的根结点，从而使整棵 B- 树减少了一层。,第73页,B- 树的删除,删除关键字Ki和相应指针Ai,则需将其右兄弟结点中的最小（或最大）的关键字上移至双亲结点， 而将双亲结点中小于该上移关键字的关键字下移至被删关键字所在 结点。如删除以下关键字50,70,53 61 90,61 90,53,第74页,B- 树的删除,不妨设右兄弟结点存在，且由双亲结点中的Ai指针所指，则在删除关键字后，把剩余的关键字和指针，加上双亲结点中的关键字 Ki一起，合并至于Ai指针所指兄弟结点中。,45,24,3 12,37,100,b,d,f,g,h,e,bt,a,c,70,61 90,53,例如：删除关键字53,第75页,B+ 树,B+ 树是 B- 树的一种变型树。 一棵 m 阶的 B+ 树和 m 阶的 B- 树的差异在于 (1) 有 n 棵子树的结点中含有 n 个关键字 (nm)；B- 树为 n-1 个 (2) 所有的叶结点包含了全部关键字的信息以及指向包含这些关键字的信息以及指向包含这些关键字记录的指针，叶结点本身依关键字由小到大顺序链接，从而既可从根开始随机查找，又可从叶结点顺序查找； (3) 所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。 示例8 下图为一棵3阶的 B+ 树,59 97,72 97,63 72,51 59,10 15,15 44 59,21 37 44,85 91 97,root,sqt,图9.18 一棵3阶的 B+ 树,第76页,说明：,(1) B+ 树与 B- 树的相同之处在于 a. 根结点（非叶）最少有两棵子树 b. 所有非终端结点（除根外）至少有 棵子树； c. 叶结点均在同一层次 (2) B+ 树的查找、插入、删除等操作与 B- 树类似。需强调的是，B+ 树查找时，若非终端结点上的关键字等于给定值时，并不终止，而是继续向下直到叶结点。因此，对 B+ 树，不管查找成功与否，每次查找都是走上了一条从根到叶结点的路径； (3) 通常在 B+ 树上有两个头指针，一个指向根结点。因此，可以对 B+ 树进行两种查找操作。,B+ 树,第77页,哈希表（散列表）,前面所介绍的查找方法是建立在“比较”的基础之上进行的，目标都是尽量减少“比较”的次数。,更希望不经过任何比较，一次存取就能得到所查记录。,哈希函数、哈希表,提出了哈希表。,思想： 通过在关键字和它的记录存贮位置之间建立一个确定的对应关系 f ，使每个关键字和结构中一个唯一的有效位置相对应。因而在查找时，只要根据这个对应关系 f 找到给定值 k 的映象 f (k)，若结构中存在关键字和 k 相等的记录，则必定在 f(k) 的存贮位置上。,这个对应关系f为哈希函数，根据这种思想建立的表称为哈希表。,第78页,通常对于一个给定的关键字集合，设计一个函数。这个函数将关键字映射到M个连续的整数集合中，且把这些整数解释成向量V元素的标号，这个向量称为关键字集合的Hash向量，向量的长为M。,哈希函数、哈希表,例如 假设每个标记符由2个字母构成，并将标识符视为关键字，则这种关键字共有2626=676个，若接收这些关键字就会要M=676个的存贮向量，按字典序把26个字母赋予代码126， 则编码为： aa, ab, , az, ba, , bz, , zz （标识符） 1 ，2, , 26, 27, , 52, , 676 （编码）,显然可定义函数 此函数可将标识映射到一个长为676的向量中。,第79页,哈希函数、哈希表,但在实际应用中，