资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。不能作为科学依据。,第九章 查找,1/98,这也是线性表基本运算之一。通常称为检索、查询等。,1 线性查找,11 次序检索,基本思想：,从线性表一端开始，逐一地将待查找元素关键字与每个元素关键字进行比较，若找到，则返回1，不然返回0。,该算法时间,复杂度为O(n).,1 线性查找,2/98,次序查找采取,从头至尾逐一比较,最快O(1)最慢O(n),查找成功,等概率平均时间复杂性,O(,(n+1)/2,),1/n(1+2+3+n)=(n+1)/2,查找失败O(n+1),查找等概率平均时间复杂性,O(,3(n+1)/4,),查找成功失败各半,1/2n(1+2+n)+n(n+1)=,3(n+1)/4,1 线性查找,3/98,1 线性查找,12 二分查找,亦称折半查找，是基于提升查找速度一个方法。检索时要求元素是排序。,基本思想：,每次将待查找元素关键字与已排序元素序列中间点元素进行比较，如相等，则返回1，不然修改高点或低点，重新进行查找比较。,该算法时间复杂度为O(n).,4/98,这是有序表查找查找,对已排序查找结构先确定中点，比较待查关,键字与中点关键字大小，重复直到成功。,求n个数据折半查找等概率成功查找平均时,间复杂性,1 2 3 4 5 6 7 8 9 10,1,2,2,3,3,3,3,4,4,4,1+2*2+4*3+3*4=29,O(29/10),5/98,n个元素折半查找,2,k,-1n2,k+1,-1,查找成功平均概率时间复杂性,介于 log,2,(2,k,)-1 和 log,2,(2,k+1,)-1 之间,即 k-1 和 k 之间,k=log,2,(n+1),n个元素折半查找成功平均概率时间复杂性,log,2,(n+1)-1/2,6/98,1 线性查找,13 分块查找,亦称索引次序查找。也是基于提升查找速度一个方法。检索时要求元素组成块间是排序，而块内是未排好序。,基本思想：,将全部元素按关键字值划分成若干块，块之间是排序，而块内暂时是无序。查找时候，首先折半查找确定元素所在块，然后再在块内进行次序查找即可比较。,7/98,3、索引次序查找,分块有序,后一子表中关键字都大于前一子表中关键字,22,48,86,1,7,13,22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53,最大关键字,起始地址,索引表,8/98,索引次序表查找,查找 关键字key=38,1.先检索索引表 确定子表位置,2.再在子表中查找,22,48,86,1,7,13,22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53,索引表,9/98,分块查找成功平均概率时间复杂性,索引表查找时间+子表查找时间,设索引表长为s，查找表长为n,被平均分成s块，,每块长n/s,索引表平均查找时间 (s+1)/2,子表平均查找时间 (n/s+1)/2,(s+1)+(n/s+1)=(s+n/s)+1,当 s=n 时 有最小值 n +1,10/98,当索引次序表已经排序时，子块查找能够用折半查找。,平均查找时间：,(s+1)/2+log,2,(1+n/s)-1/2,=log,2,(1+n/s)+s/2,索引也用折半查找，平均查找时间,log,2,(s+1)-1/2+log,2,(1+n/s)-1/2,=log,2,(s+1)(1+n/s)-1,当s=n 时 2 log,2,(n+1)-1,11/98,2 树形结构查找,21 二叉排序树及其查找过程,二叉树BT是二叉排序树，只要BT是满足以下条件,：,（1）若BT左子树非空，则其左子树上全部结点值均小于其根结点值；（2）若其右子树上全部结点值均大于其根结点值；（3）其左右子树均为二叉排序树。,对二叉排序树中序遍历结果就是一个升序序列。,二叉排序树又称为二叉查找树。,于是，只要将元素序列组织成二叉排序树，在进行查找时，让待查找元素与根结点值进行比较，若相等，则查找成功，不然，假如比根结点小，则只需要在左子树中查找即可；假如比根结点大，则只需要在右子树中查找即可。,12/98,2 树形结构查找,其所包括到数据结构以下：,typedef struct btnode,keytype key;,datatype other;,struct btnode*lchild,*rchild;,BSTNODE;,BSTNODE*ptr;,则*ptr就表示一棵二叉排序树。,13/98,2 树形结构查找,22 二叉排序树实现查找运算,依据二叉排序树定义和性质，不难得到其查找算法：,int bstsearch(*Pt,x),pkey=x)return(1);,if(p-keyx)prchild;,else plchild;,14/98,二叉查找树查找分析,平均等概率查找时间,(1+2+2+3+3+3)/6=14/6,45,12,57,8,20,60,45,12,8,20,3,11,(1+2+3+4+5+6)/6=7/2,15/98,随机二叉查找树等概率平均查找时间,P(n)2(1+1/n)ln,n,O(log,2,n),最坏 O(n/2),16/98,特点：用于频繁进行插入、删除、查找所谓动态查找表。,122,250,300,110,200,99,二叉排序树,L,N,P,E,M,C,Y,105,230,216,17/98,查找步骤：若根结点关键字值等于查找关键字，成功。,不然，若小于根结点关键字值，查其左子树。,若大于根结点关键字值，查其右子树。,在左右子树上操作类似。,122,250,300,110,200,99,105,230,216,18/98,2 树形结构查找,2.2 二叉排序树插入运算,因为插入运算是二叉树基本运算之一，所以利用二叉树插入运算就能够实现在线性升序序列中插入结点，使之依然是升序功效。,其实现过程为,：,若二叉排序树为空，则待插入结点*s就作为根结点插入到空二叉树中；若二叉树非空，则比较s-key:p-key,若，就插入到右子树中，若=则无须插入。,该过程是递归，很轻易得到递归算法，也能够得到非递归算法。,19/98,2 树形结构查找,void insertbst(*pt,*s),p=pt;,while(p!=NULL),fkeykey),plchild;,else prchild;,if(pt=NULL)ptkeykey)f-lchildrchildrchild=NULL,则就相当于将空树连接到*fath左（右）链域中。,30/98,2 树形结构查找,（2）,若*p有左子树，则*p也可能有右子树，需要将*p左、右子树按照二叉排序树特征，连接到适当位置。此时能够采取两种处理方法：一个是令p左子树直接连接到*p双亲*fath左（右）链域上，而*p右子树下接到*p中序前趋结点*s右链域上。（这里*s是*p左子树中最右下结点，其右链域必定为空）。,另外一个处理方法是：采取以*p中序前趋*s顶替*p(相当于将*s内容复制到*p中)，将*s左子树直接上接到*s双亲*q左（右）链域上，再删去*s。,31/98,叶子结点：直接删除，更改它父亲结点对应指针域为空。如：删除关键字为 15、70 结点。,15,60,70,30,20,50,60,30,20,50,子树根结点：通常做法：选取“替身”取代被删结点。有资格充当该替身是谁哪？左子树中最大结点 或 右子树中最小结点，参看图。,关键点：维持二叉排序树特征不变。在中序周游中紧靠着被删结点结点才有资格作为“替身”。,32/98,122,250,300,110,200,99,105,230,216,400,450,500,子树根结点：若被删结点左儿子为空或者右儿子为空。,以下列图所表示，删除结点关键字为 99、200 结点。,被删结点,122,250,300,200,230,216,400,450,500,110,105,删除,99,33/98,122,250,300,110,200,99,105,230,216,400,450,500,被删结点,子树根结点：若被删结点左儿子为空或者右儿子为空。,以下列图所表示，删除结点关键字为 99、200 结点。,122,250,300,230,216,400,450,500,删除,200,110,99,105,34/98,122,250,300,110,200,99,105,230,216,400,450,500,被删结点,子树根结点：若被删结点左儿子为空或者右儿子为空。,以下列图所表示，删除结点关键字为 99、200 结点。,结论：将被删结点另一儿子作为它父,亲结点儿子，终究是作为左儿子,还是右儿子依原替身结点和其父亲,结点关系而定。,释放被删结点空间。,被删结点,35/98,子树根结点：若被删结点左、右子树皆不空，通常做法：选取“替身”取代被删结点。有资格充当该替身是谁哪？左子树中最大结点(被删结点左子树中最右结点，其右儿子指针域为空)或 右子树中最小 结点(被删结点右子树中最左结点，其左儿子指针域为空)，参看下列图。,关键点：维持二叉排序树特征不变。在中序周游中紧靠着被删 结点结点才有资格作为“替身”。,122,250,300,110,200,99,105,230,216,400,450,500,被删结点,替身,替身,110,250,300,105,200,99,230,216,400,450,500,做法：将替身关键字复制到被删结,点关键字。,将结点 左儿子作为,父结点,右儿子。,110,110,99,注意：结点 右儿子必为空,结点 父结点为,110,110,99,36/98,122,250,300,110,200,99,105,230,216,400,450,500,被删结点,替身,替身,200,250,300,110,99,105,230,216,400,450,500,做法：将替身关键字复制到被删结,点关键字。,将结点 右儿子作为,父结点,左儿子。,注意：结点 左儿子必为空,结点 父结点为,200,200,200,200,250,37/98,122,250,300,110,200,99,105,230,216,400,450,500,被删结点,替身,替身,结论：,先将替身关键字复制到被删结点,将原替身另一儿子作为它父亲,结点儿子，终究是作为左儿子还,是右儿子依原替身结点和其父亲结,点关系而定。,释放原替身结点空间。,38/98,F,P,被删结点,P,R,P,L,F,P,被删结点,C,C,L,P,R,Q,Q,L,S,S,L,F,S,C,C,L,P,R,Q,Q,L,S,L,F,C,C,L,P,R,Q,Q,L,S,S,L,F,P,R,P,L、,P,R,皆 空，,直接删除。,P,L,或P,R,为空，,P,L,为空，删除后情况。,1.删除法,2.删除法,39/98,2 树形结构查找,24 平衡二叉树介绍,因为二叉排序树结构形态直接影响到查找效率，所以必须结构出平衡二叉树。只要满足平衡因子（即任何两个子树高度之差）只能是-1，0，1，则称为平衡二叉树。,通常情况下，平衡二叉树深度是很低，所以其查找效率是最高。,40/98,D,G,E,D,A,B,C,F,E,G,B,A,平衡二叉排序树,起因：提升查找速度，防止最坏情况出现。如右图情况出现。,即使完全树树型最好，但结构困难。常使用平衡树。,C,F,平衡因子（平衡度）：结点平衡度是结点左子树高度右子树高度。,平衡二叉树：每个结点平衡因子都为 1、1、0 二叉树。或者说每个,结点左右子树高度最多差一二叉树。,注意：完全树必为平衡树，平衡树不一定是完全树。,41/98,平衡树 Adelson 算法本质特点：,以插入为例：,在左图所表示平衡树中插入关键字为 2 结点。,插入之后仍应保持平衡排序二叉树性质不变。,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,平衡树,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度为 0,危机结点,怎样用最简单、最有效方法保持平衡排序二叉树性质不变？,42/98,平衡树 Adelson 算法本质特点：,以插入为例：,在左图所表示平衡树中插入关键字为 2 结点。,插入之后仍应保持平衡排序二叉树性质不变。,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度为 0,危机结点,怎样用最简单、最有效方法保持平衡排序二叉树性质不变？,处理方案：,不包括到危机结点父亲结点，即以危机结点为根子树高度应保持不变（左图为 3）。,新结点插入后，找到第一个平衡度不为 0 结点（如左图结点,）即可。新插入结点和,第一个平衡度不为 0 结点（也可能是危机结点）之间结点，其平衡度皆为 0,在调整中，仅调整那些在平衡度改变路径上结点（如：），其它结点不予调整。,仍应保持排序二叉树性质不变。,9,3,5,9,43/98,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度为 0,危机结点,怎样用最简单、最有效方法保持平衡排序二叉树性质不变？,2,3,5,9,7,12,2,3,5,9,7,12,不能够以结点 为子树根结点！即使，对本例来说是能够行得通。,7,44/98,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度为 0,危机结点,关键：将造成出现,危机结点情况,全部分析去除，就能够使得平衡排序二叉树性质保持不变！,14,9,3,2,5,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,12,0,0,45/98,2.5 非平衡二叉树平衡处理方法,若一棵二叉排序树是平衡二叉树，插入某个结点后，可能会变成非平衡二叉树，这时，就能够对该二叉树进行平衡处理，使其变成一棵平衡二叉树。处理标准应该是处理与插入点最近、而平衡因子又比1大或比-1小结点。我们分四种情况讨论平衡处理。,1、LL型 处理(左左型),以下列图所表示，在A左孩子B上插入一个左孩子结点C，使A平衡因子由1变成了2，成为不平衡二叉树序树。这时平衡处理为：将A顺时针旋转，成为B右子树，而原来B右子树则变成A左子树，待插入结点C作为B左子树。(注：图中结点旁边数字表示该 结点平衡因子)，即左改组。,46/98,左改组（新插入结点出现在危机结点左子树上进行调整）情况分析：,1、LL,情况：（LL：表示新插入结点在危机结点左子树左子树上）,A,B,+1,h-1,0,+2,+1,h,h-1,h-1,LL,改组,B,L,B,R,A,R,B,A,0,h,0,h-1,h-1,B,L,B,R,A,R,危机结点,改组前：高度为 h+1,中序序列：,A,B,B,L,B,R,A,R,改组后：高度为 h+1,中序序列：,A,B,B,L,B,R,A,R,注意：改组后 平衡度为 0,A,B,47/98,2、,LR型处理(左右型),以下列图所表示，在A左孩子B上插入一个右孩子C，使A平衡因子由1变成了2，成为不平衡二叉排序树。这是平衡处理为：将C变到B与A 之间，使之成为LL型，然后按第(1)种情形LL型处理。此LR型又存在以下三种情形：,48/98,左改组（新插入结点出现在危机结点左子树上进行调整）情况分析：,2、LR,情况：（LR：表示新插入结点在危机结点左子树右子树上）情形1：,A,B,+1,h-1,0,+2,-1,h-1,LR,改组,B,L,A,R,危机结点,改组前：,高度为 h+1,中序序列：,注意：改组后 平衡度为 0,0,-1,C,B,C,C,L,C,R,h-2,h-2,h-1,0,+1,C,B,0,h-1,h-1,B,L,A,R,A,C,R,h-2,C,L,h-1,-1,0,A,B,B,L,A,R,C,C,L,C,R,改组后：,高度为 h+1,中序序列：,A,B,B,L,A,R,C,C,L,C,R,A,49/98,左改组（新插入结点出现在危机结点左子树上进行调整）情况分析：,2、LR,情况：（LR：表示新插入结点在危机结点左子树右子树上）情形2：,A,B,+1,h-1,0,+2,-1,h-1,LR,改组,B,L,A,R,危机结点,改组前：,高度为 h+1,中序序列：,注意：改组后 平衡度为+1,0,0,C,B,C,C,R,C,L,h-1,h-2,h-2,0,-1,C,B,0,h-1,h-1,B,L,A,R,A,C,R,h-1,C,L,h-2,+1,0,A,B,B,L,A,R,C,C,R,C,L,改组后：,高度为 h+1,中序序列：,A,A,B,B,L,A,R,C,C,R,C,L,50/98,左改组（新插入结点出现在危机结点左子树上进行调整）情况分析：,2、LR,情况：（LR：表示新插入结点在危机结点左子树右子树上）情形3：,A,B,+1,0,+2,-1,LR,改组,危机结点,改组前：,高度为 2,中序序列：,注意：改组后,平衡度为 0,0,0,C,B,C,0,A,B,C,A,新插入结点,A,B,C,改组后：,高度为 2,中序序列：,C,B,0,A,0,0,四种情况区分：,假如 平衡度为1 则为 LL型改组；,不然为 LR型改组：若 平衡度为1、1、0；则分别为 LRA、LRB、LRC型改组。,B,C,51/98,3、RR型处理(右右型),如图下所表示，在A右孩子B上插入一个右孩子C，使A平衡因子由-1变成-2，成为不平衡二叉排序树。这时平衡处理为：将A逆时针旋转，成为B左子树，而原来B左子树则变成A右子树，待插入结点C成为B右子树。,52/98,4、RL型处理(右左型),以下列图所表示，在A右孩子B上插入一个左孩子C，使A平衡因子由-1变成-2，成为不平衡二叉排序树。这时平衡处理为：将C变到A与B之间，使之成为RR型，然后按第3 种情形RR型处理。,53/98,这里右改组方法（新插入结点出现在危机结点右子树上进行调整）情况分析：,1、RR,情况：（RR：表示新插入结点在危机结点右子树右子树上）,处理图形和 LL 镜象相同,2、RL 情况：（RL：表示新插入结点在危机结点右子树左子树上）,1、处理图形和 LRA 镜象相同 2、处理图形和 LRB 镜象相同,3、处理图形和 LRC 镜象相同。,54/98,例2，给定一个关键字序列4,5,7,2,1,3,6，试生成一棵平衡二叉树。,分析：平衡二叉树实际上也是一棵二叉排序树，故能够按建立二叉排序树思想建立，在建立过程中，若碰到不平衡，则进行对应平衡处理，最终就能够建成一棵平衡二叉树。详细生成过程见下列图。,55/98,56/98,26 平衡二叉树查找及性能分析,平衡二叉树本身就是一棵二叉排序树，故它查找与二叉排序树完全相同。但它查找 性能优于二叉排序树，不像二叉排序树一样，会出现最坏时间复杂度O(n)，它时间复杂度与二叉排序树最好时间复杂相同，都为O(log,2,n)。,57/98,例3 对例2给定关键字序列4,5,7,2,1,3,6，试用二叉排序树和平衡二叉树两种方法查找，给出查找6次数及成功平均查找长度。,分析：因为关键字序列次序己经确定，故得到二叉排序树和平衡二叉树都是唯一,得到平衡二叉树见上图，得到二叉排序树见下列图。,58/98,从上图二叉排序树可知，查找6需4次，平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/72.57。,从图8-14平衡二叉树可知，查找6需2次，平均查找长度,ASL=(1+2+2+3+3+3+3)=17/72.43。,从结果可知，平衡二叉树查找性能优于二叉排序树。,59/98,1、为何采取B_ 树和 B+树：,大量数据存放在外存中，通常存放在硬盘中。因为是海量数据，不可能一次调入内存。所以，要屡次 访问外存。但硬盘驱动受机械运动制约，速度慢。所以，主要矛盾变为降低访外次数。,在 1970 年由 R bayer 和 E macreight 提出用B_ 树作为索引组织文件。提升访问速度、降低时间。,内存,E.G:,用二叉树组织文件，当文件统计个数为 100，000时，要找到给定关键字统计，需访问外存17次（log100,000）,太长了！,50,25,10,75,15,35,60,90,20,30,40,55,70,80,95,索引文件,数据文件,文件头，可常驻内存,文件访问示意图：索引文件、数据文件存在盘上,8.2.2 B_ 树和 B+树,60/98,2、B_ 树是一个多分支数，首先介绍 m,阶 B_ 树：,定义：m,阶 B_ 树满足或空，或：,A、根结点要么是叶子，要么最少有两个儿子,B、除根结点和叶子结点之外，每个结点儿子个数为:m/2 =s=m,C、有 s 个儿子非叶结点含有 n=s 1 个关键字，即:s=n+1,这些结点数据信息为：,（n,A0,K1,R1,A1,K2,R2,A2,Kn,Rn,An）,这里：n:关键字个数,A0：K1 且 Kn 结点地址（指在该 B_ 树中）,注意：K1=K2=.=Kn,D、全部叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。,61/98,比如：m=4,阶 B_ 树。除根结点和叶子结点之外，每个结点儿子个数,最少为 m/2 =2 个；结点关键字个数最少为 1。该 B_ 树深度为 4。,叶子结点都在第 4 层上。,1，99,3，47，58，64,1，39,1，27,1，11,2，43，78,1，18,1，35,F,F,F,F,F,F,F,F,F,F,F,F,第 1 层,第 2 层,第 3 层(L,层),第 4 层(L1,层),62/98,3、B_ 树查找代价分析：,查找过程，类似于二叉树查找。如查找关键字为 KEY,统计。,从根开始查找，假如 Ki=KEY 则查找成功，Ri 为关键字为 KEY 统计地址。,若 Ki KEY Ki+1;查找 Ai 指向结点,若 KEY Kn;查找 An指向结点,若 找到叶子，则查找失败。,注意：每次查找将去掉（s-1）/s 个分支，比二分查找快得多。,设关键字总数为 N，求 m阶 B_ 树最大层次 L。,层次结点数关键字个数（最少）,111,222（m/2 -1）,3 2（m/2 ）,2（m/2 ）（m/2 -1）,4 2（m/2 ）,2,2（m/2 ）,2,（m/2 -1）,L 2（m/2 ）,L-2,2（m/2 ）,L-2,（m/2 -1）,L+1 2（m/2 ）,L-1,所以，N=1 2（m/2 -1）+.+2（m/2 ）,L-2,（m/2 -1）=2 m/2,L-1,-1,故：Llog （N+1）/2）+1,63/98,3、B_ 树查找代价分析：,设关键字总数为 N，求 m阶 B_ 树最大层次 L。,故：Llog,m/2,（N+1）/2）+1,设 N 1000，000 且 m256，则 L m-1,则该结点满。必须分裂成两个结点。不然不满结束。,如结点原为：,（m-1,A,0,(K,1,A,1,),(K,2,A,2,),(K,m-1,A,m-1,)）,插入一个关键字之后变为：,（m,A,0,(K,1,A,1,),(K,2,A,2,),(K,m,A,m,)）,该结点将进行分裂：,.(K,m/2,p,).,（m/2-1,A,0,(K,1,A,1,),(K,m/2,A,m/2,)）（m-m/2,A,m/2,(K,m,A,m,)）,生成新结点 p,将原结点后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。,P,P,(K,m/2,p,),数据项插入上层结点之中,64/98,B-树插入方法,设要插入关键值为k统计，指向k所在统计指针为p。,首先找到k应插入叶子结点，将 k和p插入。然后，判断被插入结点是否满足m叉B-树定义，即插入后结点分支数是否大于m（结点关键字数是否大于m-1)，若小于，则插入结束；不然，要把该结点分裂成两个。方法是：,申请一个新结点，由指针p指向，将插入后结点按照关键字值大小分成左、中、右三部分，中间只含一项，左边留在原结点，右边移入新结点，中间组成新插入项，插入到它们双亲结点中，若双亲结点在插入后也要分裂，则在分裂后再往上插入。,65/98,比如：3 阶 B_ 树插入操作。m=3,m/2 -1=1;,最少 1 个关键字，二个儿子结点。,3，12,7 24 30,24，30,45，70,53,90,26,100,39,50,61,85,3,45，70,53,90,26,100,39,50,61,85,12,30,3,24 45 70,53,90,26,100,39,50,61,85,12,7,30,3,24,53,90,26,100,39,50,61,85,12,7,45,70,7插入,66/98,5、B_ 树删除操作,1、查找含有给定键值关键字 K,i,2、,假如 在第 L 层，可直接删除（注意：第 L+1 层为叶子结点），转 4。,3、不然，则首先生成“替身”。用 右子树中最左面结点关键字值，即 处于第 L 层上最小,关键字值取代 。然后，删除第 L 层上该关键字。,4、从第 L 层开始进行删除。,A、不动：若删除关键字值那个结点关键字个数仍处于 m/2 -1和 m-1之间。则结束。,B、借：若删除关键字值那个结点关键字个数原为 m/2 -1。而它们左或右邻居结,点关键字个数 m/2 -1;则借一个关键字过来。处理结束。,C、并：若该结点左或右邻居结点关键字个数为 m/2 -1;则执行合并结点操作。,如结点原为：,（.(K,i,A,i,),(K,i+1,A,i+1,),.）,（A,0,(K,1,A,1,)）,（A,0,(K,1,A,1,)）,K,1,L,第 L,层：找到了被删结点替身。,67/98,比如：3 阶 B_ 树删除操作。m=3,m/2 -1=1;,最少 1 个关键字，二个儿子结点。,3,24,45,53 90,37,100,50,61，70,被删关键字,3,24,45,61 90,37,100,53,70,借：向被删结点方向旋转,假定再删除该关键字,3,24,45,90,37,100,61，70,假定再删除该关键字,3，24,45,90,100,61，70,3，24,45 90,100,61，70,并,并,并,并：和父结点一个关键字、及邻居合并。有可能进行到根，使B_,树深度降低一层！,68/98,3 散列查找,因为前两种查找方法中，统计在结构中相对位置是随机，和其关键码值之间没有直接联络，所以在进行检索时，必须采取“比较”伎俩来实现，显然，查找效率依赖于检索过程中进行比较次数。,于是，理想查找是不经过任何比较或少经过比较就能够得到所查找元素，则必须在统计与其关键字值之间建立一个确定对应关系h，使得每个关键字和结构中一个唯一存放位置相对应，这么在检索时，找到给定值K影象H（K），若统计中存在关键码和k相等统计，则必定存放在h(k)存放位置上，所以不需要进行比较即可直接得到所查找统计。通常称这个对应关系h为散列函数，采取该散列函数所建立表称为散列表。,69/98,3 散列查找,实践表明,：,（1）假如散列表是一一对应函数，则依据散列函数对给定值进行某种运算，即可得到待查找元素位置；,（2）散列表占用空间可能比结点空间多；,（3）散列函数结构标准：运算尽可能简单，而且所占用空间均匀分布；,（4）不一样关键字值可能得到相同函数值，即可能有冲突产生,。,70/98,3 散列查找,由此可见：散列查找必须处理两个问题,：,（1）结构一个尽可能简单但冲突少、“均匀”“好”散列函数；,（2）正视而且必须处理面临“地址冲突”问题。,可见：,实际上第一个问题包容了第二个问题。因为一个“优异”散列函数必须处理地址冲突问题。,所以只要处理了第一个问题即可处理第二个问题。给出很好散列函数是由HASH给出，故散列查找又称HASH查找,。,71/98,3 散列查找,【例】,11,个元素关键码分别为,18,，,27,，,1,，,20,，,22,，,6,，,10,，,13,，,41,，,15,，,25,。选取关键码与元素位置间函数为,f(key)=key mod 11,1.,经过这个函数对,11,个元素建立查找表以下：,0 1 2 3 4 5 6 7 8 9 10,2.,查找时，对给定值,kx,依然经过这个函数计算出地址，再将,kx,与该地址单元中元素关键码比较，若相等，查找成功。,22|1|13|25|15|27|6|18|41|20|10,72/98,哈希表与哈希方法,：,选取某个函数H，依该函数按关键码计算元素存放位置，并按此存放；查找时，由同一个函数对给定值kx计算地址，将kx与地址单元中元素关键码进行比，确定查找是否成功，这就是哈希方法(杂凑法)；,哈希方法中使用转换函数称为哈希函数(杂凑函数)；,按这个思想结构表称为哈希表(杂凑表)。,73/98,哈希查找基本思想：在统计存放地址和它关键字之间建立一个确定对应关系；这么，不经过比较，一次存取就能得到所查元素查找方法,定义,哈希函数在统计关键字与统计存放地址之间建立一个对应关系叫,哈希函数是一个映象，是从关键字空间到存放地址空间一个映象,哈希函数可写成：addr(ai)=H(ki),ai,是表中一个元素,addr(ai)是ai存放地址,ki是ai关键字,关键字,集合,存放地址,集合,hash,74/98,哈希表应用哈希函数，由统计关键字确定统计在表中地址，并将统计放入此地址，这么组成表叫,哈希查找又叫散列查找，利用哈希函数进行查找过程叫,例 30个地域各民族人口统计表,编号 地区分 总人口 汉族 回族.,1 北京,2 上海,.,.,以编号作关键字，,结构,哈希函数：H(key)=key,H(1)=1,H(2)=2,以地区分作关键字，取地区,名称第一个拼音字母序号,作哈希函数：H(Beijing)=2,H(Shanghai)=19,H(Shenyang)=19,75/98,从例子可见：,哈希函数只是一个映象，所以哈希函数设定很灵活，只要使任何关键字哈希函数值都落在表长允许范围之内即可,冲突：key1,key2，,但H(key1)=H(key2),现象叫,同义词：含有相同函数值两个关键字，叫该哈希函数,哈希函数通常是一个压缩映象，所以冲突不可防止,，只能尽可能降低；同时，冲突发生后，应该有处理冲突方法,76/98,哈希函数结构方法,1、直接定址法,结构：取关键字或关键字某个线性函数作哈希地址，即H(key)=key,或 H(key)=akey+b,特点,直接定址法所得地址集合与关键字集合大小相等，不会发生冲突,实际中能用这种哈希函数情况极少,77/98,2、数字分析法,结构：对关键字进行分析，取关键字若干位或其组合作哈希地址,适于关键字位数比哈希地址位数大，且可能出现关键字事先知道情况,例 有80个统计，关键字为8位十进制数，哈希地址为2位十进制数,8 1 3 4 6 5 3 2,8 1 3 7 2 2 4 2,8 1 3 8 7 4 2 2,8 1 3 0 1 3 6 7,8 1 3 2 2 8 1 7,8 1 3 3 8 9 6 7,8 1 3 6 8 5 3 7,8 1 4 1 9 3 5 5,.,.,分析：,只取8,只取1,只取3、4,只取2、7、5,数字分布近乎随机,所以：取任意两位或两位,与另两位叠加作哈希地址,78/98,3、平方取中法,结构：取关键字平方后中间几位作哈希地址,适于不知道全部关键字情况,折叠法,结构：将关键字分割成位数相同几部分，然后取这几部分叠加和（舍去进位）做哈希地址,种类,移位叠加：将分割后几部分低位对齐相加,间界叠加：从一端沿分割界往返折送，然后对齐相加,适于关键字位数很多，且每一位上数字分布大致均匀情况,例 关键字为：0442205864，哈希地址位数为4,5 8 6 4,4 2 2 0,0 4,1,0 0 8 8,H(key)=0088,移位叠加,5 8 6 4,0 2 2 4,0 4,6 0 9 2,H(key)=6092,间界叠加,79/98,4、除留余数法,结构：取关键字被某个小于哈希表表长m,数p除后所得余数作哈希地址，即H(key)=key MOD p，p,m,特点,简单、惯用，可与上述几个方法结合使用,p,选取很主要；p选不好，轻易产生同义词,5、随机数法,结构：取关键字随机函数值作哈希地址，即H(key)=random(key),适于关键字长度不等情况,80/98,选取哈希函数，考虑以下原因：,计算哈希函数所需时间,关键字长度,哈希表长度（哈希地址范围）,关键字分布情况,统计查找频率,81/98,3.2 处理冲突方法,开放定址法,方法：当冲突发生时，形成一个探查序列；沿此序列逐一地址探查，直到找到一个空位置（开放地址），将发生冲突统计放到该地址中，即Hi=(H(key)+di)MOD m，i=1,2,k(k,m-1),其中：H(key),哈希函数,m哈希表表长,di增量序列,分类,线性探测再散列：di=1,2,3,m-1,二次探测再散列：di=1,-1,2,-2,3,k(km/2),伪随机探测再散列：di=伪随机数序列,82/98,例 表长为11哈希表中已填相关键字为17，60，29统计，,H(key)=key MOD 11,现有第4个统计，其关键字为38，,按三种处理冲突方法，将它填入表中,0 1 2 3 4 5 6 7 8 9 10,60 17 29,(,1,)H(38)=38 MOD 11=5,冲突,H,1,=(5+1)MOD 11=6,冲突,H,2,=(5+2)MOD 11=7,冲突,H,3,=(5+3)MOD 11=8,不冲突,38,(,2,)H(38)=38 MOD 11=5,冲突,H,1,=(5+1,)MOD 11=6,冲突,H,2,=(5-1,)MOD 11=4,不冲突,38,(,3,)H(38)=38 MOD 11=5,冲突,设伪随机数序列为9，则：,H,1,=(5+9)MOD 11=3,不冲突,38,83/98,再哈希法,方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key)i=1,2,k,其中：Rhi不一样哈希函数,特点：计算时间增加,链地址法,方法：将全部关键字为同义词记录存储在一个单链表中，并用一维数组存放头指针,84/98,例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79),哈希函数为：H(key)=key MOD 13,用链地址法处理冲突,0 1 2 3 4 5 6 7 8 9 10 11 12,14,1,27,79,68,55,19,84,20,23,10,11,85/98,3.3 哈希查找过程及分析,哈希查找过程,给定k,值,计算H(k),此地址为空,关键字=k,查找失败,查找成功,按处理冲突,方法计算Hi,Y,N,Y,N,86/98,哈希查找分析,哈希查找过程仍是一个给定值与关键字进行比较过程,评价哈希查找效率仍要用ASL,哈希查找过程与给定值进行比较关键字个数取决于：,哈希函数,处理冲突方法,哈希表填满因子,=表中填入统计数/哈希表长度,87/98,例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79),哈希函数为：H(key)=key MOD 13,哈希表长为m=16，,设每个统计查找概率相等,(1)用线性探测再散列处理冲突，即Hi=(H(key)+di)MOD m,H(,55,)=3,冲突，H1=(3+1)MOD16=4,冲
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
