1、 查找表：查找表：是一种以集合为逻辑结构，以查找为核心运是一种以集合为逻辑结构，以查找为核心运 算，同时包括其他运算的数据结构。算，同时包括其他运算的数据结构。8.1 8.1 基本概念基本概念查找表查找表静态查找表静态查找表动态查找表动态查找表1.建表：建表：Create(st)2.查找：查找：Search(st,k)3.读表元：读表元：Get(st,pos)2.查找：查找：Search(st,k)3.读表元：读表元：Get(st,pos)1.初始化：初始化：Initiate(st)4.插入：插入：Insert(st,k)5.删除：删除：Delete(st,k)8.2 8.2 静态查找表静态查
2、找表1)1)顺序表上的查找：顺序表上的查找：以顺序表作为存储结构，然后在这以顺序表作为存储结构，然后在这个存储结构上实现静态查找表的基本运算。个存储结构上实现静态查找表的基本运算。顺序表类型定义如下：顺序表类型定义如下：#define maxsize 静态查找表的表长静态查找表的表长typedef struct keytype key;/关键字关键字 /其他域其他域 rec;typedef rec sqtablemaxsize+1;int n;/最后一个数据元素的下标最后一个数据元素的下标顺序查找过程：顺序查找过程：假定该查找表有假定该查找表有n n个记录，首先将要查个记录，首先将要查找的那个
3、关键字赋给实际上并不存在的第找的那个关键字赋给实际上并不存在的第n+1n+1个记录个记录的关键字域，然后从头开始一个一个的向下查找，用的关键字域，然后从头开始一个一个的向下查找，用i i来计数来计数,查到就送出来看查到就送出来看i i是第几个，若是第几个，若i=ni=n，则查找，则查找成功，若成功，若i=n+1i=n+1则查找失败。则查找失败。void seqsrch(sqtable r，keytype k)/在长度为在长度为n的表的表r中查找关键字为中查找关键字为k的元素，的元素，rn为表尾的扩为表尾的扩 充充;i指示查找结果指示查找结果 rn.key=k;i=0;/给监督哨赋值给监督哨赋值
4、 while(ri.key!=k)i+;if(ikrmid.keyk，则，则k k必在较低标号的那一半表中，必在较低标号的那一半表中，令令high=mid-1high=mid-13)3)若若rmid.keykrmid.keyhigh(lowhigh(查查 找失败找失败)为止。为止。例：给出表元素关键字为：例：给出表元素关键字为：05,13,19,21,37,56,64,75,80,88,921.查找关键字查找关键字k=21 的情况的情况(1)low=1;high=11;mid=(1+11)div 2=605 13 19 21 37 56 64 75 80 88 92lowmidhigh因为因为
5、rmid.keyk，所以向左找，令，所以向左找，令high=mid-1=5(2)low=1;high=5;mid=(1+5)div 2=305 13 19 21 37 56 64 75 80 88 92lowmidhigh因为因为rmid.keyk，所以向右找，令，所以向右找，令low=mid+1=4(3)low=4;high=5;mid=(4+5)div 2=405 13 19 21 37 56 64 75 80 88 92lowmidhigh因为因为rmid.key=k，查找成功，所查元素在表中的序号为，查找成功，所查元素在表中的序号为mid 的值的值(1)low=1;high=11;mi
6、d=(1+11)div 2=6因为因为rmid.keyk，所以向右找，令，所以向右找，令low=mid+1=7(2)low=7;high=11;mid=(7+11)div 2=905 13 19 21 37 56 64 75 80 88 92lowmidhigh因为因为rmid.keyk，所以向左找，所以向左找，high=mid-1=92.查找关键字查找关键字k=85 的情况的情况05 13 19 21 37 56 64 75 80 88 92lowmidhigh因为因为lowhigh，所以查找失败，所以查找失败void Binsrch(sqtable r，keytype k)/在长度为在长度
7、为n的有序表的有序表r中查找关键字为中查找关键字为k的元素，查到后输出的元素，查到后输出 low=1；high=n；/置初值置初值 while(lowrmid.key)low=mid+1；/向右找向右找 else high=mid-1；/向左找向左找 if(lowhigh)printf(no succn)；/lowhigh，查找不成功，查找不成功Void BinSearch(sqtable r;keytype k;int l,h)low=l;high=h;if highrmid.key:low=mid+1;BinSearch(r,k,low,high);break;case k=rmid.ke
8、y:printf(succ i=%dn，mid)；return;case krmid.key:high=mid-1;BinSearch(r,k,low,high);break;递归算法描述如下：递归算法描述如下：算法的性能分析：算法的性能分析：以上面的以上面的11个元素的查找表为例，找到第个元素的查找表为例，找到第6个元素仅需比较个元素仅需比较1次；找到第次；找到第3个和第个和第9个元素需比较个元素需比较2次；找到第次；找到第1,4,7和和10个元素需个元素需比较比较3次；找到第次；找到第2,5,8和和11个元素需比较个元素需比较4次。上面的查找过程可次。上面的查找过程可以用下图所示的一棵二叉
9、树来表示。以用下图所示的一棵二叉树来表示。6391471011258树中每一个结点表示树中每一个结点表示表中的一个数据元素，表中的一个数据元素，结点中的值为该元素结点中的值为该元素在表中的位置在表中的位置折半查找的最大查找长度为折半查找的最大查找长度为 log2n+1 找到元素的过程：正好是从根节点一直走到某个节点的路径，找到元素的过程：正好是从根节点一直走到某个节点的路径，因此所用的比较次数最多等于树的深度。由此看来，无论元素找因此所用的比较次数最多等于树的深度。由此看来，无论元素找到或找不到到或找不到,查找某一元素的比较次数最多等于树的深度，即查找某一元素的比较次数最多等于树的深度，即 l
10、og2n+1 。那么引出一个问题，折半查找的平均查找长度是多少那么引出一个问题，折半查找的平均查找长度是多少?ASLnS=CiPi=1/njASLnS=CiPi=1/nj*2 2j-j-1 i=1i=1n nj=1j=1h h=(n+1/n)=(n+1/n)*loglog2 2(n+1)-1(n+1)-1那么表的长度一定为那么表的长度一定为n=2n=2h h-1,-1,我们假定表中每个元素的查我们假定表中每个元素的查找概率相等找概率相等.(Pi=1/n),.(Pi=1/n),则平均查找长度为则平均查找长度为:我们用深度为我们用深度为h h的满二叉树描述折半查找来进行分析。的满二叉树描述折半查找
11、来进行分析。满二叉树的特点是：满二叉树的特点是：层次为层次为1 1的结点有的结点有1 1个个;层次为层次为2 2的结点有的结点有2 2个个;,层次为层次为h h的结点为的结点为2 2h-1h-1 个个 。若是满二叉树则节点数若是满二叉树则节点数n=2n=2h h-1-13)3)分块查找分块查找:这种查找方法是表里的元素均匀的分这种查找方法是表里的元素均匀的分成若干块，块与块之间是有序的，块中的元素是成若干块，块与块之间是有序的，块中的元素是无序的，这种查找方法又称为索引顺序查找。无序的，这种查找方法又称为索引顺序查找。在分块查找中对每一块建立一个索引项，其中包括两项内容：在分块查找中对每一块建
12、立一个索引项，其中包括两项内容：关键字项关键字项(其值为最大关键字或最小关键字其值为最大关键字或最小关键字)和指针项和指针项(指示该块指示该块的第的第1 1个记录在表中的位置个记录在表中的位置)。索引表按关键字有序，表分块有序。索引表按关键字有序，表分块有序。分块有序：指第二块中所有记录的关键字均大于分块有序：指第二块中所有记录的关键字均大于(或小于或小于)第第一块中最大一块中最大(或最小或最小)关键字，第三块中的所有关键字均大于关键字，第三块中的所有关键字均大于(或或小于小于)第二块中的最大第二块中的最大(或最小或最小)关键字关键字,以此类推。以此类推。例例:有一个表有一个表,各元素的关键字
13、为各元素的关键字为:22,12,13,9,8,33,42,44,38,24,48,60,58,74,47 22,12,13,9,8,33,42,44,38,24,48,60,58,74,47 把它平均分成三块，按上升的次序排列，如下图所示：把它平均分成三块，按上升的次序排列，如下图所示：2212139833424438244860587447123456789101112131415第一块第一块第二块第二块第三块第三块1611224474关键字表关键字表小小大大指针表指针表:应该指向各块的第一个关键字。应该指向各块的第一个关键字。分成三块分成三块每块每块5 5个个关键字关键字分块查找的方法分块
14、查找的方法:1)1)由于索引表按关键字有序，则确定由于索引表按关键字有序，则确定k k在哪一块的查找在哪一块的查找 可以用顺序查找，也可用折半查找。可以用顺序查找，也可用折半查找。分块查找的平均查找长度应该是前两者之和：分块查找的平均查找长度应该是前两者之和：即：即：ASLASLbsbs=Lb+Lw=Lb+Lw用顺序查找方法用顺序查找方法,确定所在的块确定所在的块,则则 Lb=1/bj Lb=1/bj j=1j=1b b用顺序查找方法用顺序查找方法,查找的元素所在位置查找的元素所在位置,则则Lw=1/siLw=1/sii=1i=1s s 已知表的长度为已知表的长度为n,n,分成分成b b小块小
15、块,每块有每块有s s个元素个元素,那那么么b=n/s.b=n/s.若表中各元素的查找概率相等若表中各元素的查找概率相等,那么每块的那么每块的查找概率为查找概率为1/b,1/b,块中每个元素的查找概率为块中每个元素的查找概率为1/s.1/s.Lb:Lb:为查找所在块的平均查找长度。为查找所在块的平均查找长度。Lw:Lw:为块中查找元素的平均查找长度。为块中查找元素的平均查找长度。2)2)块中的记录是任意排列的，在块中只能用顺序查找。块中的记录是任意排列的，在块中只能用顺序查找。ASL ASLbsbs=1/bj+1/si=(b+1)/2+(s+1)/2=1/bj+1/si=(b+1)/2+(s+
16、1)/2 =1/2(n/s+s+2)=1/2(n/s+s)+1 =1/2(n/s+s+2)=1/2(n/s+s)+1 j=1j=1b bi=1i=1s s可以证明可以证明:当当s=s=时，平均查找长度最小时，平均查找长度最小=+1=+1由上式可以看出，分块查找的平均查找长度不仅和表由上式可以看出，分块查找的平均查找长度不仅和表的长度的长度n n有关，而且和每一块中的元素个数有关，而且和每一块中的元素个数s s有关。有关。n nn n用折半查找确定所在的块，则分块查找的平均查找长用折半查找确定所在的块，则分块查找的平均查找长度为度为ASLASLbs bs=log=log2 2(b+1)-1+(s
17、+1)/2(b+1)-1+(s+1)/2 =log =log2 2(n/s+1)+(s-1)/2(n/s+1)+(s-1)/2三种查找方法的比较三种查找方法的比较:就就平均查找长度平均查找长度而言，折半查找最小，分块查找次而言，折半查找最小，分块查找次之，顺序查找最大。之，顺序查找最大。就就表的结构表的结构而言，顺序查找对有序表和无序表均可而言，顺序查找对有序表和无序表均可应用，折半查找仅适用有序表，而分块查找要求表中数应用，折半查找仅适用有序表，而分块查找要求表中数据是分块有序的，即需要把表分成若干块，块与块之间据是分块有序的，即需要把表分成若干块，块与块之间的记录按关键字有序。的记录按关键
18、字有序。就就表的存储结构表的存储结构而言，顺序查找和分块查找对两种而言，顺序查找和分块查找对两种存储结构存储结构-向量和链表均适用，而折半查找只适用于以向量和链表均适用，而折半查找只适用于以向量做存储结构的的表，这就要求表中的元素基本不变，向量做存储结构的的表，这就要求表中的元素基本不变，否则，当进行插入和删除运算时为保持表的有序性，便否则，当进行插入和删除运算时为保持表的有序性，便要移动元素，这在一定程度上降低折半查找的效率。要移动元素，这在一定程度上降低折半查找的效率。8.3 8.3 动态查找表动态查找表二叉排序树：二叉排序树：或者是一棵空树，或者是具有下列性质的或者是一棵空树，或者是具有
19、下列性质的二叉树：二叉树：1)1)若它的左子树不空，则它的左子树上所有结点的若它的左子树不空，则它的左子树上所有结点的值均小于根结点的值；值均小于根结点的值；2)2)若它的右子树不为空，则它的右子树上所有结点若它的右子树不为空，则它的右子树上所有结点的值均大于或等于它的根结点的值；的值均大于或等于它的根结点的值；3)3)它的左、右子树均为二叉排序树。它的左、右子树均为二叉排序树。二叉排序树的构造方法：二叉排序树的构造方法：设设R=R1,R2,R=R1,R2,Rn,Rn为一数列为一数列,按下面的原则建立二叉树：按下面的原则建立二叉树：1)1)令令R1R1为二叉树的根；为二叉树的根；2)2)若若R
20、2R1R2R1，则令，则令R2R2为为R1R1的左子树的根结点，否则令的左子树的根结点，否则令 R2R2为为R1R1的右子树的根结点；的右子树的根结点；3)3)对对R3,R4,R3,R4,RnRn重复上述步骤重复上述步骤2)2)；例：给定例：给定R=10,18,3,8,12,2,7,3R=10,18,3,8,12,2,7,3按上面的原则构造二按上面的原则构造二 叉排序树如下：叉排序树如下：R4R7R2R2R2R2比比R1R1大大1018R3R3R1R3R110183R4R1 R4R3 R4R3 右边右边101838R5R5R1 R5R1 右边右边R5R2 R5R2 左边左边10183812R6
21、R6R1 R6R1 左边左边R6R3 R6R3 左边左边101838122R1R1为根节点为根节点R1101018381227R7R1 R7R3 R7R3 右边右边R&R4 R&R4 左边左边10183812273R8R8R1 R8R3 R8R3 右边右边R8R4 R8R4 左边左边R8R7 R8datadata)bsinsert(s，t-lchild);else bsinsert(s，t-rchild);/bsinsertvoid sortree(m,rm,p)/建立一个有建立一个有m个结点个结点ri(0=idata=r0;q-lchild=NULL;q-rchild=NULL;p=q;fo
22、r(i=1;idata=ri;q-lchild=NULL;q-rchild=NULL;bsinsert(q，p);/sorttree二叉排序树的查找二叉排序树的查找 已知要找的那个记录的关键字已知要找的那个记录的关键字k,k,从根结点的关键字从根结点的关键字开始比较，有下列三种情况：开始比较，有下列三种情况：1)1)若两者相等若两者相等,则说明查找成功则说明查找成功,根结点的记录为所根结点的记录为所找记录找记录;2)2)若若k k小于根结点的关键字，则继续查找左子树小于根结点的关键字，则继续查找左子树;3)3)若若k k大于根结点的关键字，则继续查找右子树大于根结点的关键字，则继续查找右子树;
23、4)4)若二叉树为空，则查找失败。若二叉树为空，则查找失败。void sortsrch(bitreptr t,ElemType k)/在指针在指针t所指的二叉排序树中，查找关键字为所指的二叉排序树中，查找关键字为k的结点的结点 if t=NULL printf(“unsucc”);/树已空查找不成功树已空查找不成功 else if(k=t-key)printf(“succ”);outdata();/查找成功，并输出信息查找成功，并输出信息 else if(kkey)sortsrch(t-lchild,k);else sortsrch(t-rchild,k);非递归算法如下：非递归算法如下：vo
24、id search(bitreptr I,bitreptr t,ElemType k)/在二叉排序树在二叉排序树t中查找中查找k。每个结点有三个字段：。每个结点有三个字段：lchild，key，rchild。若。若k不不/在在t中，则送回中，则送回B=1。否则送回。否则送回i，结果，结果i-key=k。/设设lchild（空二叉树）（空二叉树）=rchild（空二叉树）（空二叉树）=0 i=t;B=1;/当当B=0时，查找成功，否则失败时，查找成功，否则失败 while(i!=NULL)&(B=1)if(kkey)i=i-lchild;/查找左子树查找左子树 else if(k=i-key)B
25、=0;printf(“succ%d”,i);else i=i-rchild;/查找右子树查找右子树 /search二叉排序树在查找过程中的插入、删除二叉排序树在查找过程中的插入、删除1)二叉排序树的插入：二叉排序树的插入：给定关键字给定关键字x,x,如果如果x x在二叉排序树中，送在二叉排序树中，送 出指向出指向x x所在结点的指针，否则将所在结点的指针，否则将x x插入到二叉排序树的合适位插入到二叉排序树的合适位 置上。置上。void BST(bitreptr&t,ElemType x)/在二叉排序树中查找一个结点的关键字在二叉排序树中查找一个结点的关键字x，若，若x已不在表中，则将它放在适
26、当已不在表中，则将它放在适当的位置。当的位置。当B=0时，查找成功，否则没查到时，查找成功，否则没查到 j=t;B=1;p=NULL;while(j!=NULL)&(B=1)if(xkey)p=j;j=j-lchild;else if(x=j-key)B=0;printf(“succ，%d”，j);else p=j;j=j-rchild;if(B=1)j=new btnode;j-key=x;j-lchild=NULL;j-rchild=NULL;if(t=NULL)t=j;else if(xkey)p-lchild=j;else if(xp-key)p-rchild=j;2)2)二叉排序树的
27、删除：二叉排序树的删除：在二叉排序中删除某个结点，删在二叉排序中删除某个结点，删 除此结点后仍保持二叉排序树的性质。除此结点后仍保持二叉排序树的性质。下面这棵二叉排序树，我们要删除结点下面这棵二叉排序树，我们要删除结点2 2：2 2是根结点，它有左、右子树，要删除是根结点，它有左、右子树，要删除2,2,就要找一就要找一个新的根结点，从哪儿找呢个新的根结点，从哪儿找呢?从左子树，在左子树中找从左子树，在左子树中找一个值最大的结点，此结点仅次于根节点，比右子树的一个值最大的结点，此结点仅次于根节点，比右子树的所有结点都小，让这个结点做为根结点。所有结点都小，让这个结点做为根结点。426131241
28、6312pq,js 在算法中用了在算法中用了4个指针：个指针：j:指向被删除结点指向被删除结点;p:指向被删除结点的双亲指向被删除结点的双亲;s:指向新选择的根结点指向新选择的根结点;q:指向新选择的根结点的双亲指向新选择的根结点的双亲;下面分四种情况进行讨论：下面分四种情况进行讨论：被删结点是叶子结点被删结点是叶子结点 即即 j-lchild=NULL;j-rchild=NULL s=NULL为选择的合适结点为选择的合适结点 由于删去叶子结点不影响二叉排序树的结构和性质，由于删去叶子结点不影响二叉排序树的结构和性质，所以只需修改其双亲结点的指针即可。若被删结点是所以只需修改其双亲结点的指针即
29、可。若被删结点是p 的左子树，则的左子树，则p-lchild=s;若被删结点是若被删结点是p的右子树，的右子树，则则p-rchild=s。被删结点不是叶子，被删结点不是叶子，j无左，仅有右子树，则无左，仅有右子树，则 s=j-rchild,s做做p的左的左(或右或右)子树。子树。41361243612 被删结点不是叶子，被删结点不是叶子，j有左，无右子树，则有左，无右子树，则 s=j-lchild,s做做p的左的左(或右或右)子树子树pjs43261242612pjs j既有左，又有右。则沿既有左，又有右。则沿j的左子树的右子树方向找，的左子树的右子树方向找，一直找到按中序遍历一直找到按中序遍
30、历j的直接前趋结点。此结点作为的直接前趋结点。此结点作为 新选的根结点新选的根结点s,然后做相应的指针修改。然后做相应的指针修改。2010306153913188pjqs20930615381318在上图中，在上图中，s-rchild=NULL;s-lchild!=NULL修改四个指针：修改四个指针：1)s-rchild=j-rchild;2)q-rchild=s-lchild;3)s-lchild=j-lchild;4)p-lchild=s;201030615391318pjqs2093061531318在上图中，在上图中，s-rchild=s-lchild=NULL,仍做前面的四个操作。仍
31、做前面的四个操作。2093061531318pj,qs206303151318上图中，上图中，s-rchild=NULL,且且q=j,修改两个指针：修改两个指针：1)s-rchild=j-rchild;2)p-lchild=s;下面给出在二叉排序树下面给出在二叉排序树T中查找结点中查找结点j,使使j-key=x，如，如果果x在在T中，则删除中，则删除x结点，否则结点，否则,送出送出B=1，说明此树中，说明此树中无被删结点的算法：无被删结点的算法：void det(bitreptr t,ElemType x)/j指向被删结点，指向被删结点，p指向其双亲，假设树不空指向其双亲，假设树不空 j=t;
32、B=1;while(j!=NULL)&(B=1)if(xkey)p=j;j=j-lchild;else if(x=j-key)B=0;else if(xj-key)p=j;j=j-rchild;/以上过程是查找过程以上过程是查找过程 if(B=0)if(j-lchild=NULL)s=j-rchild;while(s-rchild=NULL)q=s;s=s-rchild;if(q=j)s-rchild=j-rchild;if(j=p-lchild)p-lchild=s;else p-rchild=s;if(j=p-lchild)p-lchild=s;else p-rchild=s;if(j=p
33、-lchild)p-lchild=s;else p-rchild=s;if(j=p-lchild)p-lchild=s;else p-rchild=s;else if(j-rchild=NULL)s=j-lchild;else q=j;s=q-lchild;else s-rchild=j-rchild;q-rchild=s-lchild;s-lchild=j-lchild;平衡二叉树平衡二叉树：或者是一棵空树，或者是具有下列性质的或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过
34、树和右子树的深度之差的绝对值不超过1 1。例例:2-1=12-1=10-0=00-0=01-0=11-0=10-0=00-0=0平衡二叉树平衡二叉树2-3=-12-3=-11-1=01-1=00-0=00-0=00-2=-20-2=-21-0=11-0=10-0=00-0=0非平衡二叉树非平衡二叉树ABCDABCDFG0-0=00-0=0E平衡因子：二叉树中任一结点的左子树的深度与它的右平衡因子：二叉树中任一结点的左子树的深度与它的右子树的深度之差称为平衡因子。子树的深度之差称为平衡因子。二叉排序树的平衡化二叉排序树的平衡化 假设表中的关键字序列为假设表中的关键字序列为(13,24,37,90
35、,53)(13,24,37,90,53)空树和一个结点空树和一个结点 的的二叉树显然是平衡二叉树二叉树显然是平衡二叉树 .插入插入2424后仍平衡后仍平衡131324-101324 2437RRRR型即逆时针旋转型即逆时针旋转 插入插入 后结点后结点 的平衡因子为的平衡因子为0-2=-20-2=-2，不平衡，不平衡37130-1-1-2-2132437把把 从从 的右下侧的右下侧左转到左转到 的右上侧的右上侧241313原来原来 的左为的左为 的右的右,新的新的 的左为的左为24132413插入插入90,5390,53后后,又失去平衡又失去平衡,可经过下列步骤转化为平衡二叉树可经过下列步骤转化
36、为平衡二叉树13243790532_02_101324379053RLRL型的第一次旋转型的第一次旋转(顺时针顺时针)1324539037RLRL型的第二次旋转型的第二次旋转(逆时针逆时针)第一次旋转第一次旋转(顺时针顺时针)以以 为轴心为轴心,把把 从从 的右上的右上,转到转到的右下的右下,的右是的右是 ,的右为的右为 ,原原 的右变成新的右变成新 的左。的左。53905353375353905390 以以 为轴心为轴心,把把 从从 的左上转到的左上转到 的左下的左下,使得使得 的左的左是是 ;右是右是 ，原，原 的左变成了的左变成了 的右。的右。533753535337905337 一般情
37、况下，假设由于二叉排序树上插入结点而失去一般情况下，假设由于二叉排序树上插入结点而失去平衡的最小子树的根结点指针为平衡的最小子树的根结点指针为a a（即（即a a是离插入结点最是离插入结点最近近,且平衡因子绝对值超过且平衡因子绝对值超过1 1的祖先结点），则失去平衡的祖先结点），则失去平衡后进行调整的规律可归纳为下列四种情况后进行调整的规律可归纳为下列四种情况:RRRR型平衡旋转型平衡旋转:ab a1 b1 br-2-1hh-1h-1插入节点插入节点 把结点把结点b b从从a a的右下侧逆时针的右下侧逆时针(左转左转)转到转到a a的右上侧，的右上侧，原原b b的左成为的左成为a a的右，新的
38、右，新b b的左为的左为a a。ba br a1 b1RR0hh-10h-12.LL2.LL型平衡旋转型平衡旋转:LL21hh-1h-1ab ar br b1 把结点把结点b b从左下侧顺转从左下侧顺转(右转右转)转到转到a a的左上侧的左上侧,原原b b的右的右成为成为a a的左的左,新新b b的右为的右为a a。3.RL3.RL型平衡旋转型平衡旋转:RL(RL(顺时针顺时针)-21h-11h-1 a1 c c1 cr brh-1h-2aba b1 br ar00bhh-1 c1 a1 cr bracbh-1h-2h-1h-1-1-1-2 以以c c为轴心，把为轴心，把b b从从c c的右上
39、侧顺时针（右转的右上侧顺时针（右转)到到c c的右的右下侧，从而下侧，从而a a的右是的右是c c，c c的右是的右是b b，原，原c c的右变成的右变成b b的左。的左。以以c c为轴心，把为轴心，把a a从从c c的左上方，转到的左上方，转到c c的左下方，使的左下方，使得得c c的左是的左是a a，右是，右是b b，原，原c c的左子树变成的左子树变成a a的右。的右。RL(RL(逆时针逆时针)4.LR4.LR型平衡旋转型平衡旋转:以以c c为轴心把为轴心把b b从从c c的左上侧，逆时针（左转）到的左上侧，逆时针（左转）到c c的左的左下侧，从而下侧，从而a a的左是的左是c,cc,c
40、的左是的左是b b，原，原c c的左变成新的左变成新b b的右。的右。c1 a1 cr bracbh-1h-2h-1h-1-1-1-2 c1 a1 cr brcabh-1h-2h-1-100LR(LR(逆时针逆时针)2-11h-1h-1h-2 ar c1 cr b1h-1LR(LR(顺时针顺时针)再以再以c c为轴心，把为轴心，把a a从从c c的左上方转到的左上方转到c c的右下方，使得的右下方，使得c c的右是的右是a a，左是，左是b b，原，原c c的右子树变成的右子树变成a a的左。的左。abc c1 ar cr blacbh-1h-1h-2h-1022a c1 ar cr blcb
41、h-1h-1h-2h-1022 c1 ar cr blcbah-10h-2h-1-10例例1 将关键字集合将关键字集合K=60，40，49，23，25，13，95，196，856006040106040490-12604049000LR60404901123060404902223-1250602549001230400LR060254900123400602549012231400130LL602549002314013000602549-1-2231401300-295-21260RR9525490-2231401300-2126160085-1RL9525600-123149130001
42、260400850B-B-树树B-B-树：一棵树：一棵m m阶的阶的B-B-树，或为空树，或为具有下列性质树，或为空树，或为具有下列性质 的的m m叉树：叉树：1)1)树中每个结点有树中每个结点有m m个儿子；个儿子；2)2)除根和叶子结点之外的结点有除根和叶子结点之外的结点有Upper(m/2)Upper(m/2)个儿子；个儿子；3)3)根结点至少要有两个儿子根结点至少要有两个儿子(除非它本身又是一个除非它本身又是一个 叶子叶子)；4)4)所有的非终端结点中包含下列信息数据所有的非终端结点中包含下列信息数据(n,A(n,A0 0,k k1 1,A,A1 1,k k2 2,k,kn n,A,A
43、n n)；n n：本结点中关键字的个数：本结点中关键字的个数m-1m-1 k ki i：关键字，从左到右其值按递增次序排列：关键字，从左到右其值按递增次序排列 A Ai i：指向一个所有关键字都在：指向一个所有关键字都在k ki i和和k ki+1i+1间的子树形间的子树形 5)5)所有的叶子结点都在同一层次上，并且不带信所有的叶子结点都在同一层次上，并且不带信 息息(可以看作是查找失败的结点，实际上这些结可以看作是查找失败的结点，实际上这些结 点不存在，指向这些结点的指针为空点不存在，指向这些结点的指针为空)；118111127135139199243783475364abcdefgh上图中
44、上图中,结点形式为结点形式为:n n 指针指针 关键字关键字 指针指针 关键字关键字.p0p0k1k1p1p1k2k2 每一个结点每一个结点(除了根结点和叶子除了根结点和叶子),),有有Upper(4/2)Upper(4/2)到到4 4个儿子，个儿子，所以可以有所以可以有1 1，2 2或或3 3个关键字，根结点允许有个关键字，根结点允许有1 1至至3 3关键字，此时关键字，此时所有的所有的叶子都在第四层上。叶子都在第四层上。例：下图所是为一棵例：下图所是为一棵4阶的阶的B-树，深度为树，深度为4B-B-树的查找过程：树的查找过程：B-B-树的查找是一个顺指针查找结点和在结点的关树的查找是一个顺
45、指针查找结点和在结点的关键字中顺序查找交叉进行的过程。键字中顺序查找交叉进行的过程。结点类型说明如下：结点类型说明如下：typedef struct mbnode int keynum;struct mbnode*parent;KeyType keysm-1;struct mbnode*ptrsm;*mblink;typedef struct mblink*p;int i;int tag;Result;查找算法如下：查找算法如下：Result mbsearch(mblink t,KeyType k)p=t;q=NULL;key0=-max;/key0.m为关键字辅助数组为关键字辅助数组 whi
46、le(p!=NULL)n=p-keynum;keyn+1=max;for(j=0;jkeysj;for(j=0;jptrsj;/a0.m为指针型辅助数组为指针型辅助数组 i=sqSearch(key,k);/在数组在数组key中进行顺序查找直到中进行顺序查找直到keyikkkeyi+1 if(keyi=k)Rst-p=p;Rst-i=i;Rst-tag=1;return(Rst);/查找成功查找成功 q=p;p=ai;/继续向下查找继续向下查找 Rst-p=q;Rst-i=i;Rst-tag=0;return(Rst);/查找失败查找失败,其中其中q,i指示等于指示等于k的关键字在的关键字在B
47、-树中树中 应插入的位置应插入的位置在在B-B-树上进行查找所需时间的分析树上进行查找所需时间的分析 从上述过程可知，在从上述过程可知，在B-B-树上进行查找所需时间取决于两个因树上进行查找所需时间取决于两个因素：素：等于给定值的关键字所在的层次数等于给定值的关键字所在的层次数;结点中关键字的数目。结点中关键字的数目。(较大时可用折半查找较大时可用折半查找)显然，节点所在的最大层次数即为树的深度。那么，含有显然，节点所在的最大层次数即为树的深度。那么，含有N N个个关键字的关键字的m m阶阶B-B-树的最大深度是多少？树的最大深度是多少？根据根据B-B-树的定义树的定义 第一层至少有第一层至少
48、有1 1个结点个结点 第二层至少有第二层至少有2 2个结点个结点 第三层至少有第三层至少有2 2*m/2 m/2 个结点个结点 (因为除根之外的每个非终端结点至少有因为除根之外的每个非终端结点至少有 m/2 m/2 个个)第四层至少有第四层至少有2 2*m/2 m/2 2 2个结点个结点最末层最末层L+1L+1层有层有2 2*m/2 m/2 L-1L-1个结点个结点 (因为最末层为叶子因为最末层为叶子,m,m阶阶B B树中有树中有N N个关键字个关键字,则叶子结点为则叶子结点为N+1N+1个个,由此有由此有 N+12N+12*(m/2)(m/2)L-1L-1 N+1N+12 2(m/2)(m/
49、2)L-1L-1两边取对数两边取对数log()log()N+1N+12 2(L-1)(L-1)log(m/2)log(m/2)L-1L-1log()log()N+1N+12 2log(m/2)log(m/2)换底换底=log ()log ()m/2m/2N+1N+12 2loglogm/2m/22 2log ()log ()m/2m/2m/2m/2loglogm/2m/22 2=log ()log ()m/2m/2N+1N+12 21 1log ()log ()m/2m/2N+1N+12 2LL log ()log ()m/2m/2N+1N+12 2+1+1 这就是说，在含有这就是说，在含有N
50、 N个关键字的个关键字的B-B-树上，进行查找时，从根树上，进行查找时，从根j j结点到关键字所在结点的路径上涉及的结点数不超过结点到关键字所在结点的路径上涉及的结点数不超过log ()log ()m/2m/2N+1N+12 2+1+1 个个例如例如:当当N=1999998N=1999998且且m=199m=199时时,L,L最多为最多为3 3。这就是说，在最坏情况下，一次查找至多需要存取这就是说，在最坏情况下，一次查找至多需要存取3 3个结点。个结点。B-B-树的插入：树的插入：B-B-树的生成也是从空树起，逐个插入关键字。但由树的生成也是从空树起，逐个插入关键字。但由于于B-B-树结点中的
