先讨论查找成功时的 ASL：如果要查找 56，需要对比一次关键字，查找长度为 1，查找概率为 1/8（一共八个元素，概率均等）；如果要查找 13，需要对比两次关键字，查找长度为 2，查找概率同为 1/8；以此类推。那么推广到一般情况，查找第 i 个元素需要对比 i 次关键字，一共有 n 个元素。所以 ASL = (1+2+3+...+n)/n = (n+1)/2。

然后是查找失败时的 ASL：对于任何一个不存在于数组中的元素，显然都是查找失败的，假设要查找 m 个关键字，全都失败了。每次查找都需要对比 n 次（每个都对比一次），那么总共就是 m*n 次，每个关键字被查找的概率都是 1/m，所以 ASL = n*m/m = n。

显然，顺序查找的时间复杂度为 O(n)。

1.2 改进的无序查找——哨兵

事实上，我们在调用查找函数的时候是有返回值的，对于前一种方法，判断查找成功与否的条件是函数返回值是否为 -1（或其他值）。但是除了 0 以外，无论是正是负，其实逻辑上都为 true。在这种情况下，想写 if(search(key) 或 if(!search(key)) 就不现实了。而在待查找数组中增加哨兵则可以解决这个问题。

哨兵是什么？

哨兵其实是一个抽象出来的概念，其本质上也是一个数据元素，并且值和待查找关键字是相等的，同时位于数组的 0 号下标。

比如上图中，待查找关键字为 14，此时会将数组的 0 号位置修改为 14，这时候就给下标 0 这个位置取个名字叫“哨兵”。查找的过程是从后向前的（图中为 7 到 0）。显然 14 是存在的，所以查找会返回 14 的下标 3。

当待查找数据本身不在数组中时，如上图中查找的 5。最终判断条件会在访问到下标为 0 时终止，也就是下标为 0 时，数组元素（哨兵）和待查找关键字相等，返回值为 0。

存在哨兵的目的就是不让你访问它的，它就像个看门的。当你找到它的时候，说明前面没有符合条件的元素，也就是查找失败了。

查找成功时的 ASL：从后往前看，如果查找第 n 个元素，需要对比 1 次；如果查找第 n-1 个元素，需要对比 2 次；以此类推；如果查找第 1 个元素，需要对比 n 次。每个元素被查找的概率都是 1/n。所以结果还是 (n+1)/2。

查找失败时的 ASL：和没有哨兵的顺序查找相比，显然每次查找失败都需要多和哨兵对比一次。所以 ASL = n+1。

显然，哨兵查找的时间复杂度依然为 O(n)。

1.3 有序的顺序查找

对于一个有序的数组来说，查找成功时的情况显然和前面是一样的。

而查找失败时会有所改变，比如要查 30 这个关键字，查到下标为 3 时，27<30，继续；查到下标为 4 时，43>30。此时显然知道 30 不在表中，那么 30 的查找路径就为 5，而非挨个对比一次的 8。

针对有序表的顺序查找，有种特殊的 ASL 分析方法，即查找判定树。

简化一下……8个元素的树太高了……

上面那个 4 元素的数组所构造的查找判定树长这样，比如要查找 14，先对比 2，14>2，往右走，14>13，往右走，14==14，终止。而如果要查 8，先对比 2，8>2，往右走，8<13，往左走，查找失败。

所以不难看出，查找成功时，查找路径长度就是关键字所在层数，并且有多少个元素就会有多少层。所以 ASL = (1+2+...+n)/n = (n+1)/2。

查找失败时，查找路径长度为其查找失败结点父结点所在层数，比如上面查的 8，路径长度就是 13 所在层数 2。所以也比较好算，对上图来说，假如 2 和 13 之间要查找 m 个关键字，每个关键字都会查找失败并且落在 13 的左孩子结点上，即查找路径长度为 2，对于这部分的 ASL = m*2/m = 2。同理，第二个和第三个结点之间的 ASL = 3，第三个和第四个结点之间的 ASL=4，以此类推，最后第 n 个结点后面，还会有两个长度为 n 的路径（上图中即 27 的左右孩子）。所以 ASL = (1+2+...+n+n)/n+1 = n/2 + (n+1)/2。（n+1怎么来的，因为分子上有 n+1 个数，对应了 n+1 种查找情况）。

显然，时间复杂度还是 O(n)。

二、折半查找/二分查找

对于上面这个表来说，显然是有更优的查找办法的。

比如要查 14，可以用 35 当作中间值，35 左边的都小于它，35 右边的都大于它。那么 14<35 显然应该在左边查。接着再找中间值，比如 13，14>13 显然在 13 右边、35 左边。再用 14 作为中间值，就是我们要找的元素了。

这便是折半查找的思路，每次都把查找区间分成一半，故也叫二分查找。

实现思路是这样的：

首先有个 int low = 0，标记第一个元素的位置；还有个 int high = n-1，标记最后一个元素的位置。

然后就是关键的 int mid = (low+high)/2，如果 low+high 为奇数，自动向下取整，不影响。

假设数组叫 arr，第一步即对比 arr[mid] 和关键字 key 的大小。

如果 key > arr[mid]，应该在右边找，low = mid+1, high--，重新让 mid = (low+high)/2。
如果 key < arr[mid]，应该在左边找，low++，high = mid-1，重新让 mid = (low+high)/2。
如果 key == arr[mid]，万事大吉，退出循环返回 mid。

假如关键字不在表中，最后一次对比 low==high==mid，紧接着下一次，无论是 low++ 还是 high--，都会造成 low>high，这便是循环终止条件。

对于折半查找的查找判定树构造方式很简单，但是软件画图太难了……

第一次有 n 个元素，通过 mid 分为了左半部分和右半部分，此时让 mid 所指元素为根结点，左子树为其左边元素，右子树为其右边元素。同理，递归调用上述过程，直到不能再构造了为止。

省略一些步骤：

图中紫色为查找失败结点。

不难发现，对于 n 个结点的判定树来说，查找失败结点有 n+1 个（树的空链域数量）。

但是抽象的 ASL 我不会算，只会算具体的。

比如上图中，查找成功结点，第一层有一个，第二层两个，第三层四个，第四层两个。查找成功 ASL = (1*1 + 2*2 + 4*3 + 2*4)/9。

查找失败结点第四层有六个，第六层有四个，~~查找失败 ASL = (6*4 + 4*6)/10。~~

@20221102查找失败ASL应该算失败结点父结点的层数，因为查找失败结点不涉及关键字比较，故查找失败 ASL = (6*3 + 4*4)/10。

形象上很好理解，每次找到都会把查找区间折半，对于 n 个元素的有序表来说，能够折半 log2(n) 次（log以2为底对n取对数）。

另外给一个思路，查找成功时的 ASL 和树高有关，而树高 h = ⌈log2(n+1)⌉。计算方法同二叉树的最小高度。所以 ASL 是和这个值相关的。

故时间复杂度为 O(log2(n))。

三、分块查找

直接上例子吧。

上面那个黄色的叫索引表，下面的就是顺序表。

简述一下特征就能理解分块查找是什么了：

首先对于索引表，每个结点由三部分构成，①其所指分块中最大的数据元素②其所指分块的下界③其所指分块的上界。比如上例中，黄色的 10 这个结点中，10 是分块中的最大元素，另外还包含下界 0 和上界 1，用来指示所指分块的区间。

对于顺序表，块内是无序的，块间是有序的（第一块都小于第二块，以此类推）。

而分块查找，就是从索引表中确定要查关键字所在的分块，再到相应的分块中去查。

比如要查 60 这个元素，首先索引表中就有，可以直接到其所指分块 5-8 去查，分块中的查找就是最基础的顺序查找，挨个对比，到 7 为止查到 60，则返回。

如果要查 26 这个元素，它大于 25 小于 60，所以应该在 60 所指的分块中，结果是 9。

对于索引表来说，每个元素都是有序的，所以对于索引表的查找可以按照折半查找进行。

对于分块查找的 ASL 计算，比较复杂，但是有特例比较好计算，这里就不贴图了，文字描述一下：索引表有 b 个结点，即整个顺序表被分为了 b 块，其中每个块都有 s 个数据元素，即一共有 b*s 个数据元素。

要计算分块矩阵的 ASL，可以分别计算查找索引表的平均查找长度 LI 和块内查找的平均查找长度 LS。

首先，因为块内是无序的，所以必须要用顺序查找，即 LS = (s+1)/2。

其次，对于索引表，有顺序查找和折半查找两种方式。

若为折半查找，LI = ⌈log2(b+1)⌉，ASL = LI+LS = ⌈log2(b+1)⌉ + (s+1)/2。

若为顺序查找，LI = (b+1)/2，ASL = LI+LS = (b+1)/2 + (s+1)/2 = (s^2+2s+n)/2s。求导可以得出，ASL 最小值为 sqrt(n)+1，s=sqrt(n) 时 ASL 取最小值。（sqrt为开根号）

四、二叉搜索树

二叉搜索树（BST，Binary Search Tree），其实就是二叉排序树，其定义在树那篇中有说明：

③ 二叉排序树

对于一棵二叉排序树来说，每个结点的左子树均小于（或大于）根结点，右子树均大于（或小于）根结点，并且递归来看，左子树的左子树和右子树、右子树的左子树和右子树都要满足这个条件。

图自王道课件

下面介绍对于 BST 的基本操作：

①查找

具体来说，查找有两种实现方式。

其一为循环遍历查找，利用左子树根结点、根结点、右子树根结点依次递增的原理进行实现：最外层套一个 while 循环，当当前结点 p 不为空且 p->data != key 时循环。循环内部，若 key < p.data，则向左子树寻找，即 p = p->lChild；若 key > p.data，则向右子树寻找，即 p = p->rChild。退出循环的条件要么是 p == NULL，代表查找失败；要么是查找成功，p 指向查找到的结点。所以循环外面 return p 即可。

其二为递归遍历查找，利用树递归定义的特性进行实现：首先，递归退出条件有两个，要么查找成功，即 key == p.data，此时 return p；要么查找失败，即 p == NULL，此时 return NULL。而在递归进行过程中，如果 key < p.data，则递归调用查找函数寻找左子树；如果 key > p.data，则递归调用查找右子树。

两个方式实现起来都很简单，贴个王道课件。

图自王道课件

对于递归遍历查找来说，空间复杂度来自递归调用栈，若树只朝着一边长（看起来像个链表），那么查到最后一个结点就需要 n 层递归，所以最坏空间复杂度为 O(n)。而循环遍历查找只需要两个实参即可，空间复杂度为 O(1)。二者时间复杂度是相同的。

②插入

BST 的插入非常简单，新插入的结点一定是叶子结点，所以相当于先查找待插入结点的关键字，在最后 p == NULL 的位置插入即可。需要注意，若新插入结点值已存在于树中，应当认为插入失败。

③删除

BST 的删除有三种情况。

第一种，待删除结点是叶子结点，其没有子树。此时应当直接删除，并不影响 BST 特性。

第二种，待删除结点是分支结点，其只有一棵子树。假如待删除结点是 B，其父结点为 A，其左孩子为 BL（没有右孩子），那么一定满足 BL<B<A；如果其右孩子为 BR（没有左孩子），那么一定满足 B<BR<A。所以两种情况都可以将 B 的子树直接连到 A 上。

第三种，待删除结点是分支结点，并且有两棵子树。这种相对相对来说麻烦点，通过第二种情况的分析，大概可以明白删除的规律：就是用 B 左子树中最大的或者右子树中最小的结点来代替 B。假如 B 左子树中最大的结点为 C，那么会有 BL<C<B<BR<A，用 C 代替 B 后，BL<C<BR<A，是满足 BST 特性的；同理，假如 B 右子树中最小的结点为 C，那么会有 BL<B<C<BR<A，用 C 代替 B 后，BL<C<BR<A，同样满足 BST 特性。而“左子树中最大的结点”和“右子树中最小的结点”其实就是对 B 这棵树做中序遍历后得到的 B 的直接前驱后后继。所以结论是，用 B 的直接前驱或后继 C 替代 A 的位置，然后对 C 进行删除，最后会转化成前两种情况。

关于找中序前驱和后继的方法，同样在树那篇中详细提到过：

找后继

对于右子树的中序遍历，同样是按照左子树 -> 根结点 -> 右子树的顺序进行的，所以第一个遍历的结点一定在右子树的左边。此时分为两种情况，当右子树的左子树为空，右子树的根结点本身就是第一个遍历的；当右子树的左子树不为空，则第一个遍历的在右子树的最左下角。

找前驱

对于左子树的中序遍历，同样是按照左子树 -> 根结点 -> 右子树的顺序进行的，所以最后一个遍历的结点一定在左子树的右边。此时分为两种情况，当左子树的右子树为空，左子树的根结点本身就是最后一个遍历的；当左子树的右子树不为空，则最后一个遍历的结点在左子树的右下角。

《数据结构（C语言版）》学习笔记6 树_学生罢了的博客-CSDN博客数据结构中树的介绍，包含普通的树、二叉树、森林的存储方式以及相互之间的转换，另含树和森林的遍历，二叉树的线索化，哈夫曼树等https://blog.csdn.net/vv0610_/article/details/126799910

ASL 的计算方法和前面的查找判定树是一样的，第 i 层有 Ni 个结点，然后用 i*Ni 就是第 i 层的所有结点的查找路径长度，所有层都加在一块，最后乘以每个结点被查找的概率 1/n 即可。

这里如果 BST 是尽可能平衡（横着长）的，那么 ASL 是 log2(n) 的数量级，最坏时间复杂度就为 O(log2(n)) ；但如果 BST 是往深了长的，瘦高瘦高的，那么 ASL 是 n 的数量级，最坏时间复杂度就为 O(n)。

图自王道课件

五、平衡二叉搜索树

承前所述，在 BST 中无法保证树是平衡的，所以最坏时间复杂度可能为 O(n) 量级。想要改进这一点，就需要在每次删除和删除的时候让树尽可能保持平衡，使得最坏时间复杂度控制在 O(log2(n)) 量级。平衡二叉树（AVL，以人名命名）就应运而生了。

所以在 AVL 中，查找和 BST 无异，就不再细说，重点是如何让树保持平衡，这里着重说明插入导致不平衡的情况，删除的分析和插入相同，故不赘述。

这里所说的平衡二叉树，其实全名是平衡搜索二叉树，而非普通的平衡二叉树。故应当是在 BST 的基础上，任一结点左右子树深度之差不超过 1。

引入平衡因子的概念，平衡因子 b(alance) = 左子树高度 - 右子树高度。在 AVL 中，b 的取值为 -1、0、1。当插入某个结点导致不平衡后，不平衡结点的 b 值为 -2 或 2。

插入某个结点后，如果 AVL 仍平衡，则不需要做任何处理；若不平衡，则需要顺着插入结点向上寻找到最小不平衡子树的根结点 A（事实上，若不平衡，只需要处理最小不平衡子树，而不需要处理整棵树。原因也比较简单，因为不平衡的最小单位就是最小不平衡子树，其左右子树高度差为 2，如果不平衡性向上传导了，也是因为最小不平衡子树的高度和其兄弟树差为 2。所以将最小不平衡子树调整平衡后，其和兄弟树高度差恢复为平衡情况）。

对于最小不平衡子树 A 的调整，又会具体分为四种情况：

①LL，即在 A 的左孩子的左子树中插入导致的不平衡。

如上图所示，A 为最小不平衡子树的根结点，BL 为 B 的左子树（不一定是单独的结点，可能是一棵树，故插入位置可能为 BL 的任何一个位置，但 B 是平衡的）。

先解释一下为何要假设 AL BR AR 高度都为 A。首先基于的前提是，在左图中，以 A 为根结点的树不平衡的；同时，在 BL 中插入结点后的右图中，以 A 为根结点的树是最小不平衡子树。

那么如果 BL=H+1，BR=H，AR=H，显然 A 的平衡因子为 2，已经不平衡了。

如果 BL=H+1，BR=H，AR=H+1，此时 B 的平衡因子为 1，A 的平衡因子也为 1，但是对 BL 进行插入操作会导致 B 成为最小不平衡子树。

如果 BL=H，BR=H+1，AR=H+1，插入前平衡，插入后也平衡。

其他情况同理。

故只能按照上图假设。

对最小不平衡子树的调整是基于 AVL 特性的：首先，AVL 也是有序树，必然满足 BL<B<BR<A<AR，调整后应当也满足这个条件；其次，AVL 平衡的条件是任一结点左右子树之差不超过 1。

要满足上两个条件，做法是将 B 向右上旋转，代替 A 的位置，同时 BR 成为 A 的左子树，A 连带其右子树成为 B 的右子树：

为何要这样调整？本质上我们希望平衡因子减少，也就是让两个高度相差最小的单位并列成为一个结点的左右子树。其中 BL 高度为 H+1，A+AR 高度为 H+1，BR 高度为 H，AR 高度为 H。显然最优的情况就是将 BL 和 A 放在同一层，将 BR 和 AR 放在同一层。但还需要满足大小顺序，故解为上图。

结论：A 的左子树 B 右上旋转代替 A，A 右下旋成为 B 的右子树，B 的原右子树成为 A 左子树。

②RR，即在 A 的右孩子的右子树中插入导致的不平衡。

分析情况类似，A+AL 高度为 H+1，BR 高度为 H+1，所以 A 和 BR 在同一层；AL 高度为 H，BL 高度为 H，所以 AL 和 BL 在同一层；同时还需满足大小顺序。

结论：A 的右子树 B 左上旋代替 A，A 左下旋成为 B 的左子树，B 的原左子树成为 A 右子树。

③LR，即在 A 的左孩子的右子树中插入导致的不平衡。

后面两种情况相对来说要复杂些。如果仍用 B 当作根结点，BR = H+1，A+AR = H+1，按照上面的分析，BR 和 A 在同一层，BL = H，AR = H，BL 和 AR 在同一层，但是又要满足 BL<B<BR<A<AR，显然，BR 和 A 在同一层时，没有根结点连接他俩使得 BR<根<A。而大于 BR 小于 A 的结点，就藏在 BR 里面。所以需要展开 BR，如上图所示。

图示是在 CR 插，同样可以在 CL 插，都满足 LR 的情况，并且分析类似，结果相同。

还按照前面相同的分析方法的话，BL 高度为 H，CR 高度为 H，AR 高度为 H，所以他们三个应该在同一层，同时注意到 CL 高度为 H-1，按理说应该在 BL CR AR 的下一层，但是没有根结点可以用了，所以只能把 CL 放在 BL CR AR 同一层。图中要满足的关系为 BL<B<CL<C<CR<A<AR，所以上述四个结点从左到右依次为 BL、CL、CR、AR，BL 和 CL 中间夹着 B，CR 和 AR 中间夹着 A，B 和 A 中间夹着 C。所以调整结果如图：

另外如果在 CL 插，结果如下，不难发现调整方式是相同的：

结论：A 的左孩子 B 的右子树 C 左上旋代替 B，C 再右上旋代替 A，C 的原左子树成为 A 的左子树。

④RL，即在 A 的右孩子的左子树中插入导致的不平衡。

以 CL 插入为例。

分析方法和 LR 是一样的，这里同样也可以在 CR 插。

结论：A 的右孩子 B 的左子树 C 右上旋代替 B，C 再左上旋代替 A，C 的原右子树成为 A 的右子树。

说完了插入，对于某个结点的删除，也分为失衡与否两种情况，而因为删除导致的不平衡，其实也是按照上面四种调整方式进行的，但是 L 和 R 的指代会有不同。

首先，删除还是直接删，参照 BST 的删除操作即可。

删除后，需要判断 AVL 是否因为删除操作失去平衡，并且从删除结点向上找到最小不平衡子树的根结点，至此都和插入操作类似。

但是，删除操作的 L 和 R 并非指代删除结点的位置，具体如下：

以最小不平衡子树的根结点为根，找它的最高儿子和最高孙子，最高儿子是指，以其孩子结点为根结点的子树中最高的那棵；最高孙子是指，以其孙子结点为根结点的子树中最高的那棵。显然，最高儿子在最高孙子上层，那么：

LL 就指最高儿子是根结点的左孩子，最高孙子是最高儿子的左孩子；（最高孙子是左孩子的左孩子）
RR 就指最高儿子是根结点的右孩子，最高孙子是最高儿子的右孩子；（最高孙子是右孩子的右孩子）
LR 就指最高儿子是根结点的左孩子，最高孙子是最高儿子的右孩子；（最高孙子是左孩子的右孩子）
RL 就指最高儿子是根结点的右孩子，最高孙子是最高儿子的左孩子。（最高孙子是右孩子的左孩子）

然后按照插入结点时介绍的 LL/RR/LR/RL 四种调整方法，对删除操作的最小不平衡子树进行调整。

在这之后，需要注意不平衡性是否向上传导，如果传导了，那么需要对新的最小不平衡子树进行调整，直至处理完根结点。

下例摘自王道课件：

此例中，要删除 32 这个结点，因为是叶子结点，所以可以直接删除，并不影响 BST 特性。删除后，17 的平衡因子为 0，44 的平衡因子为 -2，失去平衡。且 44 就是最小不平衡子树根结点，如下图：

44 的左子树高为 1，右子树高为 3，所以以右孩子为根结点的树是 44 的最高儿子。

78 的左子树高为 2，右子树高为 1，所以以左孩子为根结点的树是 44 的最高孙子。

最高孙子在 RL，对 RL 的调整是先右上旋，再左上旋（参考前文），结果如下图：

调整完之后，虽然这棵最小不平衡子树恢复平衡了，但是不平衡性向上传导。可以注意到，33 的左子树高度为 5（33-10-20-25-23-21），右子树高度为 3，33 的平衡因子为 2。因此，接着对以 33 为根结点的最小不平衡子树进行处理：

类似的，33 最高儿子为左孩子，最高孙子为左孩子的右孩子，符合 LR。对于 LR 的处理是，先左旋再右旋（参照前文），处理结果如下：

至此，所有结点都平衡了。

六、B树

在上文中，先介绍了 BST，随后是对 BST 进行查找效率的优化变成了 AVL，而B树，则是在 AVL 的基础上进一步修改。

如果简单来说，AVL 是一棵平衡二叉查找树，那么B树就是一棵平衡m叉查找树。

上图中是对B树的精确定义，也可以叫特性，满足以上特性的便是B树。B树除了分叉不同外，最大的不同就是对于平衡的要求，AVL中，任一结点左右子树高度之差不大于1则认为平衡，而B树中，任一结点左右子树高度都相同才算平衡，这就造就了从任一结点出发到叶子结点路径长度都相同（体现在上图的第四条，所有叶结点都在同一层）。

如图就是一个 B 树，在B树中，查找失败结点叫叶子结点，也就是最下面那层紫色的；而倒数第二层叫做终端结点。不难发现，B树是满足 BST 和 AVL 要求的，并且比他们要求更多。

B树的阶数可以简单地理解成分叉的上限，m阶B树即m叉B树。B树中每个结点构成，最多可以有 m 个分叉（即 m 个指向孩子的指针）和 m-1 个关键字。

如上图是一个 5阶B树（通过最右下角可以看出），根结点为 22，5 和 11 构成的是 22 的左孩子，其中有两个关键字和三个指针；1 3、6 8 9、13 15、30 35、40 42、47 48 50 56 都是终端结点，注意，不是一个关键字一个结点，而是一个结点中有多个关键字，如上图中 47 48 50 56 四个关键字构成了一个结点，其有五个指针都指向叶子结点。

除此之外我们注意到，每个结点内的各个关键字是有序的。

至此，B树的结构应该介绍清楚了。其实查找也很简单，和 BST、AVL 无异。

比如想查 15，15<22，往左边子树走；15>5，继续比较下一个关键字，15>11，继续比较下一个关键字，但是没有，所以往 11 的右边子树走；15>13，继续比较下一个关键字，15==15，查找成功。

再比如想查 51，51>22，继续比较下一个关键字，但是没有，所以往 22 的右边子树走；51>36，继续比较下一个关键字，51>45，继续比较下一个关键字，但是没有，所以往 45 的右边子树走；51>47，继续比较下一个关键字，51>48，继续比较下一个关键字，51>50，继续比较下一个关键字，51<56，所以往 56 的左边子树走；此时走到 NULL，查找失败。

下面再介绍一些B树的特性。

规定根结点和其他结点的分叉数，是为了保证查找效率的，使得B树尽量宽而不高。而根结点分叉个数最小为2，是因为B树最少有一个元素，此时最少只有两个分叉。

下面着重算一下有 n 个关键字的 m 阶B树的最小和最大高度。

首先讨论最小高度：

最小高度，则要求每个结点的分叉尽可能多。第一层根结点最多有 m 个分叉，则有 m-1 个关键字；第二层会有 m 个结点，每个结点都包含 m-1 个关键字……

假设有 h 层，那么第一层有 (m-1)*1 个关键字，第二层有 (m-1)*m 个关键字，第三层有 (m-1)*m^2 个关键字……第h层有 (m-1)*m^(h-1) 个关键字。结论为：

解得：

对不等式右边向上取整则为最小高度的整数值。

最大高度：

要求每个结点分叉尽可能少，但还需符合B树要求，而B树要求的最少分叉：根结点 2，其他结点 ⌈m/2⌉。第一层根结点最少有 2 个分叉，1 个关键字；第二层有 2 个结点，每个结点有 ⌈m/2⌉ 个分叉，⌈m/2⌉-1 个关键字……

假设有 h 层，那么第一层有 1 个关键字，第二层有 2*(⌈m/2⌉-1) 个关键字，

第三层有 2*(⌈m/2⌉-1)*⌈m/2⌉ 个关键字……第h层有 2*(⌈m/2⌉-1)*⌈m/2⌉^(h-2) 个关键字。结论为：

解得：

对不等式右边向下取整则为最大高度的整数值。

接下来就是插入和删除操作了。

插入的时候，都是在终端结点插入的，因为新元素插入后必定会新增查找失败结点，并且查找失败结点是新元素的左右孩子，如果不在终端结点插入，就无法保证叶结点都在同一层了。

除此之外无非就两种情况，因为每个结点是有关键字个数上限的，所以没超过上限的时候，直接插入即可；超出了上限，则需要特殊处理。用一个5阶B树的例子来说明（改编自王道课件）：

5阶B树中，根结点分叉数为2~5，其他非叶结点的分叉数为3~5，关键字个数比分叉少 1 个。

首先插 25：

连着叶子结点是为了方便看出新结点是在终端结点的位置插入的，此时根结点就是终端结点。

插 38，因为现在只有一个结点，所以 38 也插入这个结点，38>25，所以在 25 的右边。

插 49，仍然插入这个结点中，49>38，在 38 右边。

插 60，同上。

插 80。注意，此时这个结点已经有 4 个关键字 5 个分支了，达到了一个结点所能容纳的上限。此时要进行调整，先假装把 80 并进这个结点，然后把第 ⌈m/2⌉ 个元素拎出来当爹，5阶B数中 ⌈m/2⌉ = 3，即图中的 49。逻辑上看，就是把 49 单独拎出来作为父结点，左边的元素构成左子树的根结点，右边的元素构成右子树的根结点。（注意，如果插的是一个小于 49 的元素，那么 ⌈m/2⌉ =3 就不是 49 了，这也是为什么需要“假装并入”）

左图是假装并入，80 这个元素实际上是没插进去的，而右边是真正插入后的情况。

插 90。找终端结点，此时除了 49 所在结点其余的都是终端结点。而查找 90，最后一次查找判定落在 80 右侧，则插入这个位置。

下面举个错误的例子来理解为什么要插入在终端结点，如果 90 插在 49 右边，会变成这样：

从各种意义上来说这都是不合法的，比如根结点第二棵子树高为1，第三棵子树高为0，不平衡；或者说叶子结点不在同一层。因此必须要在终端结点插入。

插99。同样，查找最后一次判定会落在 90 右边，插入这个位置。

插 88。最后一次查找判定落在 80 右边，90 左边。先逻辑上并进去：

此时 ⌈m/2⌉ = 3，指向 88 所在位置，这也是为什么要先插入再调整了。

然后把 88 拿出来当左右孩子的爹。注意，左孩子已经有爹了，所以俩爹并作一个爹。也即把 88 拿到所在结点的父结点中。

现在，依次插入 83 和 87，结果如下图：

再插 70，位置在 60 右边 80 左边，插入后：

此时要把第三个元素也就是 80 放到父结点中，但还需保证父结点中的递增次序，所以 80 拿上去之后，应该在 49 右边和 88 左边：

再依次插 92 93 94，都在 90 和 99 之间：

调整第三个元素即 93：

再依次插入 73 74 75，都在 70 的右边：

调整第三个元素即 73：

调整完之后，发现父结点也多了，接着调整父结点，也即，把父结点中的第三个元素 80 拿出来，成为 80 当前所在结点的父结点，并且左右孩子分别指向左右侧元素：

（上图比较丑，没有调整位置，是为了方便对比）

后面再怎么插，也逃不过这个逻辑了（见思维导图）。

再看删除。

把前面的例子调整一下，再多插几个元素，就变成了上图的样子。

删除的逻辑是，如果删除的元素在终端结点，那么直接删掉；如果不在终端结点，则用被删除元素的前驱或者后继替换它的位置。删除之后，看看每个结点中关键字的个数是否低于下限，如果有结点中关键字个数低于下限，且其相邻兄弟元素多（拿一个也不低于下限），则可以把其兄弟结点中的元素拿一个过来填充（如果找右兄弟借，处理方法为，用被删除元素的后继替代它，用后继的后继替代后继，再删除后继的后继；如果找左兄弟借，处理方法为，用被删除元素的前驱替换它，用前驱的前驱替换前驱，再删除前驱的前驱）；如果其兄弟结点也不多（拿一个低于下限），则把这个元素不多的兄弟、低于下限的结点、它俩的父结点合并成一个结点。请看例子（依然来自王道，谢谢王道）：

删 60，60 在终端结点可以直接删除，发现 60 删除之后，该结点中还剩三个元素，所以不用调整：

删 80，80 在非终端结点，则需要用其直接前驱或后继替换它，再删那个直接前驱或后继。这里用直接前驱来替换，80 的直接前驱为其左子树的最右下结点的最右下元素（和中序前驱类似），即为 77。

删 77，和 80 类似，这次用直接后继替代。77 的直接后继为其右子树的最左下结点的最左下元素（和中序后继类似），即为 82。

删 38，删除后，38 所在结点只剩下一个元素，低于5阶B树的关键字下限 2，先看看能不能找兄弟借一个，发现它的右兄弟有 3 个元素，借一个过来也还剩 2 个，可以借。但是不能把 70 直接拿到 38 右边，因为要保证 38 所在结点中所有元素值都比其父结点 49 要小。前面说的比较抽象，这里拿出来解释一下：如果找右兄弟借，处理方法为，用被删除元素的后继替代它，用后继的后继替代后继，再删除后继的后继。38 的后继为 49，后继的后继为 70，所以就是用 49 替代 38，用 70 替代 49，然后删除 70 原来的位置：

删 90，删除之后低于下限。右兄弟不够借了，左兄弟可以借，那么类似的：如果找左兄弟借，处理方法为，用被删除元素的前驱替换它，用前驱的前驱替换前驱，再删除前驱的前驱。90 的前驱为 88，前去的前驱为 87，所以用 88 替代 90，用 87 替代 88，然后删除 87 原来的位置：

删 49，删完之后，低于下限，但是其兄弟也也没法借了，为了方便描述，标几个颜色：

红色是被删除元素所在的结点，黄色是它的相邻兄弟结点，蓝色是这两个结点的“父结点”（之所以打引号，是因为 70 并非一个结点，而只是结点中的一个元素，但是 70 两侧的指针分别指向这两个结点，形象上的理解）。现在要做的是把这三个带颜色的结点合成一个结点，按照大小顺序，如下排列：

显然彩色结点中的元素都比 73 小。而调整完之后，发现 73 所在的结点元素个数又低于下限了，而且显然它唯一的兄弟也没法给它提供元素：

因此类似地，把三个带颜色的结点合并：

注意，少了一个结点，是要把空结点释放掉的。

至此，删除结束。

七、B+树

就考试来说，B+树内容并不多，主要是和B树对比出题。

首先，在理解上，B+树和分块查找的逻辑比较接近，回顾一下分块查找，其有一个索引表，索引表中的关键字是其所指分块中最大值，B+树也有这个特性，可以对照下例：

其次，B+树和B树对于结点分支数量的要求是一样的，即根结点至少有 2 个至多有 m 个分叉，非叶结点至少有 ⌈m/2⌉ 个至多有 m 个分叉（注，B+树的叶子结点不再是查找失败节点，而是上图中绿色的那一层，可以理解为对应B树的终端结点）。但是对于每个结点关键字的数量要求有所不同，B树的关键字数量是分支数-1，而B+树关键字的数量和分支数相同。

再者，在B树中，每个结点中的每个元素都对应一个查找成功情况，而B+树中，只有查找到叶子结点（最后一层）才会查找成功，非叶结点只充当路径，而不包含信息（图中的记录就是信息），而分支结点中的关键字一定全部包含在叶子结点中，这类似于分块查找。

最后，B树不支持顺序查找，而B+树的叶子结点会通过一个链表链接在一块，因此支持顺序查找。并且如刚才所说，B树中所有结点都可以被查找，而B+树只有叶子结点可以被查找。

八、散列查找（Hash）

前文介绍了顺序查找和排序树，接下来是一个全新的概念。

散列查找是基于散列表实现的，又叫哈希表（Hash Table）。其存储的数据元素的关键字与其存储地址直接相关，这就像数组中可以通过元素下标直接查找元素一样（随机存取）。理想的散列查找时间复杂度为O(1)，但是由于冲突的存在，往往要慢一些。

散列表中，关键字与其存储地址的映射关系是通过散列函数实现的，即 Addr = H(key)，每个 key 通过 H 映射到一个 Addr（地址）上，因此散列查找的实现和散列函数的设计是直接相关的。

在映射地址的时候，往往会产生冲突，即两个不同的关键字被映射到同一块地址上，此时这两个冲突的关键字就被称作“同义词”。

常见的散列函数有四种：

①除留余数法：

H(key) = key % p

p 代表 prime number，是不大于表长 n 的最大质数。比如表长为 8，p = 7；表长为 15，p = 13。

例如关键字为 1~20，表长为 10，p 取 9。通过上述散列函数，映射地址如下表（9号下标没画）：

会发现比如 1 10 19 这三个关键字都映射到了 1 这个地址上，这便是冲突，1 10 19 便是一组同义词，而冲突处理的方法，将在后面提到。

②直接定址法

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

这个比较好理解，比如 1~20 这 20 个数，用一个长度为 20 的表，关键字 1 就存在地址 1 的位置，关键字 2 就存在地址 2 的位置。或者关键字为 1-20 之间的偶数，就可以让 H(key) = key/2，映射到 1~10 这些位置。

③数字分析法

取关键字当中的某几位，这几位分布比较均匀（不怎么重复）

比如手机号中，前三位固定就那几种，中间四位虽然比前三位好点，但重复也比较多，比如0552是吧。而最后四位，相对来说就比较均匀，重复较少，如果不放心也可以多带一位，取后五位。

④平方取中法

就是把关键字平方，然后对平方后的数用数字分析法

这种方法适用于关键字中的每个位都不均匀，或者均匀了但是超出表长了。比如手机号后四位我觉得不均匀，取后五位，而我表长只有 10000，最多只能存 0-9999，取五位就是 0-99999 了。这时候可以考虑把关键字平方，然后看看有没有分布均匀的几位取出来即可。

接下来介绍矛盾分析法，矛盾具有同一性斗争性……跑题了。

冲突处理法：

①拉链法

顾名思义，哪里冲突就从哪里拉一条链表出来

比如这个例子中，每个位置都冲突了，用 1 号位举个例子，1 10 19 三个关键字冲突，则可以把 1 号位置变成链表的头结点或者头指针，指向 1->10->19 这样一个链表。当需要查找的时候，比如要查找关键字为 k，先通过散列函数映射到 Addr = H(k) 这样一个地址，然后去查这个地址中的链表，依次比较。

比如这样一个散列表：

下面分析平均查找长度：

查找成功的 ASL，对应 12 个查找成功的关键字，就是把每个关键字的查找长度都算出来，加在一块，然后除以关键字个数（默认查找概率相同）。比如上图中 14 的查找长度为 1，1 的查找长度为 2，27 的查找长度为 3，79 的查找长度为 4，68 的查找长度为 1……其实某个关键字的查找长度就等于其在链表中第几个结点，因为通过散列函数，任意一个关键字都可以直接定位到链表所在的地址，所以查找长度只和链表长度相关。

上图的成功 ASL = (1+2+3+4+1+2+1+2+1+1+2+1)/12

查找失败的 ASL，对应空位置和链表末端的位置。空位置不算做查找长度，比如表中地址 0、2、4、5 等这些没有存放关键字的位置。链表末端的位置，查找长度等于链表表长。而以上都算作查找失败的情况。上图中，没存关键字的位置有 7 个，链表有 6 个，所以总的失败情况有 13 个。

上图的失败 ASL = (0+4+0+2+0+0+2+1+0+0+2+1+0)/13

注，失败时的 ASL 也叫散列表的装填因子 α，定义为表中记录数/散列表长度，而记录数就等于表中所有链表的长度之和，散列表长度也对应着查找失败的情况数量。

②开放定址法

在拉链法中，多个元素可以对应同一个地址，但他们必须是同义词。但是在开放定址法中，地址开放，即使不是同义词，也可以存到某个位置中。可以通过后面的介绍进一步理解。

核心的散列函数 ADDRi = (H(key)+di)%m（m 为表长），ADDRi 和 di 分别对应第 i 次发生冲突时的地址和增量。

而几种不同的开放定址法，主要都是在 di 上做文章（注，i 是从 0 开始的，这也是为什么 di 的起始值都是 0）。

下面几种方法以除留余数法为例，H(key) = key % 13，表长 m=16。

Ⅰ线性探测法

di = 0, 1, 2, ..., m-1

直接举个极端点的例子，比如依次要存 { -12, 1, 14, 27}

存 -12，H = (-12)%13 = 1（注，这里顺便说一下负数取余，a%b = (a+kb)%b，a<0，k为整数，这里计算方法为 -12+13=1, 1%13=1）。显然表里没有任何元素，所以直接存位置 1。

存 1，H = 1%13 = 1。访问 1 号位置，发生第一次冲突，d1 = 1，ADDR1 = (H+d1)%m = 2；访问 2 号位置，没有冲突，所以存位置 2。

存 14，H = 14%13 = 1。访问 1 号位置，发生第一次冲突，ADDR1 = 2；访问 2 号位置，发生第二次冲突，d2 = 2，ADDR2 = (H+d2)%m = 3；访问 3 号位置，没有冲突，所以存位置 3。

存 27，H = 27%13 = 1。访问 1 号位置，发生第一次冲突，ADDR1 = 2；访问 2 号位置，发生第二次冲突，ADDR2 = 3；访问 3 号位置，发生第三次冲突，d3 = 3，ADDR3 = (H+d3)%m = 4；访问 4 号位置，没有冲突，所以存位置 4。

其实很容易发现，线性探测法就是在发生冲突时，依次向右探测，直到找到一个空位置就存（探测到 m-1 个位置之后会回到第 0 个位置，类似循环队列，原因在于取余）。

线性探测法获得的散列表如何查找呢？就按上个例子来说，如果要查询 1 位置，你不知道在这里冲突了多少次，所以需要顺着增量序列一直往后找，直到找到一个没存元素的位置为止。（如果没存元素，证明冲突在这之前就结束了）

此外需要注意的是，对于线性探测法获得的散列表的删除操作，不允许直接将表项置空。原因和查找是相关的，因为查找的结束条件是查到空元素，置空的话可能导致查找提前结束。因此，在设计散列表的时候，需要增加标志位以判断某一数据项是否被删除，如果是被删除导致的空元素，查找需要继续向后进行。

最后是例行 ASL：

成功的 ASL：计算每个关键字的查找长度之和，再除以关键字个数。某个关键字查找长度的算法，是先通过散列函数，映射到某一位置，然后从这一位置开始按照增量序列向后查找，关键字对比的次数就是这一关键字的查找长度。

失败的 ASL：本例中，散列函数的 p 为 13，因此计算出的映射地址范围为 0~12，一共会映射到13 个位置，所以查找失败的情况只会在这 13 种情况下发生。而每种情况的查找路径长度，需要从映射地址向后找到空元素的位置，并且需要把和空元素比较的那一次算进去。

太抽象了还是举个例子吧。如图已经是个存好的散列表了。

成功的 ASL：H(14) = 1，直接就能查到，查找长度为 1。H(1) = 1，ADDR0 = 1 没查到，ADDR1 = 2 查到，查找长度为 2。H(68) = 3，直接就能查到，查找长度为 1。H(27) = 1，ADDR0 = 1 没查到，ADDR1 = 2 没查到，ADDR2 = 3 没查到，ADDR3 = 4 查到，查找长度为 4。以此类推。

ASL = (1+2+1+4+3+1+1+3+9+1+1+3)/12=2.5，分子为查找长度，按照表中元素顺序排列。

失败的 ASL：按位置看，位置 0 查找失败长度为 1（空位置也计入比较），位置 1 查找失败长度为 13（从 1 查到 13），位置 2 查找失败长度为 12（从 2 查到 13），以此类推，位置 12 查找失败长度为 2（从 12 到 13）。通过散列函数映射的位置只有以上 13 种可能。

ASL = (1+13+12+11+10+9+8+7+6+5+4+3+2)/13=7，分子为查找长度，按照表中位置顺序排列。

散列查找的理想时间复杂度为O(1)，可以发现不管是查找成功的 2.5 还是查找失败的 7，都相差 1 较远，原因是冲突后的探测结果是存放在某个连续位置，造成了同义词的堆积，影响查找效率。

Ⅱ 平方探测法

di = 0, 1, -1, 4, -4, 9, -9,..., k^2, -k^2 (k为小于等于m/2的整数)

其实是 0, 1^2, -1^2, 2^2, -2^2, 3^2, -3^2, ...，k^2, -k^2

设计成平方，目的是为了使同义词相较线性探测法更不容易堆积。

需要注意的是，散列表长度 m 需要表示成 4k+3（k为整数）的质数，才能保证探测到所有位置。

Ⅲ 伪随机序列法

di = 伪随机序列，没有规律

③再散列法

即准备多个散列函数，第一个冲突就换成第二个散列函数，第二个冲突就换成第三个散列函数，以此类推。

==总结==

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/407304