零基础学数据结构查找.pptx
11.1 查找的基本概念 关键字(key)与主关键字(primary key)：数据元素中某个数据项的值。如果该关键字可以将所有的数据元素区别开来，也就是说可以唯一标识一个数据元素，则该关键字被称为主关键字，否则被称为次关键字(secondary key)。特别地，如果数据元素只有一个数据项，则数据元素的值即是关键字。查找表(search table)：是由同一种类型的数据元素构成的集合。查找表中的数据元素是完全松散的，数据元素之间没有直接的联系。第1页/共77页11.1 查找的基本概念 查找(searching)：根据关键字在特定的查找表中找到一个与给定关键字相同的数据元素的操作。如果在表中找到相应的数据元素，则称查找是成功的，否则，称查找是失败的。例如，表11.1中为教师基本情况，如果要查找职称为“教授”并且性别是“男”的教师，则可以先利用职称将记录定位，然后在性别中查找为“男”的记录。表11.1 教师基本情况信息表第2页/共77页11.1 查找的基本概念 对查找表经常进行的操作有（1）查询某个“特定的”的数据元素是否在查找表中；（2）检索某个“特定的”数据元素的各种属性；（3）在查找表中插入一个数据元素；（4）从查找表中删除某个数据元素。若对查找表只进行前两种查找操作，则称此类查找表为静态查找表（static search table），相应的查找方法称为静态查找（static search）。若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找为动态查找表（dynamic search table），相应的查找方法为动态查找（dynamic search）。第3页/共77页11.1 查找的基本概念 平均查找长度(average search length)：是指在查找过程中，需要比较关键字的平均次数，它是衡量查找算法的效率标准。平均查找长度的数学定义为：ASL=。其中，Pi表示查找表中第i个数据元素的概率，Ci表示在找到第i个数据元素时，与关键字比较的次数。第4页/共77页11.2 静态查找 顺序表的查找 顺序表的存储结构如下。#define MaxSize 100 typedef struct KeyType key;DataType;typedef struct DataType listMaxSize;int length;SSTable;第5页/共77页11.2 静态查找顺序表的查找算法描述如下：int SeqSearch(SSTable S,DataType x)/*在顺序表中查找关键字为x的元素，如果找到返回该元素在表中的位置，否则返回0*/int i=0;while(ix.key)/*从有序顺序表的最后一个元素开始向前比较*/i-;return i;第10页/共77页11.2 静态查找 设表中的元素个数为n且要查找的数据元素在表中出现的概率相等即为，则有序顺序表在查找成功时的平均查找长度为：即查找成功时平均比较次数约为表长的一半。在查找失败时，即要查找的元素没有在表中，则有序顺序表在查找失败时的平均查找长度为：第11页/共77页11.2 静态查找 2折半查找 折半查找（binary search）又称为二分查找，这种查找算法要求待查找的元素序列必须是从小到大排列的有序序列。折半查找的算法描述如下：将待查找元素与表中间的元素进行比较，如果两者相等，则说明查找成功；否则利用中间位置将表分成两部分，如果待查找元素小于中间位置的元素值，则继续与前一个子表的中间位置元素进行比较；否则与后一个子表的中间位置元素进行比较。不断重复以上操作，直到找到与待查找元素相等的元素，表明查找成功。如果子表变为空表，表明查找失败。第12页/共77页11.2 静态查找 一个有序顺序表为（7,15,22,29,41,55,67,78,81,99），如果要查找元素67。利用折半查找算法思想，折半查找的过程如图11.1所示。第13页/共77页11.2 静态查找折半查找的算法描述如下。int BinarySearch(SSTable S,DataType x)/*在有序顺序表中折半查找关键字为x的元素，如果找到返回该元素在表中的位置，否则返回0*/int low,high,mid;low=0,high=S.length-1;/*设置待查找元素范围的下界和上界*/while(low=high)mid=(low+high)/2;if(S.listmid.key=x.key)/*如果找到元素，则返回该元素所在的位置*/return mid+1;else if(S.listmid.keyx.key)/*如果mid所指示的元素大于关键字，则修改high指针*/high=mid-1;return 0;第14页/共77页11.2 静态查找 折半查找过程可以用一个判定树来描述。例如，用折半查找算法查找值为56的元素时，需要比较4次。从图11.1中可以看出，查找元素41需要比较1次，查找元素78需要比较2次，查找元素55需要比较3次，查找元素67需要比较4次。整个查找过程可以用二叉判定树来表示，如图11.2所示。第15页/共77页11.2 静态查找 对于具有n个结点的有序表（恰好构成一个深度为h的满二叉树）来说，有h=，二叉树中第i层的结点个数是2i-1。假设表中每个元素的查找概率相等，即Pi=，则有序表在折半查找成功时的平均查找长度为：查找失败时，有序表的折半查找失败时的平均查找长度为：第16页/共77页11.2 静态查找索引顺序表的查找 当顺序表中的数据量非常大时，无论使用前述哪种查找算法都需要很长的时间，此时提高查找效率的一个常用方法就是在顺序表中建立索引表。建立索引表的方法是将顺序表分为几个单元，然后分别为这几个单元建立一个索引，我们把原来的顺序表称为主表，提供索引的表称为索引表。索引表中只存放主表中要查找的数据元素的主关键字和索引信息。图11.3是一个主表和一个按关键字建立的索引表结构图。第17页/共77页11.2 静态查找 我们把这样的表称为索引顺序表，要使查找效率高，索引表必须有序，但主表中的元素不一定要按关键字有序排列。索引顺序表的查找也称分块查找。因索引表中的元素的关键字是有序的，故在确定元素所在主表的单元时，既可采用顺序查找法也可采用折半查找法，但对于主表，只能采用顺序法查找。索引顺序表的平均查找长度可以表示为：ASL=Lindex+Lunit。其中，Lindex是索引表的平均查找长度，Lunit是单元中元素的平均查找长度。假设主表中的元素个数为n，并将该主表平均分为b个单元，且每个单元有s个元素，即b=n/s。如果表中的元素查找概率相等，则每个单元中元素的查找概率就是1/s，主表中每个单元的查找概率是1/b。如果用顺序查找法查找索引表中的元素，则索引顺序表查找成功时的平均查找长度为：ASL成功=。第18页/共77页11.2 静态查找 当然，如果主表中每个单元中的元素个数是不相等的时候，就需要在索引表中增加一项，即用来存储主表中每个单元元素的个数。将这种利用索引表示的顺序表称为不等长索引顺序表。例如，一个不等长的索引表如图11.4所示。第19页/共77页11.2 静态查找静态查找应用举例 【例11_1】给定一组元素序列，利用顺序表查找、有序顺序表查找和索引顺序表查找值x的元素。【分析】主要考察静态查找的3种算法思想。第20页/共77页11.3 动态查找 二叉排序树 二叉排序树也称为二叉查找树。二叉排序树的查找是一种常用的动态查找方法。下面介绍在二叉排序树中进行查找、二叉排序树的插入和删除结点。1什么是二叉排序树 所谓二叉排序树（binary sort tree），或者是一棵空二叉树，或者二叉树具有以下性质：（1）如果二叉树的左子树不为空，则左子树上的每一个结点的值均小于其对应根结点的值；（2）如果二叉树的右子树不为空，则右子树上的每一个结点的值均大于其对应根结点的值；（3）该二叉树的左子树和右子树也满足性质（1）和（2），即左子树和右子树也是一棵二叉排序树。第21页/共77页11.3 动态查找 显然，这是一个递归的二叉排序树定义。例如，一棵二叉排序树如图11.6所示。从图11.6中不难看出，每个结点元素值都大于其所有左子树结点元素的值，且小于其所有右子树中结点元素值。例如，80大于左孩子的结点元素值70，小于右孩子结点元素值87。第22页/共77页11.3 动态查找 2查找算法 二叉排序树中每个结点的值都大于其所有左子树结点的值，而小于其所有右子树中结点的值。如果要查找与二叉树中某个关键字相等的结点，可以从根结点开始，与给定的关键字比较，如果相等，则查找成功。如果关键字小于根结点的值，则在其左子树中查找。如果给定的关键字大于根结点的值，则在其右子树中查找。采用链式存储结构的二叉排序树的类型定义如下：typedef struct Node DataType data;struct Node*lchild,*rchild;BiTreeNode,*BiTree;第23页/共77页11.3 动态查找二叉排序树的查找算法描述如下。BiTree BSTSearch(BiTree T,DataType x)/*二叉排序树的查找，如果找到元素x，则返回指向结点的指针，否则返回NULL*/BiTreeNode*p;if(T!=NULL)/*如果二叉排序树不为空*/p=T;while(p!=NULL)if(p-data.key=x.key)/*找到则返回指向该结点的指针*/return p;else if(x.keydata.key)/*如果关键字小于p指向的结点的值，则在左子树中查找*/p=p-lchild;else p=p-rchild;/*如果关键字大于p指向的结点的值，则在右子树中查找*/return NULL;第24页/共77页11.3 动态查找 假设存在一棵二叉排序树，在该二叉排序树中查找元素75的过程如图11.7所示。第25页/共77页11.3 动态查找 在二叉排序树的查找过程中，查找某个结点的过程正好是走了从根结点到要查找结点的路径，其比较的次数正好是路径长度+1，这类似于折半查找，与折半查找不同的是由n个结点构成的判定树是唯一的，而由n个结点构成的二叉排序树则不唯一。例如，对于图11.8所示的两棵二叉排序树，其元素的关键字序列分别是66，35，81，23，47，69，92和23，35，47，66，69，81，92。第26页/共77页11.3 动态查找3 3二叉排序树的插入二叉排序树的插入二叉排序树的结构不是一次生成的，而是在查找的过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。因此，可以说二叉排序树的插入操作过程其实就是二叉排序树的建立过程。在算法的实现过程中，需要设置一个指向下一个要访问结点的双亲结点指针parent，记下前驱结点的位置，以便在查找失败时进行插入操作。第27页/共77页11.3 动态查找二叉排序树的插入操作算法描述如下。int BSTInsert(BiTree*T,DataType x)/*二叉排序树的插入操作，如果树中不存在元素x，则将x插入到正确的位置并返回1，否则返回0*/BiTreeNode*p,*cur,*parent=NULL;cur=*T;while(cur!=NULL)if(cur-data.key=x.key)/*二叉树中存在元素为x的结点，则返回0*/return 0;parent=cur;/*parent指向cur的前驱结点*/if(x.keydata.key)/*如果关键字小于p指向的结点的值，则在左子树中查找*/cur=cur-lchild;elsecur=cur-rchild;/*如果关键字大于p指向的结点的值，则在右子树中查找*/第28页/共77页11.3 动态查找 p=(BiTreeNode*)malloc(sizeof(BiTreeNode);/*生成结点*/if(!p)exit(-1);p-data=x;p-lchild=NULL;p-rchild=NULL;if(!parent)/*如果二叉树为空，则第一结点成为根结点*/*T=p;else if(x.keydata.key)/*如果关键字小于parent指向的结点，则将x成为parent的左孩子*/parent-lchild=p;else/*如果关键字大于parent指向的结点，则将x成为parent的右孩子*/parent-rchild=p;return 1;第29页/共77页假设一个元素序列55,43,66,88,18,80,33,21,72，根据二叉排序树的插入算法思想，对应的二叉排序树插入过程如图11.9所示。11.3 动态查找第30页/共77页11.3 动态查找 4二叉排序树的删除 对于一般的二叉树来说，删去树中的一个结点是没有意义的。因为它将使以被删结点为根的子树变成森林，破坏了整棵树的结构。然而对于二叉树来说，删除树中的一个结点其实是删除有序序列的一个记录，只要在删除某个结点之后依旧保持二叉树的特性即可。那么如何在二叉树排序树中删除一个结点呢？假设要删除的结点由指针s指示，指针p指向s的双亲结点，设s为f的左孩子结点。删除一个结点分为3种情况讨论。二叉排序树的各种删除情形如图11.10所示。第31页/共77页11.3 动态查找（1）如果s指向的结点为叶子结点，其左子树和右子树为空，删除叶子结点不会影响到树的结构特性，因此只需要修改p的指针即可。（2）如果s指向的结点只有左子树或只有右子树，在删除了结点*s后，只需要将s的左子树sL或右子树sR作为f的左孩子即p-lchild=s-lchild或p-lchid=s-rchild。第32页/共77页（3）若s存在左子树和右子树，在删除结点T之前，二叉排序树的中序序列为QLQXLXYLYTTRP，因此，在删除了结点S之后，使该二叉树仍然保持原来的性质不变的调整方法有两种：（1）使结点T的左子树作为结点P的左子树，结点T的右子树作为结点Y的右子树。（2）使结点T的直接前驱取代结点T，并删除T的直接前驱结点Y，然后令结点Y原来的左子树作为结点X的右子树。如图11.10所示。11.3 动态查找第33页/共77页二叉排序树的删除操作算法描述如下。int BSTDelete(BiTree*T,DataType x)/*在二叉排序树T中存在值为x的数据元素时，删除该数据元素结点，并返回1，否则返回0*/if(!*T)/*如果不存在值为x的数据元素，则返回0*/return 0;elseif(x.key=(*T)-data.key)/*如果找到值为x的数据元素，则删除该结点*/DeleteNode(T);else if(*T)-data.keyx.key)/*如果当前元素值大于x的值，则在该结点的左子树中查找并删除之*/BSTDelete(&(*T)-lchild,x);else/*如果当前元素值小于x的值，则在该结点的右子树中查找并删除之*/BSTDelete(&(*T)-rchild,x);return 1;11.3 动态查找第34页/共77页void DeleteNode(BiTree*s)/*从二叉排序树中删除结点s，并使该二叉排序树性质不变*/BiTree q,x,y;if(!(*s)-rchild)/*如果s的右子树为空，重接左子树*/q=*s;*s=(*s)-lchild;free(q);else if(!(*s)-lchild)/*如果s的左子树为空，重接右子树*/q=*s;*s=(*s)-rchild;free(q);11.3 动态查找第35页/共77页11.3 动态查找else/*如果s的左、右子树都存在，则使s的直接前驱结点代替s，并使其直接前驱结点的左子树成为其双亲结点的右子树结点*/x=*s;y=(*s)-lchild;while(y-rchild)/*查找s的直接前驱结点，y为s的直接前驱结点，x为y的双亲结点*/x=y;y=y-rchild;(*s)-data=y-data;/*结点s被y取代*/if(x!=*s)/*如果结点s的左孩子结点存在右子树*/x-rchild=y-lchild;/*使y的左子树成为x的右子树*/else/*如果结点s的左孩子结点不存在右子树*/x-lchild=y-lchild;/*使y的左子树成为x的左子树*/free(y);第36页/共77页 5二叉排序树应用举例 【例11_2】编写算法，利用二叉树的插入算法创建一棵二叉排序树树，然后输入一个元素，查找该元素是否存在，最后输出这棵树的中序序列。11.3 动态查找第37页/共77页平衡二叉树 若二叉排序树的深度为n，在最坏的情况下平均查找长度为n。因此，为了减小二叉排序树的查找次数，需要对二叉树排序树进行平衡化处理，平衡化处理得到的二叉树称为平衡二叉树。1什么是平衡二叉树 平衡二叉树（balanced binary tree）又称为AVL树，它或者是一棵空树，或者是具有以下性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。11.3 动态查找第38页/共77页若将二叉树中结点的平衡因子BF（balance factor）定义为结点的左子树的深度减去右子树的深度，则平衡二叉树中每个结点的平衡因子只可能是-1、0和1。如图11.12所示为两棵平衡二叉树，结点的右边表示平衡因子，因为该二叉树既是二叉排序树又是平衡树，因此，该二叉树称为平衡二叉排序树。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。如图11.13所示为两棵不平衡的二叉树。11.3 动态查找第39页/共77页 2二叉排序树的平衡处理 在二叉排序树中插入一个新结点后，如何保证该二叉树是平衡二叉排序树呢？设有一个关键字序列7，36，45，78，65，依照此关键字序列建立二叉排序树，且使该二叉排序树是平衡二叉排序树。初始时，二叉树为空树，因此是平衡二叉树。插入结点7和36后，该二叉树依然是平衡的，结点7和结点36的平衡因子分别为-1和0。当插入结点45后，结点7的平衡因子变为-2，二叉树变为不平衡，这需要进行调整。以结点36为轴进行逆时针旋转，将二叉树变为以36为根，各个结点的平衡因子都为0，二叉树恢复了平衡。11.3 动态查找第40页/共77页 继续插入结点78，二叉树仍然为平衡的。当插入结点65后，该二叉树又失去了平衡，为了保持二叉排序树的性质，又要保证该二叉树是平衡的，需要进行两次调整：先以结点78为轴进行顺时针旋转，然后以结点65为轴进行逆时针旋转。构造平衡二叉排序树的过程如图11.14所示。11.3 动态查找第41页/共77页 通过上述平衡化处理，我们得出一个结论：通过让插入点最近的祖先结点恢复平衡，从而使上一层祖先结点恢复平衡。因此，为了使二叉排序树恢复平衡，需要从离插入点最近的结点开始调整。平衡化二叉排序树可分为以下4种情形。（1）LL型。LL型是指在离插入点最近的失衡结点的左子树的左子树中插入结点，导致二叉排序树失去平衡。如图11.15所示。距离插入点最近的失衡结点为A，插入新结点X后，结点A的平衡因子由1变为2，该二叉排序树失去平衡。为了使二叉树恢复平衡且保持二叉排序树的性质不变，可以使结点A作为结点B的右子树，结点B的右子树作为结点A的左子树。这样就恢复了该二叉排序树的平衡，这相当于以结点B为轴，对结点A进行顺时针旋转。11.3 动态查找第42页/共77页 为平衡二叉排序树的每个结点增加一个域bf，用来表示对应结点的平衡因子。平衡二叉排序树的类型如下：typedef struct BSTNode/*平衡二叉排序树的类型定义*/DataType data;int bf;/*结点的平衡因子*/struct BSTNode*lchild,*rchild;/*左、右孩子指针*/BSTNode,*BSTree;11.3 动态查找第43页/共77页 对LL型二叉排序树的平衡化处理代码如下：BSTree b;b=p-lchild;/*lc指向p的左子树的根结点*/p-lchild=b-rchild;/*将lc的右子树作为p的左子树*/b-rchild=p;p-bf=b-bf=0;/*修改平衡因子*/11.3 动态查找第44页/共77页 （2）LR型。LR型是指在离插入点最近的失衡结点的左子树的右子树中插入结点，导致二叉排序树失去平衡。如图11.16所示。11.3 动态查找第45页/共77页11.3 动态查找 （3）RL型。RL型是指在离插入点最近的失衡结点的右子树的左子树中插入结点，导致二叉排序树失去平衡。如图11.17所示。第46页/共77页11.3 动态查找（4）RR型。RR型是指在离插入点最近的失衡结点的右子树的右子树中插入结点，导致二叉排序树失去平衡。如图11.18所示。第47页/共77页11.3 动态查找 综上以上4种情形，在平衡二叉排序树中插入一个结点e后，若仍需保持二叉排序树平衡的算法描述如下：（1）若平衡二叉排序树是空树，则插入的结点e作为根结点，并使该树的深度增1；（2）若二叉树中已存在与结点e的关键字相等的结点，则无须插入；（3）若结点e的关键字小于要插入位置的结点的关键字，则将e插入到该结点的左子树位置，并使该结点的左子树高度增1，同时修改该结点的平衡因子；如果该结点的平衡因子绝对值大于1，则需要进行平衡化处理；（4）若结点e的关键字大于要插入位置的结点的关键字，则将e插入到该结点的右子树位置，并将该结点的右子树高度增1，同时修改该结点的平衡因子；如果该结点的平衡因子绝对值大于1，则进行平衡化处理。第48页/共77页11.3 动态查找 1LL型的平衡处理 对于LL型的失去平衡的情形，只需要对离插入点最近的失衡结点进行一次顺时针旋转处理即可。其算法实现如下。void RightRotate(BSTree*p)/*对以*p为根的二叉排序树进行右旋，处理之后p指向新的根结点，即旋转处理之前的左子树的根结点*/BSTree lc;lc=(*p)-lchild;/*lc指向p的左子树的根结点*/(*p)-lchild=lc-rchild;/*将lc的右子树作为p的左子树*/lc-rchild=*p;(*p)-bf=lc-bf=0;*p=lc;/*p指向新的根结点*/第49页/共77页11.3 动态查找 2LR型的平衡处理 对于LR型的失去平衡的情形，需要进行两次旋转处理：先进行一次逆时针旋转，然后再进行一次顺时针旋转处理。其算法实现如下。第50页/共77页11.3 动态查找 3RL型的平衡处理 对于RL型的失去平衡的情形，需要进行两次旋转处理：先进行一次顺时针旋转，然后再进行一次逆时针旋转处理。其算法实现如下。第51页/共77页11.3 动态查找4RR型的平衡处理对于RR型的失去平衡的情形，只需要对离插入点最近的失衡结点进行一次逆时针旋转处理即可。算法实现如下。void LeftRotate(BSTree*p)/*对以*p为根的二叉排序树进行左旋，处理之后p指向新的根结点，即旋转处理之前的右子树的根结点*/BSTree rc;rc=(*p)-rchild;/*rc指向p的右子树的根结点*/(*p)-rchild=rc-lchild;/*将rc的左子树作为p的右子树*/rc-lchild=*p;*p=rc;/*p指向新的根结点*/第52页/共77页11.4 B-树与B+树 树 与二叉排序树类似，B-树是一种特殊的m叉动态查找树。下面介绍B-树的结构与查找算法。1什么是B-树 B-是一种平衡的多路查找树，也称为m路（叉）查找树，它在文件系统中很有用。一棵m路（阶）B-树或者是一棵空树，或者是满足以下性质的m叉树：（1）任何一个结点最多有m棵子树；（2）或者是根结点或者是叶子结点，或者至少有两棵子树；（3）除根结点外，所有非终端结点至少有棵子树；（4）所有的非终端结点的结构如下：第53页/共77页11.4 B-树与B+树 其中，n为结点中关键字的个数，-1nm-1，Pi为指向子树根结点的指针，并且Pi指向子树的每个结点关键字都小于Ki+1(i=0,1,n-1)。（5）所有叶子结点处于同一层次上，且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在）。例如，一棵深度为4的4阶的B-树如图11.19所示。第54页/共77页11.4 B-树与B+树 2B-树的查找 B-树的查找其实是对二叉排序树查找的扩展，与二叉排序树不同的地方是，B-树中每个结点有不止一棵子树。在B-树中查找某个结点时，需要先判断要查找的结点在哪棵子树上，然后在结点中逐个查找目标结点。B-树的类型描述如下：#define m 4/*B-树的阶数*/typedef struct BTNode/*B-树类型定义*/int keynum;/*每个结点中的关键字个数*/struct BTNode*parent;/*指向双亲结点*/KeyType datam+1;/*结点中关键字信息*/struct BTNode*ptrm+1;/*指针向量*/BTNode,*BTree;第55页/共77页11.4 B-树与B+树 3B-树的插入操作 在B-树上插入结点与在二叉树上插入结点类似，都是插入前后，保证B-树仍然是一棵排序树，即结点左子树中每个结点的关键字小于根结点的关键字，右子树结点的关键字大于根结点的关键字。但由于B-树结点中的关键字个数必须-1，因此每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插入完成，否则对该结点进行分裂。第56页/共77页11.4 B-树与B+树 例如，图11.20为一棵3阶的B-树（省略了叶子结点），当给定一棵B-树的阶之后，就确定了这棵树的最少子树个数为和最多子树个数，确定了每个结点要求最少1个关键字，最多2个关键字。假设在该B-树中依次插入关键字53、22、85和59。插入关键字53：。第57页/共77页11.4 B-树与B+树插入关键字22：插入关键字85：第58页/共77页11.4 B-树与B+树 此时，结点C的关键字个数大于2且C的子树大于3，因此，需要将结点C进行分裂，并对C的子树进行重新组合。仍将中间的关键字即82上升到双亲结点A中，关键字77保留在C中，关键字86被插入到新结点C中，结点A的P1指针指向结点C，结点A的P2指针指向结点C。结点C的分裂过程如图11.24所示。插入关键字59：第59页/共77页11.4 B-树与B+树 此时，结点E中的关键字个数大于2，需要将结点E分裂：把中间的关键字59提升到双亲结点B中，关键字62保留在结点E中，关键字53被插入到新的结点E中，并使结点B的P2指针指向结点E，结点B的P3指针指向结点E。结点E的分裂过程如图11.26所示。结点B被分裂的过程如图11.27所示。第60页/共77页11.4 B-树与B+树 关键字70提升到结点A后，结点A的关键字个数大于2，因此，还需要继续对结点A进行分裂。因结点A是根结点，故需要生成一个新结点R作为根结点，与上面的操作类似，也需要将结点A中位于中间的关键字70插入到R中，关键字51保留在结点A中，关键字82被插入到新结点A中，结点R的P0和P1指针分别指向结点A和A。结点A的分裂过程如图11.28所示。第61页/共77页11.4 B-树与B+树 4B-树的删除操作 B-树的删除操作可分为3种情况：（1）若删除的关键字所在结点的关键字个数大于等于，则仅需将关键字Ki和对应的指针Pi从该结点中删除即可。删除该关键字后，该结点的关键字个数仍满足大于等于-1。例如，图11.29显示了从结点E中删除关键字62的情形。第62页/共77页11.4 B-树与B+树 （2）被删除的关键字所在结点的关键字个数等于-1，而与该结点相邻的的右兄弟（或左兄弟）结点中的关键字个数大于-1，则删除关键字后，需要将其兄弟结点中最小（或最大）的关键字上移至双亲结点中，将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在的结点中。例如，把如图11.29所示的关键字95删除后，需要将关键字82上移至双亲结点C中，并把关键字86下移至结点H中，得到如图11.30所示的B-树。第63页/共77页11.4 B-树与B+树 （3）被删除的关键字所在结点和其相邻的兄弟结点中的关键字个数均等于-1，假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Pi所指，则在删除关键字之后，它所在的结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一起，合并到Pi所指的兄弟结点中。若没有右兄弟结点，则合并至左兄弟结点中。例如，若删除关键字86后，需要把关键字86的左兄弟结点的关键字79与其双亲结点中的关键字82合并到一起，得到如图11.31所示的B-树。第64页/共77页11.4 B-树与B+树树 B+树是B-树的一种变型树。一棵m阶的B+树和m阶的B-树的差异在于：（1）有n棵子树的结点必有n个关键字，即关键字个数与结点的子树个数相等；（2）所有的叶子结点中包含了全部关键字的信息，及指向这些关键字记录的指针，且叶子结点本身依关键字的大小从小到大顺序链接。（3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。第65页/共77页11.5 哈希表 什么是哈希表 如何在查找元素的过程中，不与给定的关键字进行比较，就能确定所查找元素的存放位置。这就需要在元素的关键字与元素的存储位置之间建立起一种对应关系，使得元素的关键字与唯一的存储位置对应。有了这种对应关系，在查找某个元素时，只需要利用这种确定的对应关系，由给定的关键字就可以直接找到该元素。用key表示元素的关键字，f表示对应关系，则f(key)表示元素的存储地址，将这种对应关系f称为哈希函数，利用哈希函数可以建立哈希表。哈希表也称为散列函数。表11.2 哈希表示例第66页/共77页11.5 哈希表哈希函数的构造方法 构造哈希函数的目的主要是使哈希地址尽可能地均匀分布以减少或避免产生冲突、使计算方法尽可能地简便以提高运算效率。哈希函数的构造方法主要有以下几种：1直接定址法 2平方取中法 3折叠法 折叠法是将元素平均分割为若干等份，最后一个部分如果不够可以空缺，然后将这几个等份叠加求和作为哈希地址。这种方法主要用在元素的位数特别多且每一个元素的位数分布大体相当的情况。例如，给定一个元素为23467523072，可以按照3位将该元素分割为几个部分，其折叠计算过程如下：第67页/共77页11.5 哈希表 4除留余数法 通过对元素取余，将得到的余数作为哈希地址。设哈希表长为m，p为小于等于m的最大质数，则哈希函数为h(key)=key%p。例如，在一组元素66,235,332,29,43,58,77,38中，设哈希表长m为14，取p=13则这组元素的哈希地址存储情况如图11.33所示。第68页/共77页11.5 哈希表处理冲突的方法 处理冲突的方法常用的主要有：开放定址法、再哈希法和链地址法。1开放定址法 开放定址法是解决冲突比较常用的方法。开放定址法就是利用哈希表中的空地址存储产生冲突的关键字。当冲突发生时，按照下列公式处理冲突：hi=(h(key)+di)%m,其中i=1,2,m-1 其中，h(key)为哈希函数，m为哈希表长，di为地址增量。地址增量di可以以下三种方法获得：（1）线性探测再散列：在冲突发生时，地址增量di依次取1,2,m-1自然数列，即di=1,2,m-1;（2）二次探测再散列：在冲突发生时，地址增量di依次取自然数的平方，即di=12，-12，22，-22,k2，-k2。（3）伪随机数再散列：在冲突发生时，地址增量di依次取随机数序列。第69页/共77页11.5 哈希表 例如，在长度为14的哈希表中，元素序列37,561,49,86在哈希表中的存放情况如图11.34所示。当要插入元素232时，由哈希函数h(232)=149%13=11，而单元11已经有元素存在，产生冲突，利用线性探测再散列法解决冲突，即h1=(11+1)%14=12，因此把232存放在单元12中，如图11.35所示。当要插入元素50时，第70页/共77页11.5 哈希表 2再哈希法 再哈希法就是在冲突发生时，利用另外一个哈希函数再次求哈希函数的地址，直到冲突不再发生为止.3链地址法 链地址法就是将具有相同散列地址的关键字用一个线性链表存储起来。每个线性链表设置一个头指针指向该链表。链地址法的存储表示类似于图的邻接表表示。在每一个链表中，所有的元素都是按照关键字有序排列。链地址法的主要优点是在哈希表中增加元素和删除元素方便。第71页/共77页11.5 哈希表 例如，一组元素序列66,53,123,77,89,48,274,92,26,230，采用哈希函数h(key)=key%13构造哈希表、用链地址法处理冲突，哈希表如图11.37所示。第72页/共77页11.5 哈希表哈希表应用举例 【例11_3】给定一组元素的关键字hash=78,90,66,70,155,82,123,231，利用除留余数法和线性探测再散列法将元素存储在哈希表中，并查找给定的关键字，求平均查找长度。【分析】主要考察哈希函数的构造方法、冲突解决的办法。算法实现主要包括几个部分：构建哈希表、在哈希表中查找给定的关键字、输出哈希表及求平均查找长度。关键字的个数是8个，假设哈希表的长度m为11，p为11，利用除留余数法求哈希函数即h(key)=key%p，利用线性探测再散列解决冲突即hi=(h(key)+di)，哈希表如图11.38所示。第73页/共77页11.5 哈希表【考研真题】将关键字序列(7,8,30,11,18,9,14)散列存储在散列表中，散列表的存储空间是一个下标从0开始的一维数组，散列函数为H(key)=(key*3)MOD 7，处理冲突采用线性探测再散列法，要求装填因子为0.7。（1）请画出构造的散列表。（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。第74页/共77页11.5 哈希表 【分析】该题目是2010年的考研题目，主要考察哈希表的构造和平均查找长度的概念。根据给出的散列函数H(key)=(key*3)MOD 7和处理冲突方法，构造哈希表如表11.1所示。表11.1 哈希表 （2）查找成功的平均查找长度：ASL成功=(4*1+2*3+1*2)/7=12/7 查找不成功的平均查找长度：ASL不成功 =(3+2+1+2+1+5+4+3+2+1)/10=24/10=12/5第75页/共77页11.6 小结 查找分为两种：静态查找与动态查找。静态查找主要有顺序表、有序顺序表和索引顺序表的查找。其中，索引顺序表的查找是为主表建立一个索引，根据索引确定元素所在的范围，这样可以有效地提高查找的效率。动态查找有二叉排序树、平衡二叉树、B-树和B+树。静态查找中顺序表的平均查找长度为O(n)，折半查找的平均查找长度为O(log2n)。动态查找中的二叉排序树的查找类似于折半查找，其平均查找长度为O(log2n)。哈希表大大减少了与元素的关键字的比较次数。建立哈希表的方法主要有：直接定址法、平方取中法、折叠法和除留余数法等。解决冲突最为常用的方法主要有两个：开放定址法和链地址法。第76页/共77页感谢您的观看！第77页/共77页
