查找的基本概念课件

第第8 8章章 查查 找找查找是数据处理中经常使用的一种重要运算，查找是数据处理中经常使用的一种重要运算，查找算法的优劣对系统运行效率的影响非常查找算法的优劣对系统运行效率的影响非常大。静态查找表、动态查找表和哈希表是主大。静态查找表、动态查找表和哈希表是主要的查找技术。要的查找技术。本章要点本章要点 查找的基本概念；查找的基本概念；几种常见的静态查找表的查找算法；几种常见的静态查找表的查找算法；二叉排序树的创建、查找和删除算法；二叉排序树的创建、查找和删除算法；平衡二叉树的基本操作；平衡二叉树的基本操作；哈希函数的构造方法和哈希表的查找算法。哈希函数的构造方法和哈希表的查找算法。感谢你的观看2019年8月23第8章查找查找是数据处理中经常使用的一种重要运章节安排章节安排8.18.1查找的基本概念查找的基本概念8.28.2静态表的查找静态表的查找8.38.3动态表的查找动态表的查找8.48.4散列表散列表感谢你的观看2019年8月23章节安排8.1查找的基本概念感谢你的观看2019年8月238.18.1查找的基本概念查找的基本概念查找：又称检索，是指在查找表中查找满足一查找：又称检索，是指在查找表中查找满足一定条件的结点或记录。定条件的结点或记录。查找方法：静态查找、动态查找查找方法：静态查找、动态查找 衡量查找算法优劣指标：最大查找长度、平均衡量查找算法优劣指标：最大查找长度、平均查找长度如对查找长度如对n n个记录进行查找时，平均查找长个记录进行查找时，平均查找长度可表示为：度可表示为：感谢你的观看2019年8月238.1查找的基本概念查找：又称检索，是指在查找表中查找满足一8.28.2静态表的查找静态表的查找 静态查找表可分为顺序表、有序表和静态查找表可分为顺序表、有序表和索引顺序表三种。索引顺序表三种。感谢你的观看2019年8月238.2静态表的查找静态查找表可分为顺序表、有序表和索引顺顺序表的查找基本思想是：从顺序表的顺序表的查找基本思想是：从顺序表的一端开始，逐个比较结点的关键字和给一端开始，逐个比较结点的关键字和给定值，若某个结点的关键字与给定值相定值，若某个结点的关键字与给定值相等，则查找成功；若找遍整个顺序表都等，则查找成功；若找遍整个顺序表都不相等，则查找失败。查找成功时，查不相等，则查找失败。查找成功时，查找算法返回找到结点在顺序表中的位置，找算法返回找到结点在顺序表中的位置，失败时返回失败时返回1 1。8.2.18.2.1顺序表的查找顺序表的查找 感谢你的观看2019年8月23顺序表的查找基本思想是：从顺序表的一端开始，逐个比较结点的下面的算法描述了顺序查找过程。下面的算法描述了顺序查找过程。顺序表的存储结构定义如下：顺序表的存储结构定义如下：typedef struct typedef struct KeyType keyKeyType key；/*/*关键字的数据类型关键字的数据类型*/*/DataType DataType；/*/*数据元素的类型数据元素的类型*/*/typedef struct typedef struct DataType *data DataType *data；/*/*顺序表顺序表data*/data*/int len int len；/*/*顺序表的长度顺序表的长度*/*/Stable Stable；感谢你的观看2019年8月23下面的算法描述了顺序查找过程。感谢你的观看2019年8月23【算法【算法8.18.1】顺序表查找算法】顺序表查找算法int Stable_Search(Stable Sint Stable_Search(Stable S，KeyType key)KeyType key)/*/*在顺序表在顺序表S S中查找关键字等于中查找关键字等于keykey的结点的结点*/*/int i;int i;S.data0.key=key S.data0.key=key；/*/*设置哨兵设置哨兵*/*/i=S.len;i=S.len;/*/*设置初始查找位置设置初始查找位置*/*/while(S.datai.key!=key)i-while(S.datai.key!=key)i-；/*/*从后从后往前找往前找*/*/if(i=0)return 1 if(i=0)return 1；/*/*查找失败查找失败*/*/else return ielse return i；/*/*查找成功查找成功*/*/顺序查找的平均查找长度为：顺序查找的平均查找长度为：感谢你的观看2019年8月23【算法8.1】顺序表查找算法感谢你的观看2019年8月23 二二分分法法查查找找（Binary Binary SearchSearch）又又称称为为折折半半查查找找，其其基基本本思思想想是是：首首先先取取查查找找表表中中间间位位置置上上的的结结点点的的关关键键字字与与给给定定值值进进行行比比较较，若若相相等等，则则查查找找成成功功；否否则则，如如果果给给定定值值比比中中间间位位置置上上的的结结点点的的关关键键字字大大，则则把把查查找找区区间间定定为为表表的的后后半半段段，反反之之把把查查找找区区间间定定为为表表的的前前半半段段；然然后后在在前前半半段段或或后后半半段段采采用用同同样样的的方方法法继继续续查查找找，如如此此继继续续，直直到到找找到到关关键键字字等等于于给给定定值值的的结结点点，则则查查找找成成功功；若若出出现现查查找找区区间间的的左左右右边边界界异异常常，则查找失败。则查找失败。8.2.28.2.2有序表的查找有序表的查找 感谢你的观看2019年8月23二分法查找（BinarySearch）又称为折半查找，例：已知有例：已知有1111个关键字的有序表序列如下所示：个关键字的有序表序列如下所示：0202，0808，1515，2323，3131，3737，4242，4949，6767，8383，9191 当给定的当给定的k k值为值为2323和和8383时，折半查找的过程如图时，折半查找的过程如图所示。图中用方括号表示当前的查找区间，用所示。图中用方括号表示当前的查找区间，用“”指向中间位置。指向中间位置。感谢你的观看2019年8月23例：已知有11个关键字的有序表序列如下所示：感谢你的观看20【算法【算法8.28.2】二分法查找非递归算法】二分法查找非递归算法int Binary_Search(Stable Sint Binary_Search(Stable S，KeyType key)KeyType key)int lowint low，midmid，highhigh；low=1low=1；high=S.lenhigh=S.len；while(low=high)mid=(low+high)/2while(low=high)mid=(low+high)/2；if(keyS.datamid.key)if(keyS.datamid.key)low=mid+1if(keyS.datamid.key)low=mid+1；else return mid else return mid；return 1return 1；感谢你的观看2019年8月23【算法8.2】二分法查找非递归算法感谢你的观看2019年8月索引顺序查找又称为分块查找，是顺序查找的一索引顺序查找又称为分块查找，是顺序查找的一种改进方法。在索引顺序查找法中，除表本身以种改进方法。在索引顺序查找法中，除表本身以外，还需要建立一个外，还需要建立一个“索引表索引表”。分块查找的基本思想：把顺序表分成若干块，每分块查找的基本思想：把顺序表分成若干块，每一块中结点的存放是任意的，但是块与块之间必一块中结点的存放是任意的，但是块与块之间必须有序。假设块间按关键字值递增排序，以每块须有序。假设块间按关键字值递增排序，以每块中的最大（小）关键字值建立一个索引表，存放中的最大（小）关键字值建立一个索引表，存放每块的最大（小）关键字值和每块的起始位置。每块的最大（小）关键字值和每块的起始位置。查找时需分两步走，首先在索引表中采用顺序查查找时需分两步走，首先在索引表中采用顺序查找或折半查找算法查找给定值，确定给定值所在找或折半查找算法查找给定值，确定给定值所在的块；然后在所确定的块中顺序查找。的块；然后在所确定的块中顺序查找。8.2.38.2.3索引顺序表的查找索引顺序表的查找 感谢你的观看2019年8月23索引顺序查找又称为分块查找，是顺序查找的一种改进方法。在索 例例8.2 8.2 设有一个顺序表共有设有一个顺序表共有2020个结点，现将它分个结点，现将它分成四块，每块成四块，每块5 5个结点。以每块最大关键字值建立个结点。以每块最大关键字值建立索引表，索引表包含最大关键字值和对应块的起索引表，索引表包含最大关键字值和对应块的起始地址两个域，如图始地址两个域，如图8.28.2所示。试查找关键字值为所示。试查找关键字值为5858的结点。的结点。图图8.2表及索引表结构图表及索引表结构图感谢你的观看2019年8月23例8.2设有一个顺序表共有20个结点，现将它分成四块 分块查找的平均查找长度：分块查找的平均查找长度：ASLASLbsbs=ASLASLb b+ASLASLw wASLASLbsbs表示分块查找的平均查找长度，表示分块查找的平均查找长度，ASLASLb b表表 示查找索引表以确定所在块的平均查找长度，示查找索引表以确定所在块的平均查找长度，ASLASLw w表示在块中查找关键字的平均查找长度。表示在块中查找关键字的平均查找长度。感谢你的观看2019年8月23感谢你的观看2019年8月238.38.3动态表的查找动态表的查找 动态查找表的特点是：表结构本身是在查动态查找表的特点是：表结构本身是在查找过程中动态生成的，即对于给定值找过程中动态生成的，即对于给定值keykey，若表中存在关键字等于若表中存在关键字等于keykey的结点，则查找的结点，则查找成功；否则插入关键字为成功；否则插入关键字为keykey的结点。的结点。感谢你的观看2019年8月238.3动态表的查找动态查找表的特点是：表结构本身是在查二叉排序树又称二叉查找树，它或者是一棵空二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有以下性质的二叉树：树，或者是具有以下性质的二叉树：若任一结点的左子树非空，则左子树中的所有若任一结点的左子树非空，则左子树中的所有结点的值都不大于根结点的值；结点的值都不大于根结点的值；若任一结点的右子树非空，则右子树中的所有若任一结点的右子树非空，则右子树中的所有结点的值都不小于根结点的值。结点的值都不小于根结点的值。8.3.1 8.3.1二叉排序树二叉排序树 感谢你的观看2019年8月23二叉排序树又称二叉查找树，它或者是一棵空8.3.1二叉排 例例如如：图图8.38.3所所示示为为一一棵棵二二叉叉排排序序树树（结结点点内内的的数数为为数数据据元元素素的的关关键键字字）。其其中中序序遍遍历历序序列列为为：1515，5555，6565，7575，7979，9595，100100，120120，200200，230230，240240。图图8.3 8.3 二叉排序树二叉排序树感谢你的观看2019年8月23例如：图8.3所示为一棵二叉排序树（结点内的数为数据元二叉排序树一般采用二叉链表作为存储结二叉排序树一般采用二叉链表作为存储结构，可定义如下：构，可定义如下：typedef struct BSTNodetypedef struct BSTNodeDataTypeDataType datadata；/*/*数据元素字段数据元素字段*/*/struct BSTNodestruct BSTNode*lchild*lchild，*rchild*rchild；/*/*左、右指针字段左、右指针字段*/*/NodeTypeNodeType；感谢你的观看2019年8月23二叉排序树一般采用二叉链表作为存储结构，可定义如下：感谢你的【算法【算法8.38.3】二叉排序树查找算法】二叉排序树查找算法int BST_Search(NodeType*Tint BST_Search(NodeType*T，KeyType KeyType key,NodeType*p,NodeType*q)key,NodeType*p,NodeType*q)if(T)if(T)*p=T*p=T；*q=NULL;*q=NULL;while(*p)while(*p)if(key(*p)-if(key(*p)-data.key)data.key)*q=*p *q=*p ；(*p)=(*p)-rchild(*p)=(*p)-rchild；elseelseif(keydata.key)if(keydata.key)*q=*p *q=*p ；(*p)=(*p)-lchild(*p)=(*p)-lchild；else elsereturn 1return 1；return 0return 0；感谢你的观看2019年8月23【算法8.3】二叉排序树查找算法感谢你的观看2019年8月2 二叉排序树的插入和生成过程如下：二叉排序树的插入和生成过程如下：(1)(1)若二叉排序树为空，则把待插入的结点作为根若二叉排序树为空，则把待插入的结点作为根结点插入到空树中。结点插入到空树中。(2)(2)若二叉排序树非空，则将待插入的结点关键字若二叉排序树非空，则将待插入的结点关键字和根结点的关键字进行比较，若两者相等，表示该和根结点的关键字进行比较，若两者相等，表示该结点已在二叉排序树中，无需插入；若待插入的结结点已在二叉排序树中，无需插入；若待插入的结点关键字小于根结点的关键字，将待插入的结点插点关键字小于根结点的关键字，将待插入的结点插入到根的左子树中，否则插入到右子树中。入到根的左子树中，否则插入到右子树中。(3)(3)子树中的插入过程和树中的插入过程相同，如子树中的插入过程和树中的插入过程相同，如此插入下去，直到把待插入的结点作为叶子插入到此插入下去，直到把待插入的结点作为叶子插入到二叉排序树中。二叉排序树中。感谢你的观看2019年8月23二叉排序树的插入和生成过程如下：感谢你的观看2019年8【算法【算法8.48.4】二叉排序树的插入算法】二叉排序树的插入算法int InsertNode(NodeType*tint InsertNode(NodeType*t，KeyType key)KeyType key)NodeType*p,*qNodeType*p,*q，*s;*s;if(!BST_Search(*tif(!BST_Search(*t，key,&p,&q)key,&p,&q)s=(NodeType*)malloc(sizeof(NodeType);s=(NodeType*)malloc(sizeof(NodeType);s-data.key=keys-data.key=key；s-lc=NULLs-lc=NULL；s-rc=NULLs-rc=NULL；if(!p)if(!p)t=st=s；elseelse if(keyp-data.key)if(keyp-data.key)p-rchild=sp-rchild=s；elseelsep-lchild=sp-lchild=s；return 1 return 1；return 0return 0；感谢你的观看2019年8月23【算法8.4】二叉排序树的插入算法感谢你的观看2019年8 例例如如，给给定定关关键键字字序序列列5353，8080，6969，4545，5858，3030，8888，则则构构造造相相对对应应的的一一棵棵二二叉叉排排序序树树的过程如图的过程如图8.58.5所示：所示：(a(a)(b(b)5353(c(c)53538080(d(d)696980805353(e(e)6969808053534545(f(f)69698080535345455858(g(g)6969808053534545585830306969808053534545585830308888(h(h)图图8.58.5二叉排序树的插入过程二叉排序树的插入过程(a)(a)空树；（空树；（b b）插入）插入5353；(c)(c)插入插入9090；(d)(d)插入插入6969；(e)(e)插入插入4545；(f)(f)插入插入5858；(g)(g)插入插入3030；(h)(h)插入插入8888；感谢你的观看2019年8月23例如，给定关键字序列53，80，69，45，58，30二叉排序树的删除二叉排序树的删除 设待删结点的为设待删结点的为p p，p p的双亲结点为的双亲结点为d d，若，若p p的左右孩的左右孩子分别为子分别为plpl和和prpr，则删除操作可分以下三种情况进，则删除操作可分以下三种情况进行讨论：行讨论：（1 1）若结点）若结点p p为叶子结点，则为叶子结点，则plpl和和prpr均为空二叉树。均为空二叉树。由于删除叶子结点不会破坏整棵树的结构，则根据由于删除叶子结点不会破坏整棵树的结构，则根据p p是是d d的左子树还是右子树，将的左子树还是右子树，将d d的左孩子或右孩子的左孩子或右孩子指针域置空即可。删除过程如图指针域置空即可。删除过程如图8.68.6所示。所示。(b)607555365912删去叶子结点80图8.6删除二叉排序树中的叶子结点(a)删除叶子80之前；(b)删除叶子80之后60755536591280(a)p感谢你的观看2019年8月23二叉排序树的删除(b)607555365912删去叶子图8 （2 2）若结点）若结点p p只有左子树只有左子树plpl或右子树或右子树prpr时，时，则用则用p p的左子树的根结点的左子树的根结点plpl或右子树的根结或右子树的根结点点prpr取代被删除的结点即可。删除过程如取代被删除的结点即可。删除过程如图图8.78.7所示。所示。图8.7删除二叉排序树中的单支结点(a)删除左单支结点36之前；(b)删除左单支结点36之后；(a)删除右单支结点80之前；(b)删除右单支结点80之后删去左单支结点3660755536591280(a)p9080(b)607555125990删去右单支结点8060755536591280(c)90p60755536591290(d)感谢你的观看2019年8月23（2）若结点p只有左子树pl或右子树pr时，则用p的左子树 （3 3）若结点）若结点p p同时有左右子树同时有左右子树plpl和和PrPr时，则时，则用被删除结点的左子树的根取代被删除的用被删除结点的左子树的根取代被删除的结点，将被删除结点的右子树移动到被删结点，将被删除结点的右子树移动到被删除结点的左子树的最右下方，即用结点除结点的左子树的最右下方，即用结点plpl取代结点取代结点p p，将，将PrPr及其子树移动到及其子树移动到plpl的右子的右子树的最右下方，如图树的最右下方，如图8.88.8所示。所示。(a)dpp rp l8060755512599070(b)p lp r70596055128090图8.8删除二叉排序树中的具有左右子树的结点(a)删除有左右子树结点75之前；(b)删除有左右子树结点75之后感谢你的观看2019年8月23（3）若结点p同时有左右子树pl和Pr时，则用被删除结点的【算法【算法8.58.5】二叉排序树的删除算法】二叉排序树的删除算法int DeleteNode(NodeType*tint DeleteNode(NodeType*t，KeyType key)KeyType key)/*/*在二叉排序树在二叉排序树t t中若存在关键字值为中若存在关键字值为keykey的结点则的结点则删除，函数返回删除，函数返回1 1，否则返回，否则返回0*/0*/NodeTypeNodeType*p,*d*p,*d，*s;*s;if(BST_Search(*tif(BST_Search(*t，keykey，&p&p，&d)&d)/*/*调用查调用查找算法，查找关键字值为找算法，查找关键字值为keykey的结点的结点*/*/if(q=NULL)if(q=NULL)/*/*被删除结点是被删除结点是根结点根结点*/*/if(p-lchild=NULL)if(p-lchild=NULL)*t=p-rchild;/*t=p-rchild;/*被删除结点无左子树，将其右子树被删除结点无左子树，将其右子树作为删除此结点后的树作为删除此结点后的树*/*/感谢你的观看2019年8月23【算法8.5】二叉排序树的删除算法感谢你的观看2019年8月（续）elseelse/*/*被删除结点有左子树，将其左被删除结点有左子树，将其左子树作为根结点子树作为根结点*/*/*t=p-lchild;*t=p-lchild;s=*t;/*s=*t;/*寻找被删除结点左子树的寻找被删除结点左子树的最右下结点最右下结点*/*/while(s-rchild!=NULL)while(s-rchild!=NULL)s=s-rchild;s=s-rchild;s-rchilds-rchildp-rchild;p-rchild;else if(!p-lchild)else if(!p-lchild)/*/*待删结点不是根结点，待删结点不是根结点，且其左子树为空，重接它的右子树且其左子树为空，重接它的右子树*/*/s=p s=p；p=p-rchildp=p-rchild；free(s)free(s)；感谢你的观看2019年8月23（续）感谢你的观看2019年8月23（续）（续）elseelse if(!p-rchild)if(!p-rchild)/*/*待删结点的右待删结点的右子树为空，重接它的左子树子树为空，重接它的左子树*/*/s=p s=p；p=p-lchildp=p-lchild；free(s)free(s)；else/*else/*待删结点的左右子树均不空，将其右待删结点的左右子树均不空，将其右子树挂到左子树的最右下方子树挂到左子树的最右下方*/*/s=p-lchild s=p-lchild；while(s-rchild)s=s-rchildwhile(s-rchild)s=s-rchild；/*/*找找到左子树最右下的结点到左子树最右下的结点*/*/s-rchild=p-rchild;s-rchild=p-rchild;/*/*将被删除结点将被删除结点的右子树作为的右子树作为s s的右子树的右子树*/*/s=ps=p；p=p-lchildp=p-lchild；free(s)free(s)；/*/*用被删除结点的左用被删除结点的左子树的根取代被删除结点子树的根取代被删除结点*/*/retrun 1 retrun 1；return 0 return 0；感谢你的观看2019年8月23（续）感谢你的观看2019年8月23平衡二叉树又称平衡二叉树又称AVLAVL树，其性质是：树，其性质是：(1)(1)、或或者者是是一一棵棵空空树树，或或者者是是满满足足下下列列性性质的二叉树；质的二叉树；(2)(2)、树树的的左左子子树树和和右右子子树树的的深深度度之之差差的的绝绝对值不大于对值不大于1 1且左右子树也需满足上述性质。且左右子树也需满足上述性质。*8.3.2*8.3.2 平衡二叉树平衡二叉树感谢你的观看2019年8月23平衡二叉树又称AVL树，其性质是：*8.3.2平衡二叉树 如如图图8.98.9所所示示，结结点点左左边边的的数数字字为为该该结结点点的的平平衡衡因因子子，图图(a)(a)为为非非平平衡衡二二叉叉树树，图图(b)(b)为平衡二叉树。为平衡二叉树。060852080897751-221-102550(a)不平衡二叉树8520808960775101-11100(b)平衡二叉树图8.9平衡二叉树与非平衡二叉树感谢你的观看2019年8月23如图8.9所示，结点左边的数字为该结点的平衡因子，图(a 动态平衡技术的基本思想：在构造二叉排动态平衡技术的基本思想：在构造二叉排序树的过程中，每当插入一个结点时，首序树的过程中，每当插入一个结点时，首先检查插入之后是否破坏了树的平衡性，先检查插入之后是否破坏了树的平衡性，若是则找出其中离插入结点最近的不平衡若是则找出其中离插入结点最近的不平衡子树，在保持二叉排序树特性的前提下，子树，在保持二叉排序树特性的前提下，调整不平衡子树中各结点之间的关系，以调整不平衡子树中各结点之间的关系，以达到新的平衡。设离插入结点最近的不平达到新的平衡。设离插入结点最近的不平衡子树的根结点为衡子树的根结点为r r，则对该子树进行的平，则对该子树进行的平衡化调整，归纳起来有以下四种情况：衡化调整，归纳起来有以下四种情况：感谢你的观看2019年8月23动态平衡技术的基本思想：在构造二叉排序树的过程中，每当1.RR1.RR型调整型调整(逆时针逆时针)(a)插入前的平衡子树0-1rLhhRaMh(b)插入后未调整的子树-1-2rLhaMhh+1Re(c)调整后的平衡子树00aMrLh+1eRh+1图8.10RR型平衡处理过程感谢你的观看2019年8月231.RR型调整(逆时针)(a)插入前的平衡子树0-1rL2.LL2.LL型调整型调整(顺时针顺时针)hRrMaLhh01(a)插入前的平衡子树h+1h+1LaRrMe00(c)调整后的平衡子树(b)插入后未调整的子树hRr21eh+1MaLh图8.11LL型平衡处理过程感谢你的观看2019年8月232.LL型调整(顺时针)hRrMaLhh01(a)插入3.LR3.LR型调整型调整(先逆后顺先逆后顺)hLah-1NdMh-1hRr001(a)插入前的平衡子树hLah-1NdMh-1hRre12-1(b)插入后未调整的子树2h-1NdhRrLhaMeh02(c)先左旋处理h-1NhRrdLhaMeh00-1(d)后右旋处理图8.12LR型平衡处理过程感谢你的观看2019年8月233.LR型调整(先逆后顺)hLah-1NdMh-1hR4 4RLRL型调整型调整(先顺后逆先顺后逆)(c)先右旋处理-2hLrd-1-1hRah-1NMeh0d0-1hRah-1NhLrMeh(d)后左旋处理图8.13RL型平衡处理过程感谢你的观看2019年8月234RL型调整(先顺后逆)(c)先右旋处理-2hLrd-1.B1.B树的定义树的定义一棵一棵m m阶的阶的B B树满足下列条件：树满足下列条件：(1)(1)树中每个结点至多有树中每个结点至多有m m棵子树；棵子树；(2)(2)除根结点和叶子结点外，其他每个结点至少除根结点和叶子结点外，其他每个结点至少有有m m/2/2 棵子树；棵子树；(3)(3)根结点至少有两个子树根结点至少有两个子树(B(B树只有一个结点树只有一个结点除外除外)；(4)(4)所有的叶子结点都在同一层，且叶结点不包所有的叶子结点都在同一层，且叶结点不包含任何信息；含任何信息；*8-3-3 B_*8-3-3 B_树和树和B+B+树树感谢你的观看2019年8月231.B树的定义*8-3-3B_树和B+树感谢你的观看(5)(5)有有j j个孩子的非叶子结点恰好有个关键字，个孩子的非叶子结点恰好有个关键字，该结点包含的信息为该结点包含的信息为P0,K1,P1,K2,P2,P0,K1,P1,K2,P2,P,Pj j-1,K-1,Kj j-1,P-1,Pj j-1-1其中，其中，K Ki i为关键字，且满足为关键字，且满足K Ki iKKi i+1+1；P Pi i为指为指向子树根结点的指针，且向子树根结点的指针，且P Pi i-1-1所指子树中所有所指子树中所有结点的关键字都小于结点的关键字都小于K Ki i，P Pi i所指子树中所有结所指子树中所有结点的关键字都大于点的关键字都大于K Ki i。感谢你的观看2019年8月23(5)有j个孩子的非叶子结点恰好有个关键字，感谢你的观看2例如，下图为一个例如，下图为一个6 6阶的阶的B B树。树。感谢你的观看2019年8月23例如，下图为一个6阶的B树。感谢你的观看2019年8月23B B树的查找树的查找在在B B树上的查找给定的关键字树上的查找给定的关键字KeyKey的方法是：的方法是：首先根据给定的首先根据给定的B B树的指针取出根结点，树的指针取出根结点，在根结点所包含的关键字中按顺序或二分法在根结点所包含的关键字中按顺序或二分法查找给定的关键字，若查找给定的关键字，若K Ki i=Key=Key，则查找成功；，则查找成功；否则一定可以找到否则一定可以找到K Ki i-1-1和和K Ki i，使得，使得K Ki i-1KeyK1KeyKi i，取指针，取指针P Pi i所指的结点继续查找，所指的结点继续查找，重复上述过程，直到找到或指针重复上述过程，直到找到或指针P Pi i为空，查为空，查找失败。整个查找过程中访问外存的次数不找失败。整个查找过程中访问外存的次数不超过超过B B树的深度。树的深度。感谢你的观看2019年8月23B树的查找感谢你的观看2019年8月23B+B+树的定义树的定义B+B+树是树是B B树的一个变形树，它和树的一个变形树，它和B B树的区树的区别在于：别在于：(1)(1)有有n n棵子树的结点中包含有棵子树的结点中包含有n n个关键字；个关键字；(2)(2)所有的叶子结点中包含了全部关键字的所有的叶子结点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，信息，以及指向含这些关键字记录的指针，且叶子结点按关键字大小顺序链接。且叶子结点按关键字大小顺序链接。(3)(3)所有分支结点可看成是索引部分，结点所有分支结点可看成是索引部分，结点中仅包含其子树中最大中仅包含其子树中最大(或最小或最小)关键字。关键字。感谢你的观看2019年8月23B+树的定义感谢你的观看2019年8月23如下图所示为一棵如下图所示为一棵3 3阶的阶的B+B+树。为便于查树。为便于查找提供了两个头指针找提供了两个头指针(root(root和和headhead指针指针)。感谢你的观看2019年8月23如下图所示为一棵3阶的B+树。为便于查找提供了两个头指针(*8-3-4*8-3-4 键树键树 键树又称为数字查找树（键树又称为数字查找树（Digital Search Digital Search TreeTree）或）或TrieTrie树树(trie(trie为为retrieveretrieve中间中间4 4个个字符字符)。它是一棵度。它是一棵度22的树，树中的每个的树，树中的每个结点中不是包含一个或几个关键字，而是结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。只含有组成关键字的符号。感谢你的观看2019年8月23*8-3-4键树键树又称为数字查找树（Digital 例如：例如：JANJAN，FEBFEB，MARMAR，APRAPR，MAYMAY，JUNJUN，JULJUL，AGUAGU，SEPSEP，OCTOCT，NOVNOV，DECDEC可用图可用图8.168.16所示的键树表示。所示的键树表示。图8.16关键字符集的一棵键树感谢你的观看2019年8月23例如：JAN，FEB，MAR，APR，MAY，JUN，J 键树的查找过程为：从根结点出发，沿和键树的查找过程为：从根结点出发，沿和给定值相应的指针逐层向下，直到叶子结给定值相应的指针逐层向下，直到叶子结点；若叶子结点中的关键字和给定值相等，点；若叶子结点中的关键字和给定值相等，则查找成功；若分支结点中与给定值相应则查找成功；若分支结点中与给定值相应的指针为空，或叶子结点中的关键字和给的指针为空，或叶子结点中的关键字和给定值不相等，则查找失败。定值不相等，则查找失败。感谢你的观看2019年8月23键树的查找过程为：从根结点出发，沿和给定值相应的指针逐哈希表查找基本思想：哈希表查找基本思想：根据结点的键值从而确定结点的存储位置。即以待查的结点关键字K为自变量，通过一个确定的函数H，计算出对应的函数值H(K)，并以这个函数值作为该结点的存储地址，将结点存入H(K)所指的存储位置上。查找时再根据要查找的关键字K为自变量，用同样的函数计算地址，然后到相应的单元里去取要查找的结点。上述的函数H称为哈希函数，H(K)称为哈希地址。8-4-18-4-1哈希表哈希表感谢你的观看2019年8月23哈希表查找基本思想：8-4-1哈希表感谢你的观看2019年1.1.数字分析法数字分析法当关键字的位数比哈希表的地址码位数多时，当关键字的位数比哈希表的地址码位数多时，对关键字的各位数字进行分析，丢掉数字分布对关键字的各位数字进行分析，丢掉数字分布不均匀的位，取分布均匀的位作为地址。不均匀的位，取分布均匀的位作为地址。8.4.28.4.2哈希函数的构造方法哈希函数的构造方法 感谢你的观看2019年8月231.数字分析法8.4.2哈希函数的构造方法感谢你的观看 例如，有例如，有8080个结点，个结点，其关键字为其关键字为8 8位十进制位十进制数。若哈希表的表长数。若哈希表的表长为为100100，则可取两位十，则可取两位十进制数组成哈希地址，进制数组成哈希地址，地址编号为地址编号为099099。设。设这这8080个关键字中的一个关键字中的一部分如图部分如图8.178.17所示。所示。感谢你的观看2019年8月23例如，有80个结点，其关键字为8位十进制数。若哈希表的表2.2.平方取中法平方取中法该方法是先计算出关键字该方法是先计算出关键字K K的平方值的平方值K2K2，然后，然后再取再取K2K2值的中间几位或几位的组合作为哈希地值的中间几位或几位的组合作为哈希地址，取的位数由哈希表的表长决定。址，取的位数由哈希表的表长决定。例如，关键字为例如，关键字为36323632，则，则36322=1319142436322=13191424。若表长为若表长为10001000，则可以取第四位到第六位为哈，则可以取第四位到第六位为哈希地址，即希地址，即H(3632)=914H(3632)=914。感谢你的观看2019年8月232.平方取中法感谢你的观看2019年8月233.3.折叠法折叠法将关键字分割成位数将关键字分割成位数相同的几部分相同的几部分(最后一最后一部分的位数可以不同部分的位数可以不同)，然后取这几部分的，然后取这几部分的叠加和叠加和(舍去进位舍去进位)作作为哈希地址，这方法为哈希地址，这方法称为折叠法。例如，称为折叠法。例如，key=978 750 835 150key=978 750 835 150，哈希表的长度为，哈希表的长度为10001000，则应把关键字，则应把关键字分成分成3 3位一段，分别进位一段，分别进行移位叠加和折叠叠行移位叠加和折叠叠加，求得哈希地址为加，求得哈希地址为713713和和921921，如图，如图8-188-18所示。所示。图8-18由折叠法求哈希地址(a)移位叠加法(b)折叠叠加法感谢你的观看2019年8月233.折叠法图8-18由折叠法求哈希地址感谢你的观看2014 4除余法除余法(亦称为除留余数法亦称为除留余数法)选择一个适当的正整数选择一个适当的正整数P P，用，用P P去除关键去除关键字，取其余数作为哈希地址，即字，取其余数作为哈希地址，即H(key)=key%P+b (bH(key)=key%P+b (b为常数为常数)感谢你的观看2019年8月234除余法(亦称为除留余数法)感谢你的观看2019年8月25 5伪随机数法伪随机数法采用一个伪随机函数作哈希函数，即采用一个伪随机函数作哈希函数，即H(key)=random(key)H(key)=random(key)。在实际应用中，应根据具体情况选用不同在实际应用中，应根据具体情况选用不同的方法。通常考虑以下因素：的方法。通常考虑以下因素：（1 1）计算哈希函数所需要的时间。）计算哈希函数所需要的时间。（2 2）关键字的长度。）关键字的长度。（3 3）哈希表的大小。）哈希表的大小。（4 4）关键字的分布情况。）关键字的分布情况。（5 5）查找结点的频率。）查找结点的频率。感谢你的观看2019年8月235伪随机数法感谢你的观看2019年8月231.1.开放地址法开放地址法 基本思想是：当哈希地址基本思想是：当哈希地址I=H(key)I=H(key)出现出现冲突时，以冲突时，以I I为基础，产生另一个哈希地为基础，产生另一个哈希地址址I1I1；若；若P1P1仍然冲突，再以仍然冲突，再以I1I1为基础，为基础，产生下一个哈希地址产生下一个哈希地址I2I2，直到找出，直到找出一个不冲突的哈希地址为止。这种方法一个不冲突的哈希地址为止。这种方法的一般哈希函数的形式为：的一般哈希函数的形式为：Hi+1=(Hi(key)+di)MOD m Hi+1=(Hi(key)+di)MOD m i=1,2,i=1,2,k(km-1),k(km-1)8.4.38.4.3处理冲突的方法处理冲突的方法感谢你的观看2019年8月231.开放地址法8.4.3处理冲突的方法感谢你的观看201其中，其中，H(key)H(key)为哈希函数；为哈希函数；m m为哈希表表长；为哈希表表长；didi为增量序列，通常有三种取法：为增量序列，通常有三种取法：（1 1）di=1di=1，2 2，3 3，m-1m-1，称为线性探测，称为线性探测再散列；再散列；（2 2）di=12di=12，-12-12，2222，-22-22，k2,-k2,-k2(km/2)k2(km/2)，称为二次探测再散列；，称为二次探测再散列；（3 3）di=di=伪随机数序列，称为伪随机探测再伪随机数序列，称为伪随机探测再散列。散列。感谢你的观看2019年8月23其中，H(key)为哈希函数；m为哈希表表长；di为增量序列2 2再哈希法再哈希法这种方法是构造多个哈希函数：这种方法是构造多个哈希函数：Hi=RHi(key)i=1Hi=RHi(key)i=1，2 2，k k（式（式8.128.12）当哈希地址当哈希地址H1=RH1(key)H1=RH1(key)发生冲突时，发生冲突时，再计算再计算H2=RH2(key)H2=RH2(key)，直到没有冲，直到没有冲突发生。这种方法不容易产生聚集，但突发生。这种方法不容易产生聚集，但增加了计算时间。增加了计算时间。感谢你的观看2019年8月232再哈希法感谢你的观看2019年8月233 3链地址法链地址法这种方法的基本思想是将所有关键字为同义这种方法的基本思想是将所有关键字为同义词的结点存储在同一个线性链表中，形成词的结点存储在同一个线性链表中，形成一同义词链。一同义词链。感谢你的观看2019年8月233链地址法感谢你的观看2019年8月23例例8.4 8.4 已知一组关键字为（已知一组关键字为（2121，4040，3737，6767，8686，4545，4343，8484，7676，5454），若哈希表表长为），若哈希表表长为1111，取哈，取哈希函数希函数H(key)=key MOD 11H(key)=key MOD 11，则用链地址法法处理冲，则用链地址法法处理冲突的结果如图突的结果如图8.218.21所示。所示。图8.21链地址法处理冲突的哈希表感谢你的观看2019年8月23例8.4已知一组关键字为（21，40，37，67，86，4 4建立公共溢出区建立公共溢出区 这也是处理冲突的一种常用方法。基本思想这也是处理冲突的一种常用方法。基本思想是将哈希表分为基本表和溢出表两部分，凡是将哈希表分为基本表和溢出表两部分，凡与基本表发生冲突的结点一律存入溢出表。与基本表发生冲突的结点一律存入溢出表。感谢你的观看2019年8月234建立公共溢出区感谢你的观看2019年8月238-4-48-4-4哈希表的查找哈希表的查找 哈希表的查找过程与哈希表的构造过程是一致的。对于给定值key，先哈希函数计算出哈希地址。若哈希地址单元中没有结点，说明查找失败，则插入关键字为key的结点；否则，哈希地址单元中的结点的关键字值与key相等，则查找成功，反之则发生冲突，需要反复执行以下冲突处理过程：按照冲突处理方法计算“下一地址”，直到哈希表中某个存储单元为“空”或表中所填结点的关键字等于给定值时为止。感谢你的观看2019年8月238-4-4哈希表的查找哈希表的查找过程与哈希表的构造过程下面以线性探测再散列为例，给出哈希表的查找算下面以线性探测再散列为例，给出哈希表的查找算法。法。开放定址哈希表的存储结构如下：开放定址哈希表的存储结构如下：#define MAXSIZE 99#define MAXSIZE 99/*/*哈希表的最大长度哈希表的最大长度*/*/typedef structtypedef structDataType*elem;/*DataType*elem;/*结点存储基址，动态结点存储基址，动态分配数组分配数组*/*/int count;int count;/*/*当前结点个数当前结点个数*/*/int sizeindex;int sizeindex;/*/*哈希表当前的容量哈希表当前的容量*/*/HashTable;HashTable;感谢你的观看2019年8月23下面以线性探测再散列为例，给出哈希表的查找算法。感谢你的观看【算法【算法8.68.6】线性探测再散列查找算法】线性探测再散列查找算法int Hash_search(HashTable HT,DataType r)int Hash_search(HashTable HT,DataType r)/*HT/*HT为哈希表，为哈希表，r r为待查找或插入的结点为待查找或插入的结点*/*/int p,n;int p,n;p=H(r.key);n=p-1;p=H(r.key);n=p-1;while(Tp.key!=NULL)&while(Tp.key!=NULL)&(key!=HTp.key)&(p!=n)(key!=HTp.key)&(p!=n)p=(p+1)%MAXSIZE;p=(p+1)%MAXSIZE;if(HTp.key=key)return(p);/*if(HTp.key=key)return(p);/*查找查找成功，返回结点在表中的位置成功，返回结点在表中的位置*/*/else if(p=n)return-2;else if(p=n)return-2;/*/*溢出溢出*/*/else HTp=r;return-1;/*else HTp=r;return-1;/*插入插入*/*/感谢你的观看2019年8月23【算法8.6】线性探测再散列查找算法感谢你的观看2019年88-4-58-4-5哈希表的查找效率分析哈希表的查找效率分析1 1线性探测再散列法线性探测再散列法查找成功时的平均查找长度为：查找成功时的平均查找长度为：查找失败时的平均查找长度为：查找失败时的平均查找长度为：感谢你的观看2019年8月238-4-5哈希表的查找效率分析1线性探测再散列法感谢你的观2 2链地址法链地址法查找成功时的平均查找长度为：查找成功时的平均查找长度为：查找失败时的平均查找长度为：查找失败时的平均查找长度为：感谢你的观看2019年8月232链地址法感谢你的观看2019年8月233 3伪随机探测再散列法、二次探测再散列法伪随机探测再散列法、二次探测再散列法及再哈希法及再哈希法查找成功时的平均查找长度为：查找成功时的平均查找长度为：查找失败时的平均查找长度为：查找失败时的平均查找长度为：感谢你的观看2019年8月233伪随机探测再散列法、二次探测再散列法及再哈希法感谢你的观见教材习题见教材习题习题习题感谢你的观看2019年8月23见教材习题习题感谢你的观看2019年8月23