王道

查找

p270

【考纲内容】

(一）查找的基本概念

(二）顺序查找法

(三）分块查找法

(四）折半查找法

(五）B树及其基本操作、B+树的基本概念

(六）散列表

(七）查找算法的分析及应用

【知识框架】

基本概念:静态查找、动态查找
线性结构
- 顺序查找
- 折半查找
- 分块查找
树形结构
- 二叉排序树
- 二叉平衡树
- B树、B+树
散列结构-散列表
- 性能分析
- 冲突处理
效率指标一平均查找长度
- 查找成功
- 查找失败

【复习提示】

本章是考研命题的重点。对于散列查找，应掌握散列表的构造、冲突处理方法(各种方法的处理过程)、查找成功和查找失败的平均查找长度、)列食找的付征D出1的非占对王P城掌握折半查找的过程、构造判定树、分析平均查找长度等。B树和B+树是本章的难点。对于B树，考研大纲要求掌握插入、删除和查找的操作过程;对于B+树，仅要求了解其基本概念和性质。

单词	含义
ASL,Average Search Length	平均查找长度

查找算法的总结

查找方式	$ASL_{\text{成功}}$	$ASL_{\text{不成功}}$	$ASL$	数组	链表	关键字是否要求有序	其他
顺序查找	$\dfrac{n+1}{2}$	$n +1$		$\color{green}{\checkmark}$	$\color{green}{\checkmark}$	$\color{red}{\times}$	可使用哨兵
有序表的顺序查找	$\dfrac{n+1}{2}$	$\dfrac{n}{2} + \dfrac{n}{n+1}$		$\color{green}{\checkmark}$	$\color{green}{\checkmark}$	$\color{green}{\checkmark}$
折半查找(二分查找)	$\dfrac{n+1}{n} log_2(n+1) -1 $，不超过$\lfloor log_2(n) \rfloor + 1$	不超过$\lfloor log_2(n) \rfloor + 1$	$\dfrac{n+1}{n} log_2(n+1) -1 $,n>50近似$log_2(n+1)-1$	$\color{green}{\checkmark}$	$\color{red}{\times}$	$\color{green}{\checkmark}$
分块查找			$ \dfrac{s^2+2s+n}{2s} $ $\lceil log_2(b+1) \rceil + \dfrac{s+1}{2}$				结合了顺序查找和折半查找的优点，既有动态结构，又适于快速查找块内无序，快间有序

B-树就是b树

$\color{red}{\text{Q}}$：线性探查再散列退化成线性探测的情况

查找的基本概念

1)查找。在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为两种:一是$\color{green}{\text{查找成功}}$，即在数据集合中找到了满足条件的数掂$\color{green}{\text{元素}}$;二定$\color{green}{\text{查找失败}}$。

2）查找表（查找结构)。用于查找的数据集合称为$\color{green}{\text{查找表}}$，它田同一类型的数据元素（或记录）组成，可以是一个数组或链表等数据类型。对查找表经常进行的操作一般有4种:①查询某个特定的数据元素是否在查找表中;②检索满足条件的某个特定的数据元素的各种属性;③在查找表中插入一个数据元素;④从查找表中删除某个数据元素。

3）静态查找表。若一个查找表的操作只涉及上述操作①和②，则无须动态地修改查找表，此类查找表称为$\color{green}{\text{静态查找表}}$。与此对应，需要动态地插入或删除的查找表称为$\color{green}{\text{动态查找表}}$。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等;适合动于的查找方法有二叉排序树的查找、散列查找等。二叉平衡树和B树都是二叉排序树的改进。二叉排序树与二叉平衡树已在第4章介绍过。

4）关键字。数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找,查找结果应该是唯一的。例如，在由一个学生元素构成的数据集合中，学生元素中“学号”这一数据项的值唯一地标识一名学生。

5）平均查找长度。在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为

$\color{red}{\text{需要比较的关键字次数}}$,也就是有点像算法的时间复杂度的概念，循环中一段语句如果执行了>,=,<三次比较，那么他就算这一次中的查找长度为1(这段话用来解释有序表的顺序查找的asl)：虽然感觉很莫名奇妙，明明在代码中执行了三次比较
update:还是很奇怪，2010有一道真题，不成功就是按照最后一个成功节点的比较次数来算的（王道所有关于不成功的比较次数的题目都可以看作是2010真题的变种）；关于成功查找所需要的次数，按照严书对于一个判定树第一个节点就算一次比较，王道书在顺序查找时，自己对顺序表造了个比较查找，此时的判定树认为边才是查找长度；如题14，又是按照严书的定义来的(汗。。。)。$\color{red}{\text{结论}}$：定义还是以真题和严的教材为准；不论是严书还是王道，查找所需的次数 = 查找长度，查找失败的分母为失败节点的个数

$ASL = \displaystyle_{i=1}^n P_iC_i$

式中，$n$是查找表的长度；$P_i$是查找第$i$个数据元素的概率，一般认为每个数据元素的查找概率相等，即$P_i$找概率相等，即$P_i = 1/n$;$C_i$是找到第i个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。

顺序查找和折半查找

顺序查找

作为一种最直观的查找方法，其基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置;若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。下面给出其算法，主要是为了说明其中引入的“$\color{red}{\text{哨兵}}$”的作用。

一般线性表的顺序查找

typedef struct { //查找表的数据结构
  ElemType *elem; //元素存储空间基址,建表时按实际长度分配,0号单元留空
  int TableLen; //表的长度
}SSTable;

int Search Seq (SSTable ST, ElemType key){
  ST.elem [0]=key;//“哨兵”
  for(i=ST.TableLen;ST.elem[i]!=key;--i);//从后往前找
    return i;//若表中不存在关键字为key的元素，将查找到1为0时退出for循环
}

在上述算法中，将ST.elem[ 0]称为“$\color{green}{\text{哨兵}}$”。引入它的目的是使得search_Seq内的循环不必判断数组是否会越界，因为满足i==0时，循环一定会跳出。需要说明的是，在程序中引入“哨兵”并不是这个算法独有的。引入“哨兵”可以避免很多不必要的判断语句，从而提高程序效率。

$\color{red}{\text{Q}}$:在什么时候再次使用了“哨兵”？提高程序效率从何谈起？

对于有n个元素的表，给定值key与表中第i个元素相等，即定位第i个元素时，需进行n-i+1次关键字的比较，即$C_i = n - i + 1$。查找成功时，顺序查找的平均长度为

$ASL_{\text{成功}} = \displaystyle \sum_{i=1}^n P_i(n-i+1)$

$i$从1开始计数，当$i$=n时(即查找的元素与最后一个元素相等)，显然比较了一次（key与最后一个元素比较）

当每个元素的查找概率相等，即$P_i= 1/n$时，有

$ASL_{\text{成功}} = \displaystyle \sum_{i=1}^n P_i(n-i+1) = \dfrac{n+1}{2}$

首项1，加末项n，的和(n+1)，乘以项数(n)，除以2.

查找不成功时，与表中各关键字的比较次数显然是$n+1$次，从而顺序查找不成功的平均查找长度为$ASL_\text{不成功}= n +1$。

通常，查找表中记录的查找概率并不相等。若能预先得知每个记录的查找概率.则应先对记录的查找概率进行排序，使表中记录按查找概率由大至小重新排列。

综上所述，顺序查找的缺点是当n较大时，平均查找长度较大，效率低;优点是对数据元素的存储没有要求，顺序存储或链式存储皆可。对表中记录的有序性也没有要求，无论记录是否按关键字有序，均可应用。同时还需注意，对线性的链表只能进行顺序查找。

有序表的顺序查找

若在查找之前就已经知道表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。

假设表工是按关键字从小到大排列的,查找的顺序是从前往后,待查找元素的关键字为key,当查找到第i个元素时，发现第i个元素对应的关键字小于key，但第i+1个元素对应的关键字大于key，这时就可返回查找失败的信息，因为第i个元素之后的元素的关键字均大于key，所以表中不存在关键字为key的元素。

可以用如图7.1所示的判定树来描述有序线性表的查找过程。树中的圆形结点表示有序线性表中存在的元素;树中的矩形结点称为失败结点（若有$n$个结点，则相应地有$n +1$个查找失败结点)，它描述的是那些不在表中的数据值的集合。若查找到失败结点，则说明查找不成功。

在有序线性表的顺序查找中，查找成功的平均查找长度和一般线性表的顺序查找一样。查找失败时，查找指针一定走到了某个失败结点。这些失败结点是我们虚构的空结点，实际上是不存在的，所以到达失败结点时所查找的长度等于它上面的一个圆形结点的所在层数。查找不成功的平均查找长度在相等查找概率的情形下为

$ASL_{\text{不成功}} = \displaystyle \sum_{j=1}^n q_j(l_j -1) = \dfrac{1+2+\cdots+n+n}{n+1} = \dfrac{n}{2} + \dfrac{n}{n+1}$

l:level
???搞笑吗，$n \to \infty$,你这个算法$ASL$比没有没有优化过更差

式中,$qj$是到达第$j$个失败结点的概率，在相等查找概率的情形下，它为$1/(n + 1)$; $l_j$是第$j$个失败结点所在的层数。当n=6时，$ASL{\text{不成功}} =6/2＋6/76=3.8$，比一般的顺序查找算法好一些。

注意，有序线性表的顺序查找和后面的折半查找的思想是不一样的，且有序线性表的顺序查找中的线性表可以是链式存储结构。

折半查找

折半查找又称$\color{green}{\text{二分查找}}$，它仅适用于$\color{red}{\text{有序的顺序表}}$。

折半查找的基本思想:首先将给定值key 与表中中间位置的元素比较,若相等，则查找成功，返回该元素的存储位置;若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分(例如，在查找表升序排列时,若给定值key大于中间元素，则所查找的元素只可能在后半部分)。然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。算法如下:

折半查找的代码

int Binary Search (SeqList L, ElemType key)i
  int  low=0,high=L.TableLen-1 , mid;
  while (low<=high){
    mid=(int) (low+high) /2;//取中间位置
    if(L.elem [mid]==key)
      return mid;//查找成功则返回所在位置
    else if (L.elem[mid] >key)
      high = mid-1;//从前半部分继续查找
    else low = mid+1; //从后半部分继续查找
  }
  return -1; //查找失败,返回-1
}

n偶数的话，mid选左边的那个数
如果没有元素high=-1,直接跳出循环返回-1
如果有一个$\color{green}{\text{元素}}$，初始mid=low=high=0，${\textstyle\unicode{x2460}}$ $\color{red}{\text{查找的元素}}$就是这个元素，在第六行就返回所查找的元素；${\textstyle\unicode{x2461}}$ 如果$\color{red}{\text{查找的数}}$比这个$\color{green}{\text{元素}}$小的话,第二次执行循环，high=-1，low=0,low>high退出循环；${\textstyle\unicode{x2462}}$ 如果$\color{red}{\text{查找的数}}$比这个$\color{green}{\text{元素}}$大，第二次执行循环，low=1，high=0，low>high退出循环

二分查找的例子

第四次查找，此时子表只含有一个元素，且10≠11，故表中不存在待查元素。

折半查找的过程可用图7.2所示的二叉树来描述，称为$\color{green}{\text{判定树}}$。树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值;树中最下面的叶结点都是方形的，它表示查找不成功的情况。从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点数，而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数;每个结点值均大于其左子结点值，且均小于于其右子结点值。若有序序列有n个元素，则对应的判定树有n个圆形的非叶结点和n+1个方形的叶结点。显然，$\color{green}{\text{判定树是一棵平衡二叉树}}$。

在等概率由上述分析可知，用折半查找法查找到给定值的比较次数最多不会超过树的高度。查找时,查找成功的平均查找长度为

$ASL = \dfrac{1}{n} \displaystyle \sum_{i=1}^n l_i = \dfrac{1}{n}(1 \times 1 + 2 \times 2 + \cdots + h \times 2^{h-1}) = \dfrac{n+1}{n} log_2(n+1) -1$

推到方法：乘公比的式子减去原式除以公比-1，参考文献
此推导的的详细证明：严书p221

二分查找更详细的证明

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210709183415.png)

式中，$h$是树的高度，并且元素个数为$n$时树高$h = \lceil log_2(n + 1) \rceil$。所以，折半查找的时间复杂度为$O(log_2n)$，平均情况下比顺序查找的效率高。

在图7.2所示的判定树中，在等概率情况下，查找成功(圆形结点)的ASL=(1×1＋2×2＋3×4+4×4)/11=3，查找不成功（方形结点）的ASL=(3×4＋4×8)/12= 11/3。

因为折半查找需要方便地定位查找区域,所以它要求线性表必须具有随机存取的特性。因此，该查找法仅适合于顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列。

分块查找

分块查找又称$\color{green}{\text{索引顺序查找}}$，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。

分块查找的基本思想:将查找表分为若干子块。块内的元素可以无序，但块之间是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

分块查找的过程分为两步:第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表;第二步是在块内顺序查找。

例如,关键码集合为{88,24,72,61,21,6,32,11,8,31, 22,83,78,54},按照关键码值24,54,78,88，分为4个块和索引表，如图7.3所示。

分块查找的平均查找长度为索引查找和块内查找的平均长度之和。设索引查找和块内查找的平均查找长度分别为$L_I, L_S$，则分块查找的平均查找长度为$ASL = L_I + L_S$

将长度为n的查找表均匀地分为b块，每块有s个记录，在等概率情况下，若在块内和索引表中均采用顺序查找，则平均查找长度为

$ASL = l_I + L_S = \dfrac{b+1}{2} + \dfrac{s+1}{2} = \dfrac{s^2+2s+n}{2s}$

此时，若$s=\sqrt{n}$，则平均查找长度取最小值$\sqrt{n}+1$;若对索引表采用折半查找时，则平均查找长度为

$ASL = L_I + L_S = \lceil log_2(b+1) \rceil + \dfrac{s+1}{2}$

B树和B+树

考研大纲对B树和 B+树的要求各不相同，重点在于考查B树，不仅要求理解B树的基本特点，还要求掌握B树的建立、插入和删除操作，而对B+树则只考查基本概念。

$\color{red}{\text{Q}}$：删除中间节点(分支节点)

替换并删除，严书中的描述如下

反之,若在B-树上删除一个关键字,则首先应找到该关键字所在结点,并从中删除之,若该结点为最下层的非终端结点,且其中的关键字数目不少于$\lceil m/2 \rceil$,则删除完成,含则要进行“合并”结点的操作。假若所删关键字为非终端结点中的$K_i$则可以指针$A_i$所指子树中的最小关键字$Y$替代$K_i$,然后在相应的结点中删去$\text{Y}$。例如,在图9.16(a)的B-树上删去45,可以 f结点中的50替代45,然后在 f结点中删去50。因此，下面我们…

$\color{red}{\text{Q}}$: 插入操作一定是在叶子进行吗

可以这么理解，严书中的描述如下

每次插入一个关键字不是在树中添加一个叶子结点,而是首先在,若该结点的关键字个数不超过m-1,则插最低层的某个非终端结点中添加一个关键字，入完成,否则要产生结点的“分裂”,如图9.16所示。

B树及其基本操作

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树:

1）树中每个结点至多有 $\color{green}{\text{m}}$ 棵子树，即至多含有 $\color{green}{\text{m-1}}$ 个关键字。

2）若根结点不是终端结点，则至少有两棵子树。

3）除根结点外的所有非叶结点至少有$\lceil m/2 \rceil$棵子树，即至少含有$\lceil m/2- 1 \rceil$ 个关键字

4）所有非叶结点的结构如下:

n是指关键字的个数；B树的深度：严书中只提到了深度，是包含叶子节点的，
在树的基本术语中，高度和深度在值上是相等的
b树的阶数是预设的(天勤看原论文得出的结论)

原论文

![](https://raw.githubusercontent.com/ednow/cloudimg/main/githubio/20210710145315.png)

其中，$Ki(i= 1,2,\dots, n）$为结点的关键字，且满足$K_1 < K_2 < \cdots <K_n$; $P_i(i=0,1,\cdots, n）$为指向子树根节点的指针，且指针$P{i-1}$所指子树中所有节点的关键字均小于$K_i$,$P_i$所指子树中所有节点的关键字均大于$K_i$,$n(\lceil m/2 \rceil) -1 \leq n \leq m -1$为节点中关键字的个数

5）所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空)。

B树是所有结点的平衡因子均等于О的多路平衡查找树。

图7.4所示的B树中所有结点的最大孩子数m = 5，因此它是一棵5阶B树，在m阶B树中结点最多可以有m个孩子。可以借助该实例来分析上述性质:

1）$\color{green}{\text{结点的孩子个数}}$等于该结点中关键字个数加1。

2）如果根结点没有关键字就没有子树，此时B树为空;如果根结点有关键字，则其子树必然大于等于两棵，因为子树个数等于关键字个数加1。

3）除根结点外的所有非终端结点至少有$\lceil m/2 \rceil =\lceil 5/2 \rceil =3$棵子树（即至少有$\lceil m/2 \rceil - 1=\lceil 5/2 \rceil -1=2$个关键字)，至多有5棵子树(即至多有4个关键字)。

4）结点中关键字从左到右递增有序，关键字两侧均有指向子树的指针，左边指针所指子树的所有关键字均小于该关键字，右边指针所指子树的所有关键字均大于该关键字。或者看成下层结点关键字总是落在由上层结点关键字所划分的区间内，如第二层最左结点的关键字划分成了3个区间:(-$\infty$, 5), (5,11), (11,+$\infty$)，该结点3个指针所指子树的关键字均落在这3个区间内。

5）所有叶结点均在第4层，代表查找失败的位置。

树的高度（磁盘存取次数)

由下一节将得知，B树中的大部分操作所需的磁盘存取次数与B树的高度成正比。

下面来分析B树在不同情况下的高度。当然，首先应该明确B树的高度不包括最后的不带任何信息的叶结点所处的那一层（有些书对B树的高度的定义中，包含最后的那一层)

若$n\geq1$，则对任意一棵包含$n$个关键字、高度为$h$、阶数为$m$的$B$树:

1）因为B树中每个结点最多有m棵子树，m -1个关键字，所以在一棵高度为h的m阶B树中关键字的个数应满足$n≤(m - 1)(1 +m+ m^2+ \cdots+ m^{h-1})=m^h- 1$，因此有

$h \geq log_m (n+1)$

2）若让每个结点中的关键字个数达到最少，则容纳同样多关键字的B树的高度达到最大。由B树的定义:第一层至少有1个结点;第二层至少有2个结点;除根结点外的每个非终端结点至少有$\lceil m/2 \rceil$棵子树，则第三层至少有$2\lceil m/2 \rceil$个结点$\cdots \cdots$第$h +1$层至少有$2(\lceil m/2 \rceil )^{h-1}$个结点，注意到第h＋1层是不包含任何信息的叶结点。对于关键字个数为n的B树，叶结点即查找不成功的结点为$n+1$，由此有$n+1 \geq 2(\lceil m/2 \rceil )^{h-1}$，即$h \leq log\lceil m/2 \rceil((n+1)/2) + 1$

例如，假设一棵3阶B树共有8个关键字，则其高度范围为2≤h≤3.17。

B树的查找

在B树上进行查找与二叉查找树很相似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定。

B树的查找包含两个基本操作:①在B树中找结点;②在结点内找关键字。由于$\color{green}{\text{B树常存储在磁盘上}}$，因此前一个查找操作是在磁盘上进行的，而后一个查找操作是在内存中进行的，即在找到目标结点后，先将结点信息读入内存，然后在结点内采用顺序查找法或折半查找法。

在B树上查找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应的指针信息到所指的子树中去查找（例如，在图7.4中查找关键字42，首先从根结点开始，根结点只有一个关键字，且42>22，若存在，必在关键字22的右边子树上，右孩子结点有两个关键字，而36<42<45，则若存在，必在36和45中间的子树上，在该子结点中查到关键字42，查找成功)。查找到叶结点时（对应指针为空指针)，则说明树中没有对应的关键字，查找失败。

B树的插入

与二叉查找树的插入操作相比，B树的插入操作要复杂得多。在二叉查找树中，仅需查找到需插入的终端结点的位置。但是，在B树中找到插入的位置后，并不能简单地将其添加到终端结点中，因为此时可能会导致整棵树不再满足B树定义中的要求。将关键字key插入B树的过程如下:

1）定位。利用前述的B树查找算法，找出插入该关键字的最低层中的某个非叶结点(在B树中查找key时，会找到表示查找失败的叶结点，这样就确定了最底层非叶结点的插入位置。注意:插入位置一定是最低层中的某个非叶结点)。

2）插入。在B树中，每个非失败结点的关键字个数都在区间$[\lceil m/2 \rceil -1,m-1]$内。插入后的结点关键字个数小于$m$，可以直接插入;插入后检查被插入结点内关键字的个数当插入后的结点关键字个数大于$m-1$时，必须对结点进行分裂。

分裂的方法是:取一个新结点，在插入 key后的原结点，从中间位置($\lceil m/2 \rceil$ )将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置($\lceil m/2 \rceil$)的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B树高度增1。

对于m =3的B树，所有结点中最多有m-1=2个关键字，若某结点中已有两个关键字，则结点已满，如图7.5(a)所示。插入一个关键字60后，结点内的关键字个数超过了m-1，如图7.5(b)所示，此时必须进行结点分裂，分裂的结果如图7.5(c)所示。

B树的删除

B树中的删除操作与插入操作类似，但要稍微复杂一些，即要使得删除后的结点中的关键字个数≥$\lceil m/2 \rceil$-1，因此将涉及结点的“合并”问题。

当被删关键字k不在终端结点（最低层非叶结点）中时，可以用k的前驱（或后继）k’来替代k，然后在相应的结点中删除k’，关键字k必定落在某个终端结点中，则转换成了被删关键字在终端结点中的情形。在图7.6的4阶B树中，删除关键字80，用其前驱78替代，然后在终端结点中删除78。因此只需讨论删除终端结点中关键字的情形。

当被删关键字在终端结点（最低层非叶结点）中时，有下列三种情况:

1）直接删除关键字。若被删除关键字所在结点的关键字个数≥$\lceil m/2 \rceil$，表明删除该关键字后仍满足B树的定义，则直接删去该关键字。

2）兄弟够借。若被删除关键字所在结点删除前的关键字个数 =$\lceil m/2 \rceil - 1$，且与此结点相邻的右（或左）兄弟结点的关键字个数≥$\lceil m/2 \rceil$，则需要调整该结点、右(或左）兄弟结点及其双亲结点(父子换位法)，以达到新的平衡。在图7.7(a)中删除4阶B树的关键字65，右兄弟关键字个数 >$\lceil m/2 \rceil =2$，将71取代原65的位置，将74调整到71的位置。

3）兄弟不够借。若被删除关键字所在结点删除前的关键字个数=$\lceil m/2 \rceil - 1$，且此时与该结点相邻的左、右兄弟结点的关键字个数均 =$\lceil m/2- 1 \rceil$，则将关键字删除后与左（或右)兄弟结点及双亲结点中的关键字进行合并。在图7.7(b)中删除4阶B树的关键字5，它及其右兄弟结点的关键字个数=$\lceil m/2 \rceil - 1=1$，故在5删除后将60合并到65结点中。

在合并过程中，双亲结点中的关键字个数会减1。若其双亲结点是根结点且关键字个数减少至0(根结点关键字个数为1时，有2棵子树)，则直接将根结点删除，合并后的新结点成为根;若双亲结点不是根结点，且关键字个数减少到$\lceil m/2 \rceil -2$，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合B树的要求为止。

严书p245页最后一个例子，剩余的可以用天勤的动画理解

严书p245页最后一个例子

</details>

B+树的基本概念

B+树是应数据库所需而出现的一种B树的变形树。

一棵m阶的B+树需满足下列条件:

1）每个分支结点最多有m棵子树（孩子结点)。

2）非叶根结点至少有两棵子树，其他每个分支结点至少有$\lceil m/2 \rceil$棵子树。

3）结点的子树个数与关键字个数相等。

4)所有叶结点包含全部关键字及指向相应记录的指针，叶节点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。

5）所有分支结点(可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。

m阶的B+树与m阶的B树的主要差异如下:

1)在B+树中，具有$n$个关键字的结点只含有$n$棵子树，即每个关键字对应一棵子树;而在B树中，具有$n$个关键字的结点含有$n+1$棵子树。

2)在B+树中，每个结点(非根内部结点)的关键字个数n的范围是$\lceil m/2 \rceil$≤n≤m(根结点:1≤n$<m$);在B树中，每个结点（非根内部结点）的关键字个数n的范围是$\lceil m/2 \rceil$ -1≤n$< m -1$（根结点:1≤n≤m- 1)。

3)在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的仔储地址。

4)）在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中;而在B树中，叶结点（最外层内部结点）包含的关键字和其他结点包含的关键字是不重复的。

图7.8所示为一棵4阶B+树。可以看出，分支结点的某个关键字是其子树中最大关键字的副本。通常在B+树中有两个头指针:一个指向根结点，另一个指向关键字最小的叶结点。因此可以对B+树进行两种查找运算:一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。

B+树的查找、插入和删除操作和B树的基本类似。只是在查找过程中，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，直到叶结点上的该关键字为止。所以，在 B+树中查找时，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。

B树和B+树的区别
在$\color{green}{\text{B+}}$树中，具有$\color{green}{\text{n}}$个关键字的结点含有$\color{green}{\text{n}}$个分支;而在$\color{red}{\text{B-}}$树中，具有$\color{red}{\text{n}}$个关键字的结点含有$\color{red}{\text{n+1}}$个分支。
在B+树上有一个指针指向关键字最小的叶子结点，所有叶子结点链接成一个$\color{green}{\text{线性链表}}$,而B-树没有。

散列表

$\color{red}{\text{Q}}$ ：有hash冲突后的查找查找操作是怎么样的；拉链法很好理解，线性探查之后该怎么查找元素呢？

使用冲突处理函数继续查找，如果遇到了空位置就证明不存在，如果第二次扫描到了第一次查找冲突时的位置，也代表失败了
查找失败：注意空位置算不算一次比较
注意:查找不成功的位置是Hash函数所能映射到的位置，而不是表中所有位置!

$\color{red}{\text{Q}}$ ：插入删除操作是怎么样的

$\color{red}{\text{Q}}$ 如果有hash冲突，查找操作还是O(1)?

比如拉链法解决冲突的时候，不是要遍历对应的链表？

$\color{red}{\text{Q}}$：什么是同义词

散列表的基本概念

在前面介绍的线性表和树表的查找中，记录在表中的位置与记录的关键字之间不存在确定关系，因此，在这些表中查找记录时需进行一系列的关键字比较。这类查找方法建立在“比较”的基础上，查找的效率取决于比较的次数。

$\color{green}{\text{散列函数}}$:一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr(这里的地址可以是数组下标、索引或内存地址等)。

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为$\color{green}{\text{同义词}}$。一方面，设计得好的散列函数应尽量减少这样的冲突;另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。

$\color{green}{\text{散列表}}$:根据关键字而直接进行访问的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。

理想情况下，对散列表进行查找的时间复杂度为O(1)，即与表中元素的个数无关。

下面分别介绍常用的散列函数和处理冲突的方法。

散列函数的构造方法

在构造散列函数时，必须注意以下几点:

1）散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。

2）散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生。

3）散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址。下面介绍常用的散列函数。

下面介绍常用的散列函数。

直接定址法

直接取关键字的某个线性函数值为散列地址，散列函数为

$H(key) = key \text{或}H(key)= a \times key + b$

式中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

除留余数法

这是一种最简单、最常用的方法，假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用以下公式把关键字转换成散列地址。散列函数为

$H(key) = key \quad \\% \quad p$

除留余数法的关键是选好p，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性。

注意，6 % 5 = 1

数字分析法

设关键字是r进制数（如十进制数)，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等;而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

分析：比如电话号码，使用后面几位而不使用前面几位来做key

平方取中法

顾名思义，这种方法取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

在不同的情况下，不同的散列函数具有不同的性能，因此不能笼统地说哪种散列函数最好。在实际选择中，采用何种构造散列函数的方法取决于关键字集合的情况，但目标是尽量降低产生冲突的可能性。

处理冲突的方法

应该注意到，任何设计出来的散列函数都不可能绝对地避免冲突。为此，必须考虑在发生冲突时应该如何处理，即为产生冲突的关键字寻找下一个“空”的Hash地址。用$H_i$表示处理冲突中第i次探测得到的散列地址，假设得到的另一个散列地址$H_1$仍然发生冲突，只得继续求下一个地址$H_2$，以此类推，直到$H_k$不发生冲突为止，则$H_k$为关键字在表中的地址。

开放定址法

所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为

$H_i= (H(key) + d_i) \% m$

取定某一增量序列后，对应的处理方法就是确定的。通常有以下4种取法:

1）$\color{green}{\text{线性探测法}}$。当$d_i$=0,1,2,…, m -1时，称为线性探测法。这种方法的特点是:冲突发生时,顺序查看表中下一个单元(探测到表尾地址m-1时，下一个探测地址是表首地址0)，直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。

线性探测法可能使第i个散列地址的同义词存入第i+1个散列地址，这样本应存入第i+1个散列地址的元素就争夺第i+2个散列地址的元素的地址……从而造成大量元素在相邻的散列地址上$\color{red}{\text{“聚集”(或堆积)起来}}$，大大降低了查找效率。

堆积现象示意

意思是从冲突位一个一个往后面找

2)平方探测法。当$d_i=0^2,1^2,-1^2,2^2,-2^2,\cdots,k^2,-k^2$时，称为平方探测法，其中$k \leq m/2$散列表长度m必须是一个可以表示成4k＋3的素数，又称$\color{green}{\text{二次探测法}}$。

平方探测法是一种处理冲突的较好方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。

3)再散列法。当$d_i=Hash_2(key)$时，称为再散列法，又称双散列法。需要使用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时,则利用第.二个散列函数$Hash_2(key)$计算该关键字的地址增量。它的具体散列函数形式如下:

$H_i= (H(key)+ ixHash_2(key)) \% m$

初始探测位置$H_0$= H(key)% m。i是冲突的次数，初始为0。在再散列法中，最多经过m-1次探测就会遍历表中所有位置，回到$H_0$位置。

跳着来选key的，所以不容易出现堆积。

4）伪随机序列法。当$d_i=$伪随机数序列时，称为伪随机序列法。

注意:在开放定址的情形下，不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址。因此，要删除一个元素时，可给它做一个删除标记,进行逻辑删除。但这样做的副作用是:执行多次删除后，表面上看起来散列表很满，实际上有许多位置未利用，因此需要定期维护散列表，要把删除标记的元素物理删除。

拉链法(链接法，chaining)

显然,对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。假设散列地址为i的同义词链表的头指针存放在散列表的第i个单元中，因而查找、插入和删除操作主要在同义词链中进行。拉链法适用于经常进行插入和删除的情况。

例如，关键字序列为{19,14,23,01,68,20,84,27,55,11,10,79}，散列函数H ( key) =key%13，用拉链法处理冲突，建立的表如图7.9所示

例子：redis的dict的实现
查找成功时对空指针的比较一般不算做一次比较

散列查找及性能分析

散列表的查找过程与构造散列表的过程基本一致。对于一个给定的关键字key，根据散列函数可以计算出其散列地址,执行步骤如下:
初始化: Addr=Hash (key) ;

①检测查找表中地址为Addr的位置上是否有记录，若无记录，返回查找失败;若有记录，比较它与key的值，若相等，则返回查找成功标志，否则执行步骤②。用给定的处理冲突方法计算“下一个散列地址”，并把 Addr置为此地址，转入步骤

①。例如，关键字序列{19,14,23,01,68,20,84,27,55,11,10,79}按散列函数H(key)=key%13和线性探测处理冲突构造所得的散列表工如图7.10所示。

给定值84的查找过程为:首先求得散列地址H(84)=6，因$L [ 6]$不空且$L[6]$≠84，则找第一次冲突处理后的地址$H_1$=(6+1)%16=7，而$L[7]$不空且$L[7]$≠84，则找第二次冲突处理后的地址H2=(6+2)%16=8，L[ 8]不空且L[ 8]=84，查找成功，返回记录在表中的序号
给定值38的查找过程为:先求散列地址H(38)=12，$L [12]$不空且$L[12]\neq$ 38，则找下一地址H=(12+1)%16=13，由于$L[13]$是空记录，故表中不存在关键字为38的记录

查找各关键字的比较次数如图7.11所示。

平均查找长度ASL为:ASL= (1×6+2+3×3+4+9)/12= 2.5

对同一组关键字，设定相同的散列函数，则不同的处理冲突的方法得到的散列表不同，它们的平均查找长度也不同，本例与上节采用拉链法的平均查找长度不同。
从散列表的查找过程可见:

(1）虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需要以平均查找长度作为衡量散列表的查找效率的度量。

(2）散列表的查找效率取决于三个因素:散列函数、处理冲突的方法和装填因子装填因子。散列表的装填因子一般记为c，定义为一个表的装满程度，即

$α = \dfrac{表中记录数n}{散列表长度m}$

散列表的平均查找长度依赖于散列表的装填因子a，而不直接依赖于n或m。直观地看，α越大，表示装填的记录越“满”，发生冲突的可能性越大，反之发生冲突的可能性越小。

读者应能在给出散列表的长度、元素个数及散列函数和解决冲突的方法后，在求出散列表的基础上计算出查找成功时的平均查找长度和查找不成功的平均查找长度。