《数据结构》课件第8章(查找表)11

查找表：是一种以集合为逻辑结构，以查找为核心运算，同时包括其他运算的数据结构。关键字：用来标识数据元素的数据项，简称键。★8.1基本概念

主关键字：可以唯一标识一个数据元素的关键字。

次关键字：可以标识若干数据元素的关键字。

查找：根据某个给定的K值，在查找表中寻找一个键值等于K的元素，若找到这样的元素，则称查找成功，此时的运算结果为该数据元素在查找表中的位置，否则称查找不成功，运算结果为一特殊标志。查找表静态查找表动态查找表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静态查找表1)顺序表上的查找：以顺序表作为存储结构，然后在这个存储结构上实现静态查找表的基本运算。顺序表类型定义如下：#definemaxsize静态查找表的表长typedefstruct{keytypekey;//关键字

………//其他域}rec;typedefrecsqtable[maxsize+1];intn;//最后一个数据元素的下标顺序查找过程：假定该查找表有n个记录，首先将要查找的那个关键字赋给实际上并不存在的第n+1个记录的关键字域，然后从头开始一个一个的向下查找，用i来计数,查到就送出来看i是第几个，若i<=n，则查找成功，若i=n+1则查找失败。voidseqsrch(sqtabler，keytypek){//在长度为n的表r中查找关键字为k的元素，r[n]为表尾的扩充;i指示查找结果

r[n].key=k;i=0;//给监督哨赋值

while(r[i].key!=k)i++;if(i<n)printf(“succ,i=%d”,i);//查找成功，i指示待查元素在表中位置

elseprintf(“unsucc”);//i=n时表明查找不成功}平均查找长度：为确定某元素在表中某位置所进行的比较次数的期望值。

在长度为n的表中找某一元素，查找成功的平均查找长度:

ASL=∑PiCiPi:为查找表中第i个元素的概率Ci:为查到表中第i个元素时已经进行的比较次数

在顺序查找时，Ci取决于所查元素在表中的位置，

Ci=i,设每个元素的查找概率相等，即Pi=1/n,则:

ASL=∑PiCi=(n+1)/2查找不成功的查找长度为n+1。顺序查找表的优点：算法简单且适应面广，对表的结构无任何要求，无论元素是否按关键字有序都可应用。顺序查找表的缺点：平均查找长度比较大，特别是当n较大时，查找效率较低。2)折半查找(有序表上进行查找)：基本思想：设三个指针low,high和mid分别指示待查有序表的表头，表尾和中间元素，在开始查找时，三个指针的初值分别为：low=1;high=n;mid=(low+high)div2。折半查找是从表的中间元素开始，用待查元素的关键字k和r[mid].key比较，此时有三种情况(假设该查找表按关键字的非递减次序排列)：1)若r[mid].key=k，则查找成功；2)若r[mid].key>k，则k必在较低标号的那一半表中，令high=mid-13)若r[mid].key<k，则k必在较高标号的那一半表中，令low=mid+14)再取中间项进行比较，直到查找成功或low>high(查找失败)为止。例：给出表元素关键字为：{05,13,19,21,37,56,64,75,80,88,92}1.查找关键字k=21的情况(1)low=1;high=11;mid=(1+11)div2=60513192137566475808892lowmidhigh因为r[mid].key>k，所以向左找，令high=mid-1=5(2)low=1;high=5;mid=(1+5)div2=30513192137566475808892lowmidhigh因为r[mid].key<k，所以向右找，令low=mid+1=4(3)low=4;high=5;mid=(4+5)div2=40513192137566475808892lowmidhigh因为r[mid].key=k，查找成功，所查元素在表中的序号为mid的值(1)low=1;high=11;mid=(1+11)div2=6因为r[mid].key<k，所以向右找，令low=mid+1=7(2)low=7;high=11;mid=(7+11)div2=90513192137566475808892lowmidhigh因为r[mid].key<k，所以向右找，令low=mid+1=10(3)low=10;high=11;mid=(10+11)div2=100513192137566475808892lowmidhigh因为r[mid].key>k，所以向左找，high=mid-1=92.查找关键字k=85的情况0513192137566475808892lowmidhigh因为low>high，所以查找失败voidBinsrch(sqtabler，keytypek)//在长度为n的有序表r中查找关键字为k的元素，查到后输出{low=1；high=n；//置初值

while(low<=high){mid=(low+high)/2；

if(k==r[mid].key){printf("succi=%d\n"，mid)；break；}elseif(k>r[mid].key)low=mid+1；//向右找

elsehigh=mid-1；//向左找

}if(low>high)printf("nosucc\n")；//low>high，查找不成功}VoidBinSearch(sqtabler;keytypek;intl,h){low=l;high=h;ifhigh<low{printf("nosucc\n");return；}mid=(low+high)div2;switch(k){casek>r[mid].key:low=mid+1;BinSearch(r,k,low,high);break;casek=r[mid].key:printf("succi=%d\n"，mid)；return;casek<r[mid].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次。上面的查找过程可以用下图所示的一棵二叉树来表示。6391471011258树中每一个结点表示表中的一个数据元素，结点中的值为该元素在表中的位置折半查找的最大查找长度为log2n+1

找到元素的过程：正好是从根节点一直走到某个节点的路径，因此所用的比较次数最多等于树的深度。由此看来，无论元素找到或找不到,查找某一元素的比较次数最多等于树的深度，即log2n+1

。那么引出一个问题，折半查找的平均查找长度是多少?ASLnS=∑CiPi=1/n∑j*2j-1

i=1nj=1h=(n+1/n)*log2(n+1)-1那么表的长度一定为n=2h-1,我们假定表中每个元素的查找概率相等.(Pi=1/n),则平均查找长度为:

我们用深度为h的满二叉树描述折半查找来进行分析。满二叉树的特点是：层次为1的结点有1个;

层次为2的结点有2个;

…,

层次为h的结点为2h-1

个。若是满二叉树则节点数n=2h-13)分块查找:这种查找方法是表里的元素均匀的分成若干块，块与块之间是有序的，块中的元素是无序的，这种查找方法又称为索引顺序查找。

在分块查找中对每一块建立一个索引项，其中包括两项内容：关键字项(其值为最大关键字或最小关键字)和指针项(指示该块的第1个记录在表中的位置)。索引表按关键字有序，表分块有序。

分块有序：指第二块中所有记录的关键字均大于(或小于)第一块中最大(或最小)关键字，第三块中的所有关键字均大于(或小于)第二块中的最大(或最小)关键字…,以此类推。例:有一个表,各元素的关键字为:｛22,12,13,9,8,33,42,44,38,24,48,60,58,74,47}

把它平均分成三块，按上升的次序排列，如下图所示：2212139833424438244860587447123456789101112131415第一块第二块第三块1611224474关键字表小大指针表:应该指向各块的第一个关键字。分成三块每块5个关键字分块查找的方法:1)由于索引表按关键字有序，则确定k在哪一块的查找可以用顺序查找，也可用折半查找。

分块查找的平均查找长度应该是前两者之和：即：ASLbs=Lb+Lw用顺序查找方法,确定所在的块,则Lb=1/b∑j

j=1b用顺序查找方法,查找的元素所在位置,则Lw=1/s∑ii=1s

已知表的长度为n,分成b小块,每块有s个元素,那么b=n/s.若表中各元素的查找概率相等,那么每块的查找概率为1/b,块中每个元素的查找概率为1/s.

Lb:为查找所在块的平均查找长度。

Lw:为块中查找元素的平均查找长度。

2)块中的记录是任意排列的，在块中只能用顺序查找。ASLbs=1/b∑j+1/s∑i=(b+1)/2+(s+1)/2=1/2(n/s+s+2)=1/2(n/s+s)+1

j=1bi=1s可以证明:当s=时，平均查找长度最小=+1由上式可以看出，分块查找的平均查找长度不仅和表的长度n有关，而且和每一块中的元素个数s有关。nn用折半查找确定所在的块，则分块查找的平均查找长度为ASLbs=log2(b+1)-1+(s+1)/2=log2(n/s+1)+(s-1)/2三种查找方法的比较:

就平均查找长度而言，折半查找最小，分块查找次之，顺序查找最大。

就表的结构而言，顺序查找对有序表和无序表均可应用，折半查找仅适用有序表，而分块查找要求表中数据是分块有序的，即需要把表分成若干块，块与块之间的记录按关键字有序。

就表的存储结构而言，顺序查找和分块查找对两种存储结构--向量和链表均适用，而折半查找只适用于以向量做存储结构的的表，这就要求表中的元素基本不变，否则，当进行插入和删除运算时为保持表的有序性，便要移动元素，这在一定程度上降低折半查找的效率。★8.3动态查找表二叉排序树：或者是一棵空树，或者是具有下列性质的二叉树：

1)若它的左子树不空，则它的左子树上所有结点的值均小于根结点的值；

2)若它的右子树不为空，则它的右子树上所有结点的值均大于或等于它的根结点的值；

3)它的左、右子树均为二叉排序树。二叉排序树的构造方法：设R={R1,R2,…,Rn}为一数列,按下面的原则建立二叉树：

1)令R1为二叉树的根；

2)若R2<R1，则令R2为R1的左子树的根结点，否则令

R2为R1的右子树的根结点；

3)对R3,R4,…Rn重复上述步骤2)；例：给定R={10,18,3,8,12,2,7,3}按上面的原则构造二叉排序树如下：R4R7R2R2R2比R1大1018R3R3<R110183R4<R1左边R4>R3右边101838R5R5>R1右边R5<R2左边10183812R6R6<R1左边R6<R3左边101838122R1为根节点R1101018381227R7<R1左边R7>R3右边R&<R4左边10183812273R8R8<R1左边R8>R3右边R8<R4左边R8<R7左边二叉排序树的类型:structtree{intdata;structtree*lchild;structtree*rchild;};typedefstructtreetreenode;typedeftreenode*btree;voidbsinsert(btrees，btree&t)//将指针s所指结点插入到根指针为t的二叉树排序树中去{if(t==NULL)t=s;elseif(s->data<t->data)bsinsert(s，t->lchild);elsebsinsert(s，t->rchild);}//bsinsertvoidsortree(m,r[m],p)//建立一个有m个结点r[i](0<=i<=m-1)的二叉排序树，p为指向二叉树根的指针{q=newtreenode;q->data=r[0];q->lchild=NULL;q->rchild=NULL;p=q;for(i=1;i<m;i++){q=newtreenode;q->data=r[i];q->lchild=NULL;q->rchild=NULL;bsinsert(q，p);}}//sorttree二叉排序树的查找

已知要找的那个记录的关键字k,从根结点的关键字开始比较，有下列三种情况：

1)若两者相等,则说明查找成功,根结点的记录为所找记录;2)若k小于根结点的关键字，则继续查找左子树;3)若k大于根结点的关键字，则继续查找右子树;4)若二叉树为空，则查找失败。voidsortsrch(bitreptrt,ElemTypek)//在指针t所指的二叉排序树中，查找关键字为k的结点{ift==NULLprintf(“unsucc”);//树已空查找不成功

elseif(k==t->key){printf(“succ”);outdata();//查找成功，并输出信息

}elseif(k<t->key)sortsrch(t->lchild,k);elsesortsrch(t->rchild,k);}非递归算法如下：voidsearch(bitreptrI,bitreptrt,ElemTypek)//在二叉排序树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(k<i->key)i=i->lchild;//查找左子树

elseif(k==i->key){B=0;printf(“succ%d”,i);}elsei=i->rchild;//查找右子树

}}//search二叉排序树在查找过程中的插入、删除1)二叉排序树的插入：给定关键字x,如果x在二叉排序树中，送出指向x所在结点的指针，否则将x插入到二叉排序树的合适位置上。voidBST(bitreptr&t,ElemTypex)//在二叉排序树中查找一个结点的关键字x，若x已不在表中，则将它放在适当的位置。当B=0时，查找成功，否则没查到{j=t;B=1;p=NULL;while((j!=NULL)&&(B==1)){if(x<j->key){p=j;j=j->lchild;}elseif(x==j->key){B=0;printf(“succ，%d”，j);}else{p=j;j=j->rchild;}}

if(B==1){j=newbtnode;j->key=x;j->lchild=NULL;j->rchild=NULL;if(t==NULL)t=j;elseif(x<p->key)p->lchild=j;elseif(x>p->key)p->rchild=j;}}2)二叉排序树的删除：在二叉排序中删除某个结点，删除此结点后仍保持二叉排序树的性质。下面这棵二叉排序树，我们要删除结点2：

2是根结点，它有左、右子树，要删除2,就要找一个新的根结点，从哪儿找呢?从左子树，在左子树中找一个值最大的结点，此结点仅次于根节点，比右子树的所有结点都小，让这个结点做为根结点。4261312416312pq,js

在算法中用了4个指针：

j:指向被删除结点;p:指向被删除结点的双亲;s:指向新选择的根结点;q:指向新选择的根结点的双亲;

下面分四种情况进行讨论：①被删结点是叶子结点即j->lchild=NULL;j->rchild=NULL

s=NULL为选择的合适结点由于删去叶子结点不影响二叉排序树的结构和性质，所以只需修改其双亲结点的指针即可。若被删结点是p

的左子树，则p->lchild=s;若被删结点是p的右子树，则p->rchild=s。②被删结点不是叶子，j无左，仅有右子树，则

s=j->rchild,s做p的左(或右)子树。41361243612③被删结点不是叶子，j有左，无右子树，则

s=j->lchild,s做p的左(或右)子树pjs43261242612pjs④j既有左，又有右。则沿j的左子树的右子树方向找，一直找到按中序遍历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,仍做前面的四个操作。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，说明此树中无被删结点的算法：voiddet(bitreptrt,ElemTypex)//j指向被删结点，p指向其双亲，假设树不空{j=t;B=1;while((j!=NULL)&&(B==1)){if(x<j->key){p=j;j=j->lchild;}elseif(x==j->key)B=0;elseif(x>j->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;elsep->rchild=s;if(j==p->lchild)p->lchild=s;elsep->rchild=s;if(j==p->lchild)p->lchild=s;elsep->rchild=s;if(j==p->lchild)p->lchild=s;elsep->rchild=s;elseif(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;

}}平衡二叉树：或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。例:2-1=10-0=01-0=10-0=0平衡二叉树2-3=-11-1=00-0=00-2=-21-0=10-0=0非平衡二叉树ABCDABCDFG0-0=0E平衡因子：二叉树中任一结点的左子树的深度与它的右子树的深度之差称为平衡因子。二叉排序树的平衡化

假设表中的关键字序列为(13,24,37,90,53)①空树和一个结点的二叉树显然是平衡二叉树.②插入24后仍平衡131324-101324

2437RR型即逆时针旋转

③插入后结点的平衡因子为0-2=-2，不平衡37130-1-2132437把从的右下侧左转到的右上侧241313原来的左为的右,新的的左为24132413④插入90,53后,又失去平衡,可经过下列步骤转化为平衡二叉02_101324379053RL型的第一次旋转(顺时针)1324539037RL型的第二次旋转(逆时针)

第一次旋转(顺时针)以为轴心,把从的右上,转到的右下,的右是,的右为,原的右变成新的左。53905353375353905390

以为轴心,把从的左上转到的左下,使得的左是;右是，原的左变成了的右。533753535337905337

一般情况下，假设由于二叉排序树上插入结点而失去平衡的最小子树的根结点指针为a（即a是离插入结点最近,且平衡因子绝对值超过1的祖先结点），则失去平衡后进行调整的规律可归纳为下列四种情况:⒈RR型平衡旋转:aba1b1br-2-1hh-1h-1插入节点

把结点b从a的右下侧逆时针(左转)转到a的右上侧，原b的左成为a的右，新b的左为a。babra1b1RR0hh-10h-12.LL型平衡旋转:LL21hh-1h-1abarbrb1

把结点b从左下侧顺转(右转)转到a的左上侧,原b的右成为a的左,新b的右为a。3.RL型平衡旋转:RL(顺时针)-21h-11h-1a1cc1crbrh-1h-2abab1brar00bhh-1

c1

a1cr

bracbh-1h-2h-1h-1-1-1-2

以c为轴心，把b从c的右上侧顺时针（右转)到c的右下侧，从而a的右是c，c的右是b，原c的右变成b的左。

以c为轴心，把a从c的左上方，转到c的左下方，使得c的左是a，右是b，原c的左子树变成a的右。RL(逆时针)4.LR型平衡旋转:

以c为轴心把b从c的左上侧，逆时针（左转）到c的左下侧，从而a的左是c,c的左是b，原c的左变成新b的右。

c1

a1cr

bracbh-1h-2h-1h-1-1-1-2

c1

a1

cr

brcabh-1h-2h-1-100LR(逆时针)2-11h-1h-1h-2arc1crb1h-1LR(顺时针)

再以c为轴心，把a从c的左上方转到c的右下方，使得c的右是a，左是b，原c的右子树变成a的左。abcc1arcrblacbh-1h-1h-2h-1022ac1arcrblcbh-1h-1h-2h-1022c1arcrblcbah-10h-2h-1-10例1将关键字集合K={60，40，49，23，25，13，95，196，85}6006040106040490-12604049000LR60404901123060404902223-1250602549001230400LR060254900123400602549012231400130LL602549002314013000602549-1-2231401300-295-21260RR9525490-2231401300-2126160085-1RL9525600-123149130001260400850B-树B-树：一棵m阶的B-树，或为空树，或为具有下列性质的m叉树：

1)树中每个结点有≤m个儿子；

2)除根和叶子结点之外的结点有≥Upper(m/2)个儿子；

3)根结点至少要有两个儿子(除非它本身又是一个叶子)；

4)所有的非终端结点中包含下列信息数据(n,A0,k1,A1,

k2,…,kn,An)；

n：本结点中关键字的个数≤m-1

ki：关键字，从左到右其值按递增次序排列

Ai：指向一个所有关键字都在ki和ki+1间的子树形

5)所有的叶子结点都在同一层次上，并且不带信息(可以看作是查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)；118111127135139199243783475364abcdefgh上图中,结点形式为:n指针关键字指针关键字.....p0k1p1k2

每一个结点(除了根结点和叶子),有Upper(4/2)到4个儿子，所以可以有1，2或3个关键字，根结点允许有1至3关键字，此时所有的叶子都在第四层上。例：下图所是为一棵4阶的B-树，深度为4B-树的查找过程：

B-树的查找是一个顺指针查找结点和在结点的关键字中顺序查找交叉进行的过程。结点类型说明如下：

typedefstructmbnode{intkeynum;structmbnode*parent;KeyTypekeys[m-1];structmbnode*ptrs[m];}*mblink;typedefstruct{mblink*p;inti;inttag;}Result;查找算法如下：Resultmbsearch(mblinkt,KeyTypek){p=t;q=NULL;key[0]=-max;//key[0..m]为关键字辅助数组

while(p!=NULL){n=p->keynum;key[n+1]=max;for(j=0;j<n;j++)key[j]=p->keys[j];for(j=0;j<=n;j++)a[j]=p->ptrs[j];//a[0..m]为指针型辅助数组

i=sqSearch(key,k);//在数组key中进行顺序查找直到key[i]≤k≤key[i+1]}if(key[i]==k){Rst->p=p;Rst->i=i;Rst->tag=1;return(Rst);}//查找成功

q=p;p=a[i];//继续向下查找

}Rst->p=q;Rst->i=i;Rst->tag=0;return(Rst);//查找失败,其中q,i指示等于k的关键字在B-树中应插入的位置}在B-树上进行查找所需时间的分析

从上述过程可知，在B--树上进行查找所需时间取决于两个因素：⑴等于给定值的关键字所在的层次数;⑵结点中关键字的数目。(较大时可用折半查找)

显然，节点所在的最大层次数即为树的深度。那么，含有N个关键字的m阶B--树的最大深度是多少？根据B--树的定义第一层至少有1个结点第二层至少有2个结点第三层至少有2*m/2个结点

(因为除根之外的每个非终端结点至少有m/2个)

第四层至少有2*m/22个结点……最末层L+1层有2*m/2L-1个结点

(因为最末层为叶子,m阶B树中有N个关键字,则叶子结点为N+1个,由此有N+1≥2*(m/2)L-1

N+12≥(m/2)L-1两边取对数log()N+12≥(L-1)log(m/2)L-1≤log()N+12log(m/2)换底=log()m/2N+12logm/22log()m/2m/2logm/22=log()m/2N+121≤log()m/2N+12∴L≤log()m/2N+12+1

这就是说，在含有N个关键字的B--树上，进行查找时，从根j结点到关键字所在结点的路径上涉及的结点数不超过log()m/2N+12+1个例如:当N=1999998且m=199时,L最多为3。这就是说，在最坏情况下，一次查找至多需要存取3个结点。B-树的插入：

B-树的生成也是从空树起，逐个插入关键字。但由于B-树结点中的关键字个数必须大于Upper(m/2)-1，因此，每次插入一个关键字，不是在树中添加一个叶子结点，而是首先在最底层的某个非终端结点中添加一个关键字，若该结点的关键字不超过m-1，则插入完成，否则要产生结点“分裂”。例:在如下的3阶B-树上分别插入30,26,85和7454550501001002424373753903126170abcdefgh(图一)插入3045455050100100242453903126170abcdefgh(图二)3037插入2645455050100100242453903126170abdefg(图三)263037c将26插入d后，由于d中的关键字数目超过2，此时将d分裂为两个结点,关键字26及其前后两个指针留在d中，而37及其前后两个指针存储到新产生的结点d‘中，同时将30和指示结点d’的指针插入到双亲节点b中。由于30插入b后没超过2,则插入完成。h454550501001002653903126170abcdefgh(图四)243037d’插入8545455050100100265390312617085abcdefgh(图五)243037d’85插入g后,需分裂成两个结点g,g‘,70插入到e中,由于e中关键字>2个,所以,e又分裂为e,e‘，70插入a中。g,e分裂后的图分别见图六、图七：45505010010026537090312abcdefgh(图六)243037d’61g’855050100100264570312abcde’fgh(图七)243037d’61g’855390e插入750501001002645703712abcde’fgh(图八)243037d’61g’855390e5050100100264570abcde’fgh(图九)7243037d’61g’855390e312c’505010010026244570abcde’fgh(图十)37d’61g’855390e312c’730505010010026abcde’fgh(图十一)37d’61g’855390e312c’730b’b’247045a’m

一般情况，结点可如下实现“分裂”。假设p节点中已有m-1个关键字，但插入一个关键字之后，结点中含有信息为：此时,可将P节点分裂为P和P‘两个节点:PPP'

即把关键字K插入到它的父亲结点中，因此在父亲结点中指针P和P'是按如下顺序被放置的。

...,P,K,P'...m/2m/2m，A0，K1，A1，K2，A2，...，KmAm，A0，K1，A1，…，K，Am/2-1m/2–1m/2-1m-m/2,A,K,A,...Km,Amm/2m/2+1m/2+1在B-树上插入关键字的算法：voidmbinsert(mblinkt,KeyTypek){x=k;ap=NULL;{(x,ap)为插入的一对关键字和指针}Rst=mbsearch(t,k);q=Rst->p;i=Rst->i;tag=Rst->tag;//应插入的位置是q结点中第i+1个关键字

n=q->keynum;while(q!=NULL){insert(key,i+1,x);//x插入在数组key中第i+1个分量之前

insert(a,i+1,ap);//ap插入在数组a中第i+2个分量之前

n=n+1;if(n<=m-1){store(n,key,a,q);return;}//将插入后的信息存入q结点

s=m/2;//取中间位置

move(key,key1,s+1);//将数组key中从s+1至m的分量传送到key1数组中

move(a,a1,s);//将数组a中从s至m的分量传送到a1数组中q1=newmbnode;store(s-1,key,a,q);store(n-s,key1,a1,q1);x=key[s];ap=q1;//组成一对新的插入信息

if(q->parent!=NULL){q=q->parent;fetch(q,n,key,a);//取出q结点的全部信息

i=seqsrch(key,x);}}//继续插入至双亲结点上

t=newmbnode;store(1,q,x,ap,t);//生成新的根结点信息};B-树的删除：首先要找到关键字所在的结点，并从中删除之，若该结点为最下层非终端结点，其中关键字的数目大于等于Upper(m/2)，则删除完成，否则要进行“合并”结点的操作。假若所删关键字为非终端结点中的Ki，则以指针Ai所指子树中的最小关键字Y代替Ki，然后在相应的最下层非终端结点中删去Y。由此可见，不管删除什么位置的结点中的关键字都要变为删除最下层非终端结点中的关键字。下面分三种情况讨论：1)被删关键字所在最下层非终端结点中的关键字数目不小于Upper(m/2),则只需从该结点中删去关键字Ki和相应指针Pi，树的其它部分不变。454550501001002424373753903126170abcdefgh删去12454550501001002424373753906170abcdefgh32)被删关键字所在最下层非终端结点中的关键字数目等于Upper(m/2)-1,而与该结点相邻的右或左兄弟结点的关键字数目>Upper(m/2)-1,则需将其兄弟结点中的最小右兄弟或最大左兄弟的关键字上移至双亲结点中,而将双亲结点中小于或大于该上移关键字的关键字下移至被删关键字所在结点中。删去5045455053100100242437376190bdefgh70454550501001002424373753906170abcdefgh3c33)被删关键字所在最下层非终端结点和其相邻的兄弟结点中的关键字数目都等于Upper(m/2)-1时,假设该结点有右兄弟,且其右兄弟结点地址由双亲结点指针Aj所指，则在删去关键字之后,它所在结点中剩余的关键字和指针加上双亲结点中的关键字Kj,一起合并到Aj所指兄弟结点中(若无右兄弟,则合并至左兄弟结点中)。删去5345455053100100242437376190bdefgh70c3451001002424373790bdeghc361701001004590egh6170324删去37B+树m阶的B+树的定义如下：1)每个非叶结点至可以至多可以有m个儿子；2)每个非叶结点(根结点除外)必须有m+1/2个儿子；3)根结点至少有两个儿子；4)有k个儿子的非叶结点有k个关键字；5)所有的叶子结点中包含了全部关键字的信息及指向相应记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。B+树和B-树的主要区别：1)有n棵子树的结点中含有n个关键字(B树中含有n-1个关键字)；2)所有的叶子结点中包含了全部关键字的信息及指向相应记录的指针,且叶子结点本身依关键字的大小从小到大顺序链接；3)所有的非终端结点可以看成是索引部分,结点中仅含有其子树中最大(或最小)的关键字。下图为一棵m=2阶B+-树的例子70954070952040517091951020354044516570859193955101120303540444751616570808591929395

通常在B+树上有两个头指针：一个指向根结点；另一个指向关键字最小的叶子结点。因此，可以对B+-树进行两种查找运算，一种是从最小关键字起顺序查找，另一种是从根结点开始随机查找。

在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。只是在查找时，若非终端结点上的关键字等于给定值，并不终止，而是沿着左边的指针继续向下直到叶子结点。因此，在B+-树上，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。

纵观以上两节讨论的表示查找表的各种结构，有一个共同点：记录在表中的位置和它的关键字之间不存在一个确定的关系，因此，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。因此，用这类方法表示的查找表，其平均查找长度都不为零，不同表示方法的差别仅在于：和给定值进行比较的关键字的顺序不同。对于频繁使用的查找表，希望ASL=0。即不需要从“比较”的结果来确定查找成功，只有一个办法：预先知道所查关键字在表中的位置，也就是说，记录在表中位置和其关键字之间存在一种确定的关系。★8.4Hash法什么是Hash表？例如：为每年招收的1000名新生建立一张查找表，其关键字为xx000--xx999(前两位为年份)。则可以下标为000--999的顺序表表示之。由于关键字和记录在表中的序号相同，则不需要经过比较即可确定待查关键字。

但是，对于动态查找表而言，1)表长不确定；2)在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。因此，一般情况，需建立一个函数关系，以f(key)作为关键字为key的记录在表中的位置，通常称这个函数f(key)为哈希函数。(注意：这个函数并不一定是数学函数)简单地说，哈希表是基于哈希函数建立的一种查找表。例如：对于如下9个关键字{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}138961114122设

从这个例子可见，哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可;由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：key1<>key2，而f(key1)=f(key2),并且，改进哈希函数只能减少冲突，而不能避免冲突。

因此，在设计哈希函数时，一方面要考虑选择一个“好”的哈希函数;另一方面要选择一种处理冲突的方法。所谓“好”的哈希函数，指的是，对于集合中的任意一个关键字，经哈希函数“映象”到地址集合中任何一个地址的概率是相同的。称这类哈希函数为“均匀的”哈希函数。根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这种表被称为哈希表。Hash法的关键在于哈希表的构造和冲突的处理哈希函数的构造方法对数字的关键字可有下列哈希函数的构造方法，若是非数字关键字，则需先对其进行数字化处理。

例有一个从1到100岁的人口数字统计表,用年龄做关键字，它采用的hash函数是第一种H(K)=K,即j=k。地址010203…25262728…100年龄123…25262728…100人数300020005000…1020207070017200…101.直接定址法

哈希函数为关键字的线性函数

H(key)=key或者H(key)=a*key+b

仅限于：地址集合的大小=关键字集合的大小2.数字分析法

例有七个8位十进制的关键字（有七个关键字，每个关键字都具有八位十进制数），将其散列在地址为10-90的表中。

①②③④⑤⑥⑦⑧地址

k1：5424224242k2：5428136783k3：5422281728k4：5423896739k5：5425415751k6：5426853765k7：5421935513仅限于：能预先估计出全体关键字的每一位上各种数字出现的频度。假设关键字集合中的每个关键字都是由s位数字组成(k1,k2,…,kn)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。3.平方取中法若关键字的每一位都有某些数字重复出现频度很高的现象，则先求关键字的平方值，以通过“平方”扩大差别,同时平方值的中间几位受到整个关键字中各位的影响。4.折迭法

若关键字的位数特别多，则可将其分割成几部分，然后取它们的叠加和为哈希地址。相加的方法有移位法和折叠法。折叠法：把一关键字看承一张纸条，从一端向另一端沿边界逐层折叠，再把相应的位数加在一起。移位法：将各部分的最后一位对齐，然后相加。假定关键字:K=d1d2d3…drdr+1…d2rd2r+1…d3r允许有的存储地址有r位。移位法：d1d2…drdr+1dr+2…d2r+d2r+1d2r+2…d3r高进位不要了得到r位的存储地址折叠法:d3rd3r-1…d2r+1dr+1dr+2…d2r+drdr-1…d1d1'd2'…dr'高进位不要了得到r位的存储地址例如：K=32834872，允许存储地址为三位十进制数。位移法：328折叠法：27348348+72+8237481198H(K)=748H(K)=1985.除留余数法

实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。例有一组关键字从000001-859999，指定的存储单元地址为1000000-1005999,即m=6000。选p=5999k=172148r=(172148)mod5999=4176(mod5999)f=1000000+r=1004176

在这里选择p是关键步骤，若P为偶数，则凡是奇数的关键字，

都转换为奇数地址，则凡是偶数的关键字地都转换为偶数地址，显然会出现冲突。一般情况：(1)P尽量接近m;(2)p为质数。设给出关键字k，存储单元数为m,则可选一数p(p<=m)去除k得到余数r(以p为模)，再用一线性函数f将r转换为散列地址j,即r=(k)modp,j=f(r)§8.3.2处理冲突的方法

处理冲突的方法开放定址法链地址法线性探测再散列二次探测再散列伪随机探测再散列探测：检查关键字是否与hash向量元素相匹配。一、开放定址法假设哈希空间为T(0:m-1),哈希函数为j=H(key)。为求得下一个哈希地址，可取ji=(j+di)MODm，i=1,2,3,...,s(s≥1),其中m为哈希表的表长di为增量序列。1.当取di=1,2,3,....,s时称为线性探测再散列

例如：有一个关键字序列19,70，33，已存入长度为16的哈希表中。取哈希函数为除留余数法:j=kMOD13；01…45678…15……70193318现在要把关键字为18的记录填入表中：j=18MOD13=5冲突1次j3=(5+3)MOD16=8不冲突Hash地址是否冲突冲突次数j1=(5+1)MOD16=6冲突2次j2=(5+2)MOD16=7冲突3次j=19MOD13=6；j=70MOD13=5；j=33MOD13=7

2.当取di=12,-12,22,-22,…,n2,-n2

时称为:

二次探测再散列仍以上例为例，70，19，33已填入哈希表中，再填入关键字为18的记录:01…45678…15……70193318j=18MOD13=5冲突1次Hash地址是否冲突冲突次数j2=(5-1)MOD1