数据结构简明教程（第3版）课件 第8章查找(下)

第8章查找8.1

查找的概念8.2静态查找表8.3动态查找表8.4哈希表查找第8章查找1/61B树中所有结点的孩子结点最大值称为B树的阶，通常用m表示，从查找效率考虑，要求m≥3。一棵m阶B树或者是一棵空树，或者是满足下列要求的m叉树：8.3.3B树8.3.3

B树树中每个结点至多有m个孩子结点（即至多有m-1个关键字）。若根结点不是叶子结点，则至少有两棵子树。除根结点外，所有内部结点至少有

m/2

棵子树。1.B树的定义2/61所有的内部结点中包含下列信息数据：nP0K1P1K2P2…KnPnKi（i=1，…，n）为关键字，且Ki<Ki+1（i=1，…，n-1）。Pi（i=0，…，n）为指向子树根结点的指针，且指针Pi-1所指子树中所有结点的关键字均小于Ki（i=1，…，n），Pn所指子树中所有结点的关键字均大于Kn。n为该结点中关键字个数，并且满足

m/2

-1≤n≤m-1（设MIN=

m/2

-1，MAX=m-1）。树的所有外部结点都出现在同一层次上，并且不带信息（实际上这些结点不存在，指向这些结点的指针为空）。8.3.3

B树3/61根结点高度为4叶子结点层外部结点层内部结点104268121618202428142226abdefghic一棵4阶B树m=4内部结点关键字最多个数MAX=m-1=3内部结点关键字最少个数MIN=

m/2-1=18.3.3

B树4/612.B树的查找在B树中查找给定关键字的方法类似于二叉排序树上的查找，不同的是在每个结点上确定向下查找的路径不一定是二路（即二叉）的，而是n+1路的。因为结点内的关键字序列是有序的数量key[1..n]，故既可以用顺序查找关键字为k的方法查找，也可以用折半查找。8.3.3

B树5/61将k与根结点比较开始：若k=K[i]，则查找成功。若k<K[1]，则沿着指针P[0]所指的子树继续查找。若K[i]<k<K[i+1]，则沿着指针P[i]所指的子树继续查找。若k>K[n]，则沿着指针P[n]所指的子树继续查找。nP0K1P1K2P2…KnPn从前向后找到恰好大于k的K[i]8.3.3

B树6/61104268121618202428142226bdefghic根结点叶子结点层外部结点层查找关键字168.3.3

B树7/61向m阶B树中插入一个关键字k的步骤如下：3.B树的插入

（1）查找：从根结点开始比较，类似于查找过程，找到一个合适的叶子结点来插入关键字k。也就是说，关键字k一定是插入到某个叶子结点中。

（2）插入：在叶子结点x中插入关键字k。8.3.3

B树8/61在叶子结点x中插入关键字k。分为两种情况：若x结点的关键字个数小于MAX（m-1）

直接有序插入k。若x结点的关键字个数恰好为MAX，

分裂结点：k1

k2…km-1结点x有序插入kk1

k2…ks…km中间位置关键字结点x1分裂…ks…k1…ks-1ks+1…km结点x28.3.3

B树9/614.B树的创建给定一个关键字序列创建一棵m阶B树的过程是，从一棵空树开始，扫描所有的关键字k，采用前面介绍的B树插入方式将其插入到B树中。显然，m值的不同，构造的B树是不同的。8.3.3

B树10/61【例8.13】给定的关键字序列为（1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15），创建一棵5阶B树。这里m=5，结点中最大关键字个数MAX=m-1=4。112,6,712678.3.3

B树解11/61111267111271164,8,131247811136101247810111361246107811138.3.3

B树12/615,17,9,161245610789111316172012456107891113161720124561016789111317208.3.3

B树13/6131234561016789111317203610167891113172012348.3.3

B树14/6112,14,18,19361016789111213141718192012348.3.3

B树15/61153610167891112131415171819201234361013167891718192012341112141513163678917181920123411121415108.3.3

B树16/615.B树的删除在m阶B树中删除一个关键字k的步骤如下：

（1）查找：从根结点开始比较，类似于查找过程，找到包含关键字k的结点。

（2）删除：在该结点中删除关键字k分两种情况：一种是在叶子结点上删除关键字k；另一种是在非叶子结点上删除关键字k。8.3.3

B树17/61在非叶子结点上删除关键字k可以转化为在叶子结点中删除：如果这个非叶子结点中某个关键字ki=k，则以指针Pi所指子树中的最小关键字mink替代ki。mink所在的结点一定是叶子结点。然后在相应的叶子结点中删除mink；对称地：也可以用指针Pi-1所指子树中的最大关键字maxk替代ki，然后在相应的叶子结点中删除maxk。8.3.3

B树18/61（1）从y结点中删除关键字mink后，其中关键字个数仍大于等于MIN（MIN=

m/2

-1），直接删除关键字mink，删除过程结束。在B树的叶子结点y中删除关键字mink共有以下三种情况：14510MIN=3mink=5例如：14108.3.3

B树19/61（2）从y结点中删除关键字mink后，其中关键字个数少于MIN，而与y结点相邻的左兄弟（或右兄弟）结点中的关键字多于MIN个

则向兄弟借一个关键字。145MIN=3mink=5例如：8910…14689107…768.3.3

B树20/61（3）从y结点中删除关键字mink后，其中关键字个数少于MIN，而且y结点左右相邻的兄弟结点中的关键字都是MIN个

则可将y结点和它的双亲结点中的一个关键字合并到它的兄弟结点中。

如果这样合并后使双亲结点中的关键字少于MIN个，则需要继续进行合并，直到根结点。145MIN=3mink=5例如：7896…146789…8.3.3

B树21/61在索引文件组织中,经常使用B树的一些变形，其中B+树是一种应用广泛的变形。

一棵m阶B+树满足下列条件：

8.3.4B+树每个分支结点至多有m棵子树。根结点或者没有子树，或者至少有两棵子树。除根结点外，其他每个分支结点至少有

m/2

棵子树。有n棵子树的结点有n个关键字。8.3.4

B+树22/611028410246810121416182022242628142228sqtroot记录层叶子层一棵4阶的B+树示例：随机查找顺序查找8.3.4

B+树23/61所有叶子结点包含全部关键字及指向相应记录的指针，而且叶子结点按关键字大小顺序链接（可以把每个叶子结点看成是一个基本索引块，它的指针不再指向另一级索引块，而是直接指向数据文件中的记录）。所有分支结点（可看成是索引的索引）中仅包含它的各个子结点（即下级索引的索引块）中最大关键字及指向子结点的指针。

8.3.4

B+树24/61B+树中具有n个关键字的结点含有n棵子树，即每个关键字对应一棵子树。而在B树中，具有n个关键字的结点含有(n+1)棵子树。B+树中所有非叶子结点仅起到索引的作用，而所有叶子结点包含了全部关键字。而在B树中，叶子结点包含的关键字与其他结点包含的关键字是不重复的。B+树支持随机查找和顺序查找。而B树仅仅支持随机查找。8.3动态查找表

m阶的B+树和m阶的B树的差异：25/61哈希表（HashTable）又称散列表，是除顺序存储结构、链式存储结构和索引表存储结构之外的又一种存储结构。

8.4哈希表查找8.4.1哈希表的基本概念8.4哈希表查找26/61哈希函数h存储地址存储地址=h(key)n个对象个数m（m≥n）的连续内存单元8.4哈希表查找27/61学号姓名分数201201王实85201205李斌82201206刘英92201202张山78201204陈功90哈希表长度m=6（存储单元的地址为0～5）记录个数n=5哈希函数：h(学号)=学号-2012011.1数据结构概述地址学号姓名分数0201201王实851201202张山7823201204陈功904201205李斌825201206刘英92第1章学生成绩表28/61地址学号姓名分数0201201王实851201202张山7823201204陈功904201205李斌825201206刘英92O(1)，按关键字查找速度快哈希函数：h(学号)=学号-201201哈希表查找201204的学生姓名h(201204)=201204-201201=3地址3的记录姓名为"陈功"8.4哈希表查找29/61哈希函数：h(学号)=学号-201201如果n=30，m=35，但学号分布分散。学号201201，h(201201)=201201-201201=0…学号201250，h(201250)=201250-201201=49？哈希函数：h(学号)=(学号-201201)%m学号201201，h(201201)=(201201-201201)%35=0…学号201250，h(201250)=(201250-201201)=49%35=14问题18.4哈希表查找30/61h(201204)=(201204-201201)%35=3如果存在一个学号为201239,h(201239)=(201239-201201)%35=38%35=3?问题2哈希函数：h(学号)=(学号-201201)%m8.4哈希表查找31/61可能存在这样的问题，对于两个关键字ki和kj（i≠j），有ki≠kj（i≠j），但h(ki)=h(kj)。把这种现象叫做哈希冲突（同义词冲突）。如果出现同义词冲突，后存储的记录会覆盖前面存储的记录。这是不允许的！！！

需要解决哈希冲突8.4哈希表查找32/61设计好的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。设计解决冲突的方法。归纳起来，哈希表设计：8.4哈希表查找33/61构造哈希函数的目标：使得到的哈希地址尽可能均匀地分布在m个连续内存单元地址上，同时使计算过程尽可能简单以达到尽可能高的时间效率。根据关键字的结构和分布的不同，有多种构造哈希函数的方法。

8.4.2哈希函数构造方法8.4哈希表查找34/61以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。即h(k)=k+c。

这种哈希函数计算简单，并且不可能有冲突发生。当关键字的分布基本连续时，可用直接定址法的哈希函数；否则，若关键字分布不连续将造成内存单元的大量浪费。1.直接定址法8.4哈希表查找35/61学号姓名分数201201王实85201205李斌82201206刘英92201202张山78201204陈功90哈希表长度m=6（存储单元的地址为0～5）记录个数n=5哈希函数：h(学号)=学号-201201地址学号姓名分数0201201王实851201202张山7823201204陈功904201205李斌825201206刘英92第1章学生成绩表8.4哈希表查找36/61用关键字k除以某个不大于哈希表长度m的数p所得的余数作为哈希地址的方法。除留余数法的哈希函数h(k)为：h(k)=kmodp

(mod为求余运算，p≤m)p最好是质数（素数）。

2.除留余数法8.4哈希表查找37/61提取关键字中取值较均匀的数字位作为哈希地址的方法。适合于所有关键字值都已知的情况，并需要对关键字中每一位的取值分布情况进行分析。

3.数字分析法8.4哈希表查找38/61位序123456789231760292326875927396289234363492706816927746389238126292394220哈希地址的集合为{2，75，28，34，16，38，62，20}8.4哈希表查找39/618.4.3哈希冲突解决方法在哈希表中，虽然冲突很难避免，但发生冲突的可能性却有大有小。这主要与三个因素有关：与装填因子有关。所谓装填因子α是指哈希表中已存入的元素数n与哈希地址空间大小m的比值，即α=n/m。α越小，冲突的可能性就越小；但α越小，存储空间的利用率就越低。与所采用的哈希函数有关。与解决冲突的哈希冲突函数有关。8.4哈希表查找40/61发生冲突时查找周围一个空位置存放记录。设置一个查找周围一个空位置的函数。1.开放定址法8.4哈希表查找41/61从发生冲突的地址（设为d）开始，依次循环探测d的下一个地址（当到达下标为m-1的哈希表表尾时，下一个探测的地址是表首地址0），直到找到一个空闲单元为止。描述公式为：

d0=h(k)，di=(di-1+1)modm

(1≤i≤m-1)（1）线性探测法0123456789********8.4哈希表查找42/61问题：可能出现堆积现象：0123456789101112n=6,m=10,关键字为（10,11,12,19,20,21）哈希函数：h(key)=key%910，11，1219

h(19)=19%9=1（冲突）d0=1，d1=(1+1)%10=2（冲突）d2=(2+1)%10=3（冲突）d3=(3+1)%10=4（将19放在4位置）01234567891011121920

h(20)=20%9=2（冲突）d0=2，d1=(2+1)%10=3（冲突）d2=(3+1)%10=4（冲突）d3=(4+1)%10=5（将20放在5位置）哈希函数值不相同的多个记录争夺同一个后继哈希地址称为非同义词冲突8.4哈希表查找43/61发生冲突时前后查找空位置。描述公式为：

d0=h(k)，

di=(d0±i2)modm

(1≤i≤m-1)（2）平方探测法0123456789********8.4哈希表查找44/61平方探测法可以避免出现堆积问题。缺点是不能探测到哈希表上的所有单元，但至少能探测到一半单元。8.4哈希表查找45/61

【例8.15】假设哈希表长度m=13，采用采用除留余数法加线性探测法建立如下关键字集合的哈希表：(16,74,60,43,54,90,46,31,29,88,77)。n=11，m=13，除留余数法的哈希函数为：

h(k)=kmodp

p应为小于等于m的素数，假设p取值13。8.4哈希表查找解46/61哈希函数：h(k)=kmod13解决冲突方法：线性探测法h(16)=3 ha[3]=16,共1次探测h(74)=9 ha[9]=74,共1次探测h(60)=8 ha[8]=60,共1次探测h(43)=4 ha[4]=43,共1次探测h(54)=2 ha[2]=54,共1次探测h(90)=12 ha[12]=90,共1次探测h(46)=7 ha[7]=46,共1次探测h(31)=5 ha[5]=31,共1次探测8.4哈希表查找47/61h(29)=3 有冲突

d0=3，d1=(3+1)%13=4 仍有冲突

d2=(4+1)%13=5 仍有冲突

d3=(5+1)%13=6 ha[6]=29,共4次探测h(88)=10 ha[10]=88,共1次探测h(77)=12 有冲突

d0=12，d1=(12+1)%13=0 ha[0]=77，共2次探测8.4哈希表查找48/61下标0123456789101112k7754164331294660748890探测次数21111411111哈希表ha[0..12]ASLsucc=1*9+2*1+4*111=1.364成功的查找：在ha中找到对应的关键字h(77)=12 ha[12]=90≠77

d0=12，d1=(12+1)%13=0 ha[0]=77，共2次比较比较的次数=探测次数8.4哈希表查找49/61下标0123456789101112k7754164331294660748890哈希表ha[0..12]不成功的查找：在ha中找不到对应的关键字xh(x)=12 ha[12]≠x

d0=12，d1=(12+1)%13=0 ha[0]≠x

d2=(0+1)%13=1 ha[1]为空，查找失败，3次比较确定查找失败，一定有比较到空为止！8.4哈希表查找50/61哈希表ha中查找失败的所有情况的探测次数ASLunsucc=2+1+10+9+8+7+6+5+4+3+2+1+313=4.692下标0123456789101112k7754164331294660748890探测次数211098765432138.4哈希表查找51/61拉链法是把所有的同义词用单链表链接起来的方法。在这种方法中，哈希表每个单元中存放的不再是记录本身，而是相应同义词单链表的头指针。由于单链表中可插入任意多个结点，所以此时装填因子α根据同义词的多少既可以设定为大于1，也可以设定为小于或等于1，通常取α=1。2.拉链法8.4哈希表查找52/61

【例8.16】假设哈希表长度m=13，采用采用除留余数法加拉链法建立如下关键字集合的哈希表：(16,74,60,43,54,90,46,31,29,88,77)。8.4哈希表查找53/61

采用拉链法解决冲突建立的链表如下图所示。23∧0∧1∧67458∧111291054∧29

16∧43∧31∧46∧60∧74∧88∧77

90∧存放的不再是记录本身8.4哈希表查找解54/6123∧0∧1∧67458∧111291054∧29

16∧43∧31∧46∧60∧74∧88∧77

90∧成功的查找：在ha中找到对应的关键字ASLsucc=1*9+2*211=1.18h(77)=12，在ha[12]的单链表中共1次比较比较的次数=对应结点在单链表中的序号8.4哈希表查找55/6123∧0∧1∧67458∧111291054∧29

16∧43∧31∧46∧60∧74∧88∧77

90∧ASLunsucc=1*7+2*213=0.846h(x)=3，在ha[3]的单链表中共2次比较比较的次数=对应单链表