第09章-2 查找

1、第九章查找n9.1 静态查找表n9.2 动态查找表n9.3 哈希表29.2 动态查找表nB-树（平衡多路查找树）及其查找 一棵m阶的B-树，或为空树，或为满足下列性质的m叉树：树中每个结点最多有m棵子树；若根结点不是叶子结点，则至少有两棵子树；除根结点之外的非叶子结点至少有m/2棵子树；结点的结构如下：（n，A0，K1，A1，K2，An-1，Kn，An） 其中Ki表示关键字，且KiKi+1；Ai表示孩子结点指针，且Ai-1所指子树中的所有结点的关键字均小于Ki；n为结点中关键字的个数，m/2-1nm-1；所有的叶子结点都出现在同一层上，并且不带信息。3 以下是一个3阶B-树，除根结点外，每个结

2、点中的子树个数不少于2，不多于3，即每个结点中最多含有2个关键字，最少含有1个关键字。241547211792838335549653089769892 4nB-树及其查找 在B-树上查找关键字Kn从根结点出发，先在结点上查找K，则若找到，则查找成功；如果KiKKi+1，沿Ai 子树继续查找；如果KKn，沿An子树继续查找。n若在叶子结点中查找失败，则查找失败。9.2 动态查找表59.2 动态查找表nB-树的插入和删除向B-树中增加新的记录n新增记录将被插入到叶子结点上；n先通过查找操作，定位待插入的叶子结点，再向叶子结点中插入新记录；n如果插入后结点中的记录个数（关键字个数）超过阶数-1，则

3、进行分裂调整；69.2 动态查找表nm阶B-树的插入和删除分裂调整n当插入新记录后的结点中关键字个数超过m-1时：E1：将结点的中间记录抽出，将结点分裂为两个结点；E2：将中间记录加入到其父结点中；E3：如果父结点失衡，继续对父结点作出调整。756238731263547523523568731265247例：在一棵5阶B-树上，插入新结点后的分裂调整。9.2 动态查找表8设输入序列：45, 32, 16, 77, 94, 38, 44, 21, 39, 68, 33, 26构造3阶B-树454532 3216453216453216774532167745947732164594773216

4、944538773216944438454432771638459416384594327744384594327744211645943277442116393894327744211639386845943277442116684538333994774421166845383233399477446845383233392116269477446845333916263221389477684533391626213844329nB-树的插入和删除从B-树中删除记录n先通过查找操作，定位待删除的记录；n从记录所在结点上删除该记录；n若被删除记录的结点为最下层的非叶子结点，且结点中的记录数

5、不少于阶数/2，则删除完成，否则须进行合并调整；9.2 动态查找表10- 合并调整被删除关键字所在结点中关键字数目不小于m/2则只需从该结点删去该关键字Ki；被删除关键字所在结点中关键字数目等于m/2-1,而与该结点相邻的右兄弟(或左兄弟)结点中关键字数目大于m/2-1,则需将其兄弟结点中的最小(或最大)的关键字上移至双亲结点中，而将双亲中小于(或大于)且紧靠该上移关键字的关键字下移至被删关键字所在结点中。被删除关键字结点和其相邻的兄弟结点中的关键字数目均等于m/2-1.假设该结点有右兄弟,且其右兄弟结点地址由双亲结点中的指针Ai所指,则在删去关键字之后,它所在结点中剩余的关键字和指针,加上双

6、亲结点中的关键字Ki一起,合并到Ai所指兄弟结点中。9.2 动态查找表11153677416545515915417745655159123742596166355672132281893756355972132281896166当被删除记录的结点中的记录数低于下限，当被删除记录的结点中的记录数低于下限，如果兄弟结点中有富余的记录，则向其兄弟结点借记录。如果兄弟结点中有富余的记录，则向其兄弟结点借记录。下面是从一个下面是从一个5阶阶B-树中删除一条记录的例子。树中删除一条记录的例子。13375635597213228189616613228189357237596166当被删除记录的结点中的记

7、录数低于下限，且其兄弟结点当被删除记录的结点中的记录数低于下限，且其兄弟结点中没有富余的记录，则与其兄弟合并。中没有富余的记录，则与其兄弟合并。下面是从一个下面是从一个5阶阶B-树中删除一条记录的例子。树中删除一条记录的例子。14452453 903 12375061 70100452453 903375061 70100452461 90337537010045249033761 7010045903 2461 7010045 903 2461 7010045 903 2461 70100从下面的从下面的3阶阶B-树中依次删去：树中依次删去：12, 50, 53, 3715nB+树B+树是一

8、种变异的B-树。有n棵子树的结点中含有n个关键字。所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。1.所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大（或最小）关键字。9.2 动态查找表169.3 哈希表 前面我们所介绍的三种查找方法的共同特点在于：通过对关键字的一系列比较，逐步缩小查找范围，直到确定记录的存储位置或确定查找失败。 哈希法则希望不经过任何比较，一次存取就能得到所查记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的函数对应关系，使得每个关键字和结构中一个唯一的存储位置相对应，这样查找时只需

9、对记录的关键字进行某种运算就能确定结点在表中的位置。称这个对应关系为哈希函数。 n哈希函数17 假定某教室有35个座位，如果不加限定让学生任意就座，则要找某个学生时就要将待找学生与当前座位上的学生一一做比较，这就是我们前面所介绍的查找方法的大致思路。 哈希法则要限定学生所坐的位置，比如可规定学生座位的编号应与其学号的末两位相同，则学号为993605的学生应坐编号为5的座位。这样我们要找某个学生时只需根据其学号的末两位到相应座位上去找即可，不必一一比较了。 在这个例子里，学生好比记录，学号则为关键字，对关键字进行的操作则是取其末两位，用以确定记录的位置。 n哈希法举例9.3 哈希表9.3 哈希表

10、n哈希法举例9.3 哈希表18gassummeryockbloodzoomJohn0123Hash表summerpictureplatemomentpleasurebeachcompanygaszoombloodfrenchJohnnewlandyockH(key)集合n思想9.3 哈希表19哈希函数是一个映射函数，哈希函数的设定很灵活，只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围内即可。对不同的关键字可能得到同一哈希地址，即key1key2，而H(key1)=H(key2),这种现象称为冲突。根据设定的哈希函数H（key）和处理冲突的方法将一组关键字映像到一个有限的连续的地址集

11、上，并以函数值作为记录在表中的存储位置，这样构建的表称为哈希表或散列表，所得存储位置称为哈希地址或散列地址。n相关概念9.3 哈希表20散列函数的常用构造方法散列函数的常用构造方法n选择法选择法n叠加法叠加法n折叠法折叠法n模除法模除法n数乘法数乘法n平方取中法平方取中法n基数转换法基数转换法n伪随机法伪随机法n哈希/散列函数9.3 哈希表21如何能尽量避免冲突？如果发生冲突，该如何解决？n实现哈希查找待解决的问题9.3 哈希表22 若对于关键字集合中的任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数为均匀的哈希函数。 直接定址法：直接取关键字本身或者关键字

12、加上一个常数作为哈希地址。H(key)=key或H(key)=a*key+b 由于直接定址所得地址集合和关键字集合的大小相同。因此，对于不同的关键字不会发生冲突。但实际中能够使用这种哈希函数的情况很少。n哈希函数的构造方法9.3 哈希表23数学分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道，则可取关键字的若干数位组成哈希地址。8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5.

13、 分析：分析： 只取只取8 只取只取1 只取只取3、4 只取只取2、7、5 数字分布近乎随机数字分布近乎随机所以：取所以：取任意组合作哈希地址任意组合作哈希地址n哈希函数的构造方法9.3 哈希表24平方取中法：取关键字平方后的中间几位为哈希地址。折叠法：将关键字分割成位数相同的几部分（最后一部分可以不同），然后取这几部分的叠加和作为哈希地址。关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到哈希函数。n哈希函数的构造方法9.3 哈希表25除留余数法：取关键字被某个不大于哈希表表长m的数p 除后所得余数为哈希地址。这是一种最简单，也是最常用的构造哈希函数的方法。H(key

14、) = key % p ( pm )n哈希函数的构造方法9.3 哈希表选择哈希函数需考虑的因素：计算哈希值所需时间关键字的长度哈希表的大小关键字的分布情况记录的查找频率26 在设计或选用哈希函数时希望由它得到的地址能均匀散列分布在哈希表的空间中，即每个关键字能唯一对应表中的一个地址。但可能出现多个关键字对应一个地址的情况，这种情况称为冲突。解决冲突的方法是为同义词（哈希值相同的关键字）另外寻找一个新地址。开放定址法：按某种方法在哈希表中形成一个探查地址序列Hi，沿着这个序列在哈希表中逐个查找，直到碰到无冲突（找到或该位置为空）的位置为止。H Hi i=(H(key)+d=(H(key)+di

15、i)% m i=1,2,k(k=m-1)% m i=1,2,k(k=m-1)n处理冲突的方法9.3 哈希表di:增量序列；根据di取值的不同形式，可有多种探测法。27开放定址法：按某种方法在散列表中形成一个探查地址序列，沿着这个探查地址序列在数组中逐个查找，直到碰到无冲突的位置为止，并放入记录。H Hi i=(H(key)+d=(H(key)+di i)% m i=1,2,k(k=m-1)% m i=1,2,k(k=m-1)n处理冲突的方法9.3 哈希表一次线性探测法：di=1,2,3,4,5,，m-1二次探测法：di=12, -12,22,-22,28再哈希法：在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。 H Hi i=RH=RHi i(key) i=1,2,k(key) i=1,2,k链地址法：将所有关键字为同义词的记录存储在同一个线性链表中。 建立一个公共溢出区：所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。n处理冲突的方法9.3 哈希表29n散列表上的查找E1：计算H(key)，获得存储地址；E2：nE21：如果冲突，按照冲突解决策略，计算下一个地址；nE22:循环直到元素为空或等于keyE3：若元素为空，则查找失败，否则查找成功。n散列