数据结构-用C语言描述（第二版）第8章检索-2

第八章

检索检索的基本概念线性表的检索树表的检索B树散列检索技术第8章

检索第八章

检索检索的基本概念1、检索定义关键字关键字（Key）是数据元素（或记录）中某个数据项的值，用它可以标识（或识别）一个数据元素（或记录）。在一个记录中，每个数据项都可作为该记录的关键字。主关键字是指在一个记录众多的关键字中能唯一地标识一个数据元素（或记录）的关键字，其它的关键字称为从关键字，也叫辅助关键字。检索表检索表是由同一类型的数据元素（或记录）组成的集合，是检索操作所依赖的数据结构。检索定义检索，又叫查找，是根据给定的某个值，在一个检索表中确定一个其关键字等于给定值的记录或数据元素的操作运算。若检索表中存在这样的一条记录，则称检索是成功；若表中不存在这样的记录，则称检索是不成功的，是失败的，此时检索的结果在静态环境下可给出不存在此记录的提示信息；在动态环境下，可插入此关键字等于给定值的记录。第八章

检索2、检索方法依据数据的存储方式的不同，我们将检索分为线性表检索、树表检索和散列表检索等。3、平均检索长度将“为检索到具有给定关键字值的数据元素或记录所需要关键字的比较次数的平均值”作为衡量检索算法好坏的依据，即通过平均检索长度来衡量。具体地说，即指为确定欲检索的记录在表中的位置，需与给定值进行比较的关键字个数的期望值，称为检索算法在检索成功时的平均检索长度（Average

Search

Length）。其中，pi为检索第i个记录的概率，且 。若不特别说明，均认为每个记录的检索概率相等（即为等概率情形），从而有p1=p2=…=pn=1/n，ci为检索到第i个记录需要和给定关键值比较的关键字个数。一般情形下，ci依赖于所采用的检索方法。第八章

检索线性表的检索按照检索方法的不同可分为顺序检索、折半检索和分块检索。8.2.1顺序检索1、基本思想基本思想是：从表的第n个记录开始，用给定的值与表中各个记录的关键字逐个地进行比较，如果检索到某一个记录的关键字与给定值相等，则检索成功；若整个表中的记录均比较过，仍未检索到关键字等于给定值的记录，则检索失败。8.2线性表的检索第八章

检索2、类型定义与算法实现typedef

struct{keytype

key;

/*关键字类型*/elemtype

other;/*其他的域*/}

sqlist

;sqlist

R[n+1];/*顺序表*/顺序检索算法：int

seqsrch

(sqlist

R[

]

，keytype

k){

int

i

;R[0].key=k;/*将R[0]作为监视哨*/i=n;/*从第n个记录起向前扫描*/while(R[i].key!=k)i--

;if

(i=

=0)

return(0)

;else return

i

;}

/*seqsrch

*/第八章

检索3、顺序检索性能分析在等概率情况下，顺序检索的平均检索长度为：顺序检索成功时的平均比较次数约等于表长的一半。若所检索的给定值k不在表中，则需进行n+1次比较才可确定检索失败。其算法简单，且适用面广，对表的存储结构、记录是否按关键字有序等方面不作要求。第八章

检索8.2.2折半检索1、基本思想折半检索又称二分检索，其基本思想是：先将待检索的给定值和检索表的中间位置上的记录的关键字值进行比较，若相等，则检索成功，否则，若给定值比该中间位置上记录的关键字值大，则只要在右半部分中继续进行折半检索，否则，只要在左半部分中继续进行折半检索。这样，经过一次关键字比较就缩小一半的检索区间，…，如此进行下去，直到检索到关键字值为给定值的记录，或者未检索到，即检索失败。需注意的是，作为折半检索对象的表必须是顺序存储方式的有序表。第八章

检索2、折半检索过程示例已知一个含11个记录的有序表，其关键字序列为（

08，10，12，19，25，31，39，42，47，52，57

）（1）检索k=12：此时mid=5，由于k=12<R[mid-1].key，只要在其左子表R[0]…R[4]中继续检索中继续进行折半检索。此时mid=2，由于k=12=R[mid].key，说明检索成功。第八章

检索此时mid=5，由于k=42>R[mid].key，所以只要在其右子表中继续进行折半检索，即在R[6]…R[10]中继续检索。此时mid=8，由于k=52>R[mid].key，可缩小检索区间，即缩小

为R[9]…R[10]。此时mid=9,且有k=52=R[mid].key，则检索成功。（2）检索k=52的记录过程：第八章

检索此时，k=87>R[mid].key，则下一步为：此时，k＝87>R[mid].key，则下一步为：此时，mid=9，k>R[mid].key，则又缩小区间为R[10]…R[10]，此时

mid=10，由于此时k>R[mid].key，又缩小区间，但此时low=10+1>high，区间的下界大于上界，不能构成区间，说明检索失败。（3）检索k=87的记录第八章

检索3、折半检索算法int

binsrch（

sqlist

R[

]

，

keytype

k）{int

low

,

high

,mid

；low

=

0；high

=

n-1；while

(

low

<=

high

){

mid

=(low+high)/2

;if

(k

=

=R[mid].key)

return

(mid)

;elseif(k<R[mid].key)high=mid-1;/*在左区间上检索*/else

low=mid+1;/*在右区间上检索*/}return

(0)

;}

/*

binsrch

*/第八章

检索4、折半检索判定树折半检索过程可以借助二叉树进行描述。把当前检索区间的中间位置上的记录或结点作为二叉树的根，左半区间和右半区间中的记录分别作为根的左子树和右子树，由此就可得到一棵二叉树，称为折半检索判定树。如图8.1所示为具有11个记录的有序表的折半检索判定树表示。第八章

检索5、折半检索的平均检索长度折半检索的过程恰好是在判定树中走了一条从二叉树树根到被检索结点的路径，经历比较的关键字个数恰为该结点在树中的层数。折半检索成功时所进行的关键字比较的次数至多为

次。在等概率情况下（即表中每个记录检索的概率相等，pi=1/n），检索成功时的折半检索的平均检索长度为：当n很大时，如n>100时，则可得近似公式：ASL≈log2(n+1)-1折半检索的效率比顺序检索要高得多，但它只能适用于有序表，它一般只适用于那些有序表，且一旦建立后很少变动而又需要经常检索的线性表。第八章

检索ASL=(1+2×2+3×4+4×8)≈3.3例如，一棵具有15个结点的判定树和其检索成功时的平均检索长度如图8.2所示。第八章

检索8.2.3分块检索1、定义分块检索又称索引顺序检索，属于索引检索，是一种介于顺序检索与折半检索之间的检索方法。分块检索要求将表中数据元素分成很多子表（块）后，数据元素的关键字在块与块之间是有序，而在块内不一定有序。2、分块检索的基本思想首先依据待检索的给定值在索引表中进行检索，由于索引表是一个有序表，所以可采用折半检索（也可采用顺序检索）以确定待检索记录属于哪一块；然后在已确定的那一块内进行顺序检索，如图8.3。图8.3表及索引表第八章

检索3、分块检索算法（1）当顺序检索索引表时：#define

M

99typedef

struct{

keytype

key

;int

stadr

;int

len

;}indexlist;/*索引表的类型定义*/indexlist

ID[M];/*ID为具有indexlist类型的R上的一个索引表*/第八章

检索int

Blocksrch(

R，ID，m，k

)sqlist

R[

]

;indexlist

ID[];/*索引表ID

*/keytype

k;int

m

;{

int

i,

ji

=

0

;while((i<=m-1)&&(k>ID[i].key))/*顺序检索索引表*/i++;if(i>m-1)retutn(0)/*检索失败*/else{j=R[i].stadr；/*待检索块的第一个记录的下标*/while((j<ID[i].stadr+ID[i].len)&&(k!=R[j].key))j++;/*第i块中顺序检索给定值为K的记录元素*/if(j==ID[i].stadr+ID[i].len)retutn(0)/*块中检索失败*/elsereturn(j);/*检索成功*/}}

/*

Blocksrch

*/第八章

检索（2）当折半检索索引表时：indexlist

ID[M]; /*ID为具有indexlist类型的R上的一个索引表*/int

Blocksrch(sqlist

R[]，indexlist

ID[]，int

m，keytype

k){

int

i，j，low1，low2，mid，high1，high2；low1=0;high1=m-1;/*置折半检索区间的下、上界的初值*/while(low1<=high1)/*在索引表中检索*/{mid=(low1+high1)/2;/*求当前区间的中间位置*/if(k<=ID[mid].key)

high1=mid-1;/*在左区间上检索*/elselow1=mid+1;/*在右区间上检索*/}/*检索结束，low1为块号*/if(low1<m){low2=ID[low1].stadr;/*块起始地址*/if(low1==m-1)high2=n-1;/*块末地址*/第八章

检索elsehigh2=ID[low1+1].stadr-1;for

(i=low2；i<=high2；i++)/*块内顺序检索*/if(R[i].key==k)return(i);/*检索成功*/}retutn(0)/*检索失败*/}

/*

Blocksrch

*/第八章

检索其中，pbj=，pwi

=，Cbj

=

j

，Cwi

=

i；则有：4、分块检索的平均检索长度（1）若用顺序检索确定所在的块时：ASL

=

Lb

+

Lw第八章

检索（2）若用折半检索确定所在块时：ASL

=

Lb

+

Lw=

log2(+1)-1+≈log2(+1)

+分块检索平均检索长度界于折半检索和顺序检索之间。只要一个检索表的数据分布特性符合分块后有序，即可采用分块检索，且其对表的存储结构没有特殊要求。第八章

检索在线性表的检索中，折半检索方法效率最高，但要求表以顺序存储方式存储，不能用链表作存储结构，而且表中元素按关键字有序。由于在顺序存储结构中，若要频繁地进行插入和删除结点运算时，必须移动大量的元素，而这会花费相当多的时间。利用二叉搜索树作为表的数据组织方式就可以既能把链式存储结构的优点和折半检索方法的高效率结合在一起，又不要求表为有序表。8.3树表的检索第八章

检索8.3.1二叉检索树1．二叉检索树的定义与性质二叉搜索树又称二叉排序树，它或者是一棵空树，或者是一棵具有下列特性的非空二叉树：（l）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树非空，则右子树上所有结点的值均大于（若允许具有相同值的结点存在，则大于等于）根结点的值；且左、右子树本身又各是一棵二叉排序树。图8.4所示即为二棵二叉排序树。当将一组数值大小无序的数据元素构造成一棵二叉检索树后，再对此二叉检索树进行中序遍历运算，所得到的中序遍历序列是一个非递减的有序序列。第八章

检索第八章

检索2、二叉检索树的结点结构：typedef

struct

node{keytype

key;/*关键字域*/elemtype

other;/*其他数据域*/struct

node

*lchild，*rchild;}bilist/*二叉检索树的结点结构*/第八章

检索3、二叉检索树的检索（1）检索过程首先将一个无序序列的各个数据元素按照先后次序分放到一棵二叉

检索树中，即构造一棵二叉检索树，然后根据二叉检索树的定义进行检索。其检索过程为：若二叉检索树为空，则表明检索失败，返回一个特定值，否则，若给定值k等于二叉检索树根结点的关键字值，则说明检索成功，返回当前指向根结点的指针；若给定值k小于根结点的关键字值，则说明待检索数据元素只可能在左子树中，继续在根的左子树中检索；若给定值大于根结点的关键字值，则说明待检索数据元素只可能在右子树中，继续在根的右子树中检索。在一棵二叉检索树上检索一个关键字值等于给定值的结点的过程，若检索成功，实际上是走了一条从根结点到该结点的路径。如图8.5中右边的实线所示为检索k为80时的检索成功的过程，左边的虚线所示为检索k为15时检索不成功的过程。第八章

检索第八章

检索（2）检索算法bilist

*bstsrch

(t，k)bilist

*t

;

keytype

k;{

if

((t

=

=

NULL)||(t->key

=

=k))return

(t);elseif

(t->key

<

k)return(bstsrch(t->rchild，k));/*检索右子树*/elsereturn(bstsrch(t->lchild，k));/*检索左子树*/}

/*bstsrch

*/第八章

检索4、二叉检索树的构造（1）构造过程可以从一棵初始为空的二叉检索树开始，依次输入数据元素，每当读入一个数据，就生成一个结点，然后把它们依次插入到二叉树的适当位置上。插入运算可以按以下算法实现：（1）若二叉检索树为空，则将新插入结点作为根结点而插入到空树中；（2）若二叉检索树非空，首先将待插入结点的关键字值和树根结点的关键字值进行比较，若待插入结点的关键字值大

于根结点的关键字值，则将待插入结点插入到当前根结点的右子树中，否

则插入到其左子树中；若相等，则说明树中已有结点，不必插入。同样，

在左、右子树中的插入过程与在树中的插入过程相同，这样不断进行，直

到将待插入结点作为一个新的叶子结点插入到一棵二叉检索树中为止。第八章

检索（2）算法实现插入算法描述：bilist

*insert

(t，s)bilist

*t

,*s

;{bilist

*p

,

*q

;if(t==NULL)return(s);/*若为空树，*s作为根结点*/p=t;while

(

p!=

NULL){

q

=

p

;if

(s->key

=

=

p->key

)

return

(t)

;else{

if

(s->key>p->key

)

p

=

p->rchild

;else

p

=p->lchild

;}}第八章

检索if

(s->key>q->key)

q->rchild

=

s

;else

q->lchild=

s

;return

(t)

;}

/*insert*/第八章

检索二叉检索树构造算法描述：bilist

*bstcreat(){

bilist

*t，*s

；keytype

k

；int

i，n

;elemtype

data;t=NULL;/*设二叉检索树的初态为空树*/scantf(“%d”，&n);for

(i

=l;

i<=n;

i++){

scanf

(“

%d”，&key

);s

=

(bilist*

)

malloc(sizeof(bilist));s->lchild

=

NULL

;s->

rchild

=

NULL;s->

key

=

key

;s->other=data;/*此处假设其它域data已读入*/t=insert(t，s);}}

/*bstcreat*/第八章

检索5.二叉检索树的结点删除（1）基本思想：①若要删除的是叶子结点删除一个叶子结点（终端结点）只要将其双亲结点与它之间相链接的指针置空即可。例如，要在图8.6中删除结点100时，只要将结点100与其双亲相链接的指针去掉即可，删除后的二叉检索树如图8.7所示。②若要删除的结点只有左子树或只有右子树即单支结点，删除该结点时，要将其唯一的与后继结点相链接的指针链接它所在的链接位置上，即将被删除结点*p的左子树或右子树直接成为双亲*f的左子树或右子树。如图8.6中，要删除45结点，只要将其的右孩子指针直接赋给其双亲40的右孩子指针即可，同理，可以删除90结点。删除后的二叉检索树如图8.8所示。第八章

检索第八章

检索第八章

检索③若要删除的结点左、右子树均不空常用的方法：先将被删除结点的中序前趋结点的值域赋给该结点的值域，然后再删除它的中序前趋结点，将中序前趋结点的左孩子指针链接到中序前趋结点所在的链接位置即可。如图8.6中，要删除结点40（设为A点），首先将该结点的中序前趋结点的值30赋给A点（即以30结点顶替40结点），然后删除30结点。删除后的二叉检索树如图8.9所示。另外一种方法是将被删除结点的右子树链接到它的中序前趋结点的右孩子指针域，然后把被删结点的左子树直接链接到它的双亲的左孩子指针域上。如图8.6中，要删除结点40，首先可将该结点的右子树下接到其中序前趋结点30的右孩子指针域上，然后将该结点的左子树上接到其双亲结点50上，作为它的左子树，此时就实现了删除操作，如图8.10所示。但这种删除方法往往会增加二叉树的深度，不经常采用。其它删除方法：用待删除结点的中序后继结点替换待删除结点，或者把待删除结点的左子树链接到它的中序后继结点的左指针域，并把它的右子树直接链接在其双亲结点的相应链域中。第八章

检索第八章

检索（2）算法描述结点结构：typedef

struct

node{keytype

key;/*关键字值key域*/elemtype

other；/*其它域*/struct

node

*rchild，*lchild，*parent；}bstsrchtree;第八章

检索删除算法：bstsrchtree

*delete(bstsrchtree

*t，keytype

k)；{

bstsrchtree

*p，*q，*r；p=t；while

((p!=NULL

)

&&

(k!=p->key))if

(

k<p->key)

p=

p->lchild；else

p=p->rchild；if

(p

=

=NULL)

return(t)；if((p->lchild=

=NULL)

¦¦

(

p->rchild=

=NULL))q=p；else{

q=

p->rchild；while

(q->lchild!=NULL)q=q->lchild；}if

(q->lchild!=NULL)

r=q->lchild；else

r=q->rchild；if

(r!=NULL)

r->parent=q->parent；if

(q->parent=

=NULL)

t=r；第八章

检索elseif

(q=

=q->parent->lchild)q->parent->lchild

=r；elseq->parent->rchild

=r；if

(p!=q){

p->key=

q->key;p->other=q->other;free(q);}return

(t)；}

/*delete*/第八章

检索6、二叉检索树的检索性能分析在二叉检索树上检索关键字值等于给定值的结点的过程，正好是走了一条从根结点到该结点的路径，而且和给定值进行比较的次数等于结点所在的层次（或路径长度加1）。对于同样的结点个数和相同值的关键字，其在构造二叉检索树所得到的二叉检索树的形态也不相同，因而其平均检索长度相差很大，其检索效率取决于树的形态。在最好的情况下，平均检索长度为

；在最差的情况下，平均检索长度为n+1；在一般情况下，平均检索长度为 。一般情况下，我们希望所构造出的二叉检索树尽可能地形态匀称，即对二叉检索树的平衡化处理成为平衡二叉检索树，这样就可以有较高的检索速度。第八章

检索例如，图8.11给出了结点值都相同的两棵二叉检索树，前者深度为3，而后者深度为7。前者的平均检索长度为ASL(a)=(1+2×2+3×4)/7=17/7，后者的平均检索长度为ASL(b)=(1+2+3+4+5+6+7)/7=28/7=4。30404550556070(a)

深度为3的二叉检索树

(b)

深度为7的二叉检索树图8.11

结点值都相同的两棵二叉检索树示例30404570556050第八章

检索8.3.2平衡的二叉检索树1、平衡二叉树定义一般来说，可将形态匀称的二叉检索树称为平衡二叉树，又称AVL树。平衡二叉树或者是一棵空树，或者是具有下列性质的二叉树：它的任何结点的左子树和右子树的高度之差的绝对值不超过1。通常将二叉树上任一个结点的左子树和右子树的高度之差定义为该结点的平衡因子。因此，平衡二叉树上所有结点的平衡因子只可能是-1，0和1。只要有一个结点的平衡因子的绝对值大于1，该二叉树就不是平衡二叉树。如图8.12所示，(a)图为一棵平衡二叉树，(b)图为不平衡二叉树。第八章

检索2、二叉检索树的调整Adelson-Velskii和Landis提出了一个动态地保持二叉检索树平衡的方法。其基本思想是：在构造二叉检索树的过程中，每当插入一个新结点

时，首先检查是否由于新结点的插入而破坏了二叉树的平衡性。若是，

则找出其中最小的不平衡树，在保持检索树特性的前提下，通过调整最

小不平衡子树中结点之间的关系，使它满足平衡树的特性，达到新的平

衡。所谓最小不平衡子树即指离插入结点最近，且以平衡因子绝对值超

过1的结点为根的子树。第八章

检索设在插入结点的过程中，使二叉树失去平衡的最小不平衡子树的根结点为a点，则可依据插入结点位置的不同情形一般有以下四种：（1）LL型平衡旋转在结点a的左孩子的左子树上插入结点，使一棵二叉树上结点a的平衡因子由1增至2而失去平衡，此时须进行一次顺时针旋转操作。如图8.13所示。第八章

检索（2）RR型平衡旋转由于在a的右孩子的右子树上插入新结点，使a的平衡因子由-1增到-2而失去平衡。此时应以b为轴心作逆时针旋转，使结点a作为结点b的左孩子，如图8.14所示。第八章

检索（3）LR型平衡旋转在结点a的左孩子的右子树上插入新结点c，使a的平衡因子由1增到2而失去平衡。此时需进行两次旋转。首先以新结点c为轴心作逆时针旋转，使得结点a的左孩子变为新结点c的左孩子，然后再以新结点c为轴心作顺时针旋转，使得结点a变为新结点c的右孩子。如图8.15所示。第八章

检索（4）RL型平衡旋转由于在a的右孩子的左子树中插入新结点c，使a的平衡因子由-1增到-2而失去平衡。此时首先应以新结点c为轴心作顺时针旋转，使得结点a右孩子变为新结点c的右孩子，然后再以新结点c为轴心作逆时针旋转，使得结点a变为新结点c的左孩子，如图8.16所示。第八章

检索例如，对关键字序列{9，3，6，8，7，10}建立一棵平衡二叉检索树，其过程如图8.17所示。结点旁的数字是该结点的平衡因子。第八章

检索第八章

检索索引文件的树型索引表结构通常采用B树结构。B树又包含B-树和B+树两种，它们都是一种适用于外检索的树型结构，是一种平衡的多路检索树。B-树1、B-树的定义一棵m阶的B-树是一种平衡的多路检索树，它或者是一棵空树，或者是一棵满足下列特性的m叉树：树中每个结点至多有m棵子树；除非根结点为叶子结点，否则它至少有两棵子树；除根结点之外的所有非终端结点至少有 棵子树；所有的叶子结点均保持在同一层上，且不包含任何信息；8.4

B树第八章

检索（5）所有的非终端结点中包含有下列信息：（n，A0，K1，A1，K2，A2，…，Kn，An）其中，K1，K2，…，Kn为n个按从小到大顺序排列的关键字，A0，A1，A2，…An为n+1个指向子树根结点的指针，用于指向该结点的n+1个子树或孩子，其中A0所指向孩子中的所有关键字均小于K1，…，An所指向孩子中的所有关键字均大于Kn，Ai（0≤i≤n）所指向孩子中的所有关键字均小于Ki+1，但大于Ki。例如，图8.18为一棵由11个关键字生成的3阶B-树的示意图。第八章

检索第八章

检索2、B-树的检索在B-树上进行检索的过程类似于二叉检索树，都是走了一条从树根结点到待检索关键字所在结点的检索路径，不过通常需要经过同多个关键字比较后才能确定一个结点。需要先在B-树中检索结点，而后在结点中检索关键字，从而判断是否检索成功或失败。检索B-树所需比较的结点要比在二叉检索树上检索所需比较的结点数要少得多。例如，对于图8.18，若要检索关键字值等于70的结点，其具体过程为：由于树不空，首先从根结点开始，找到结点a，由于a中只有一个关键字，且给定值70>50，所以由指针A1可找到结点c，该结点有两个关键字（55和80），由于55<70<80，若待检索关键字70存在，则必在c结点中指针A1所指的子树中，然后由指针A1找到结点g，在结点g中顺序检索，可检索到关键字70，此时检索成功。第八章

检索3、B-树结点的插入在B-树上插入一个数据元素首先要检索出关键字的正确插入位置，然后再进行插入。在B-树中插入新元素不是添加新的叶子结点，而是需要先判断该结点是否已有m-1个键字，若不是m-1个关键字，则按关键字（设为k）的大小有序地插入到适当的位置，否则，由于结点的关键字个数为m，超过了结点所规定的范围，需要进行结点的“分裂”。例如，对一组关键字（25，80，40，45，56，75，85，20），从3阶的空的B-树开始，依次插入关键字。其具体过程如图8.19（a）到（k）图。第八章

检索第八章

检索4、B-树结点的删除要在B-树上删除一个关键字，则首先应检索到这个关键字所在的结点，然后依据关键字所在结点的情况来进行删除。如果被删除的关键字所在结点中的关键字数目不超过

，且该结点为叶子结点，则直接将该关键字删除即可；如果被删除关键字在非叶子结点中，则首先应将被删除结点的关键字同它的中序前趋的关键字（即它的左边指针所指孩子的最右下叶子结点中的最大关键字）或中序后继的关键字（即它的右边指针所指孩子结点的最左下叶子结点中的最小关键字）对调，然后再从对应的叶子结点中删除该关键字。然后再依据以下三种情形进行相应的处理。（a）若删除后该结点的关键字个数n仍大于等于-1，则直接将其删除。第八章

检索（b）若删除后该结点的关键字数目n<弟（或右兄弟）结点中的关键字数目n>-1，而与该结点相邻的左兄-1，此时，需首先将其双亲结点中指向该结点指针的左边（或右边）一个关键字下移至被删除关键字

所在结点中，接着将它的左兄弟结点中最大（或右兄弟结点中最小）的关

键字移至其双亲结点中刚空出的位置上，然后再将而将左兄弟（或右兄弟）结点中的An指针（或A0指针）赋给该结点的A0指针域（或An指针域）。（c）若删除后该结点的关键字数目n小于兄弟结点（若存在的话）中的关键字个数均等于-1，同时它的左兄弟和右-1，此时就必须进行结点的“合并”，即将该结点中的剩余关键字和指针连同双亲结点中指向

该结点指针的左边（或右边）的一个关键字一起合并到左兄弟（或右兄弟）结点中，然后再删除该结点。例如，假定一棵5阶的B-树，如图8.20（a）所示。从该B-树中删除关键字26的过程如图b、c、d所示。第八章

检索第八章

检索8.4.2

B＋树B+树是应用于文件系统中的B-树的一种变形树，一棵m阶的B+树与相应的B-树的差异主要在于：⑴有n棵子树的结点中含有n个关键字；⑵所有叶子结点中包含了全部关键字的信息及指向相应记录的指针，且叶子结点以关键字值递增顺序链接；⑶所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大（或最小）关键字。如图8.21给出了一棵3阶B+树。第八章

检索t50

8023

5060

70

8010

23sqt28

50 58

60图8.21一棵3阶B+树示例65

7076

80第八章

检索在B+树上进行插入、删除和检索的过程与B-树基本相似，只是在检索过程中，在非终端结点上检索到关键字值等于给定值的结点后并不终止，而是继续向下直到叶子结点；无论是检索成功还是检索失败，每次检索都是走了一条从根结点到叶子结点的路径。B+树的插入仅在叶子结点上进行，当结点中的关键字个数大于m时也要分裂成两个结点，它们所含关键字的个数分别为

和

，并且其双亲结点中应同时也包含这两个结点的关键字最大值。B+树的删除也在叶子结点中进行，其在非终端结点中的值可以作为分界关键字存在；若在删除后若结点中关键个数小于

时也要进行兄弟结点的合并操作。第八章

检索8.5.1散列表技术1、基本概念散列(又称哈希、Hash)检索的基本思想主要是以记录中关键字的值k为自变量，通过某一种确定的函数h（k），计算出相应的函数值，通常把这个值解释为记录或结点的存储地址，然后将该记录存放到这个位置上，而在检索时再根据要检索的记录的关键字，利用相同的函数h（k）进行计算，获得所要检索的关键字所在记录的存储地址，直接到该地址所对应的存储单元中去读取所要检索的结点，可以不需要进行关键字的比较就可以检索到某个关键字所对应的记录。将函数h（k）称为散列函数或哈希函数，利用它可以实现记录的关键字到该记录的存储地址之间的转换，有时将h（k）的值称为散列地址或哈希地址。散列技术与顺序、索引或链接存储方式一样，也是一种存储线性表的方式，有时将以这种方式存储的线性表称为散列表或哈希表。8.5散列检索技术第八章

检索例如，一组关键字序列为（25，74，36，40，82，65，57），若选取散列（或哈希）函数h(k)=k%13，可得每个记录所对应的散列地址分别如下：h(25)=25%13=12h(36)=36%13=10

…h(74)=74%13=9h(57)=57%13=5则可得到散列（或哈希）表如下表所示：第八章

检索理想情况下，哈希函数在关键字和地址之间建立了一个一一对应关系，从而使得检索只需一次计算即可完成。由于关键字值的某种随机性，使得这种一一对应关系难以发现或构造。当不同的关键字通过同一个散

列函数计算散列地址时，就有可能出现具有相同的散列地址的情况。若

该地址单元已有记录存入，则另一个具有相同散列地址的其它记录就无

法再存放进去，从而引起“冲突”现象。通常将这种具有不同关键字而

具有相同散列地址的记录的关键字叫做“同义词”，而由同义词引起的

冲突叫做“同义词冲突”。冲突现象在实际中冲突是很难避免的，除非所选取的散列表的长度大于等于所有关键字的取值范围，但这种方式有可能会由于关键字的取值不连续而浪费大量的存储空间。在实际中如何尽量避免冲突和在冲突发生后如何解决冲突，就成为在构造散列表中的两个关键问题。第八章

检索2、散列函数构造构造散列函数的目的是使散列地址尽可能均匀地分布在散列表空间内，同时使计算尽可能地简单方便以节省计算时间。在实际应用中，可以依据关键字的结构和分布的不同，构造出与之适应的各不相同的散列函数。（1）直接定址法直接定址法是将关键字本身或关键字加上某个数值常量c作为散列地址的方法。对应的散列函数h(k)为：h(k)

=

k+c若c=0时，则取散列地址为关键字本身。该方法适用于关键字的分布基本连续的情形。若关键字分布不连续，则空单元较多，将造成存储空间的浪费。第八章

检索除留余数法除留余数法是用关键字k除以某个正整数p所得余数作为散列地址的方法。对应的散列函数h(k)为：h(k)

=k

%

p其中，p可以选择小于或等于散列表长度m的某个最大素数比较好。例如，散列表长度m=600时，可选p为599。除留余数法的计算公式简单，在许多情况下效果较好，该方法是一种常用的构造散列函数的方法。数字分析法数字分析法是对关键字中数字位进行分析，然后用其中的一些较分散的数字位作为散列地址的方法。一般它适合于那些预先知道每个关键字的情况，并对关键字中每一位的取值分布情况作了分析的情形。例如，一组关键字（395003，395010，395012，395085，395097），通过分析可知，这些关键字都由六位数字组成，前四位取值相同，后二位取值较分散且随机，故可取后两位的值作为散列地址，分别为（03，10，12，85，97）。第八章

检索（4）折叠法折叠法是先将关键字分割成位数相等的几段，然后取这几段的叠加和作为散列地址。如一个关键字为k=0568243325，若要以它构造一个散列表，则可用折叠法构造一个散列函数。假设构造的散列表地址为四位数，则可构造如下：一般折叠法有移动叠加与间界叠加两种方法，移位叠加是将分割后的每一段的最低位对齐，然后相加；而间界叠加是从另一端沿分割界来回折叠，然后对齐相加，如图8.22所示，图（a）中可选

0154为散列地址，图（b）中可选7616为散列地址。该方法适用于关键字位数较多，而所需的散列地址位数较少的情况。第八章

检索（5）平方取中法平方取中法是取关键字平方的中间几位数作为散列地址的方法。由于一个数平方后的中间几位与数的每位都有关，所以用该方法得到的散列地址同关键字的每一位都有关，使得散列地址具有较好的分散性，从而使得产生冲突的可能性较小。该方法适用于关键字中的每一位取值都不够分散或者较分散的位数小于散列地址所需要的位数的情况。由于无需事先知道关键字的全部情况，所以是一种较常用的方法。第八章

检索3、冲突处理一般而言，处理冲突的方法有两类，一为开放定址法，二为拉链法。（1）开放定址法所谓开放定址法就是散列表中的空单元向处理冲突开放。当发生冲突时，从发生冲突的那个单元起，使用某种方法在散列表中形成一个探查序列，沿着此序列逐个单元进行检索，一直检索到某一个空闲的存储单元为止，把发生冲突的待插入记录放入该空闲单元中。如何形成一个合适的探查序列是关键，一般有：线性探查法、平方探查法和随机探查法等。（a）线性探查法线性探查法的基本作法是：将散列表看作是一个环形表，且假设散列表的长度为m，关键字个数为n，若发生冲突的单元地址为d，由于探查序列为线性探查序列，则依次探查下一个单元，即d+1，d+2，…，m-1，0，1，2…d-1，直到检索到一个空闲单元为止。第八章

检索开放定址法的探查序列可以用公式表示为：di

=(k+i)%m 其中，i=1,2,…s;(1≤s≤m-1)，d=h(k)例如，一组关键字为（8，15，16，22，30，32），散列表长度为10，且h(k)=k%7，开放定址法解决冲突，则构造的散列表如图8.23所示。第八章

检索利用线性探查法处理冲突容易造成堆积（又称“聚集”）现象，即散列地址不同的记录争夺同一个的后继散列地址的现象，也就所谓的“堆积”现象，它会使得不是同义词的记录处在同一个探查序列中，增加了探查序列的长度，使得检索下一个空间单元的路径长度大大增加。克服这类堆积现象的发生可利用平方探查法或另外的一些如双散列函数探查法。（b）平方探查法平方探查法也叫二次探查法。当发生冲突时，则依次探查单元d+i，其中i取12，-12，22，-22…等，即发生冲突时，求下一个开放地址的公式为：d2i-1

=

(d

+

i2)

%

md2i=

(d

-

i2)

%

m

(1≤i≤(m-1)/2)利用平方探查法可以减少堆积现象的发生，但这种方法不能探查到散列表上的所有单元，这是它的缺点。第八章

检索（2）链地址法链地址法就是将发生冲突的同义词用动态链式存储结构链接起来的一种解决冲突的方法。此时，散列表中的“空”单元不向冲突开放，而是将发生冲突的关键字同义词链接在同一个链表中。例如，假定一组关键字(36，45，85，25，74，86，64，17，27，31，70，12)，假定采用的散列函数为h（k）=k%13，而且发生冲突时，采用动态链接法处理，则可得到散列表如图8.24所示。利用链地址法处理冲突，要比开放定址法多占用一些存储单元，但它不会产生堆积现象，而且平均检索长度较短。另外，链地址法中各单链表的记录结点空间可以动态申请，更适合于构造表前无法确定表长的情况，便于表长经常变化的情况。第八