7. 查找

线性表

[操作系统] 文件查找 联立

顺序查找

$$ASL=\frac{1+2+3+\dots +n}{n}=\frac{n+1}{2}\approx \frac{n}{2}$$

最简 判别代码

折半查找（二分）

ASL

折半查找 判定树 本质 就是 一个 二叉排序树

同样对于 平衡二叉树 来说 ，因为它也算是 二叉排序树

所以三个查找 的 ASL计算公式 是一样的

但是两者的 时间复杂度并不一样

因为二叉排序树 的输入 可能是 有序的，由于其排列特性，会导致它变相的成为单链表

二叉排序树 最坏时间复杂度：$O(n)$. 等于 细狗 二叉树的 树高

折半查找 最坏时间复杂度： $O({\log }_{2}n)$ 等于决策树 树高

分块查找（索引顺序）

利用 索引表 将 每个分块的最大关键字及其 地址 存取

概念

$S$ : 一个块中 的关键字 个数 一般 $S=\sqrt{n}$

已知 顺序查找 的平均查找长度为：

$$ASL=\frac{1+2+3+\dots +n}{n}=\frac{n+1}{2}\approx \frac{n}{2}$$

假设 分块查找 的 块数为 $s$ , 每块表中有 $b$ 个元素 $(n=sb)$

则分块查找的 平均查找长度：

$$ASL=L_I+L_S=\frac{s+1}{2}+\frac{b+1}{2}=\frac{s^2+2s+n}{2s}$$

根据公式 可以得到: 当 $s=\sqrt{n}$ 时，有最小 $ASL=\sqrt{n}+1$.

树形

二叉排序🌳

二叉查找树 （Binary Search Tree）

 二叉查找树具备以下特点：

 

• 左子树中所有节点的值 小于 根节点的值。

• 右子树中所有节点的值 大于 根节点的值。

• 这种「左小右大」的有序性，使得查找可以逐层缩小范围。

查询过程如下：

1. 从 根节点 开始。

2. 如果查询的值 等于 当前节点的值，返回 当前节点。

3. 如果查询的值 小于 当前节点的值，向 左子树 查询。

4. 如果查询的值 大于 当前节点的值，向 右子树 查询。

5. 如果到达 空节点，则查询失败，返回 NULL。

插入

重点中的重点

插入操作以查找为基础，所以优先使用 中序遍历 的思想找 插入位置

新插入的节点一定是叶子结点，并且是查找不成功时查找路径上访问的最后一个节点的左孩子或右孩子节点

删除

转换 模式

• 若删除的节点为叶子结点：

  1. 直接删除

• 若删除的节点不是叶子结点：

  1. 节点有左或右孩子：删除后左/右孩子上位；

  2. 节点有左、右孩子：查找删除节点右子树的最左下孩子（中序后继），让其与删除节点交换，转换为 删除节点为 叶子结点的情况

BST查找时间复杂度分析 

查找操作的时间复杂度，取决于树的 高度（Height）：

• 树的高度越小，查找路径越短，效率越高。

• 树的高度越大（越“瘦长”），查找路径越长，效率越低。

只有当树是基本平衡的时候 我们可以认为 其 时间复杂度为： $O({\log }_{2}n)$

二叉排序树 的创建

设有n个节点，则需要n次插入操作，而插入一个节点的算法时间复杂度为 $O(lo{g}_{2}n)$

        所以创建二叉排序树算法的时间复杂度为 $O(nlog_{2}n)$

标注

为什么创建过程是 $O(n{\log }_{2}n)$？

创建一棵二叉排序树的过程，本质上是执行了 $n$ 次插入操作：

• 第 1 个节点插入：耗时 $\approx {\log }_{2}1$

• 第 2 个节点插入：耗时 $\approx {\log }_{2}2$

• …

• 第 $n$ 个节点插入：耗时 $\approx {\log }_{2}n$

将这些步骤累加起来：

${\sum }_{i=1}^n{\log }_{2}i={\log }_2(n!)$

根据斯特林公式（Stirling’s approximation），${\log }_2(n!)$ 的数量级等同于 $O(n{\log }_{2}n)$

平衡二叉树（AVL)

定义

为了避免出现 普通 二叉查找树 出现 细狗 树，于是定义了一种 平衡的 二叉查找树

该树 树型均衡 ，左右子树高度之差的绝对值不超过 1， 且 左右 子树 也是 平衡二叉树

其必定是一颗 二叉排序树

概念

平衡因子： AVL中 节点的 左子树 和 右子树 的 深度 之差

最小不平衡子树：离插入节点最近且平衡因子 绝对值 超过 1 的**祖先节点**，以该节点为根的子树

平衡因子只可能 是 1 0 -1

只有一棵BST 所有节点 的平衡因子的绝对值都小于等于1，这棵树才是AVL

插入

前置概念：

左旋

以 某节点为旋转节点，其右子节点 变成 旋转节点的 父节点，右子节点的左子节点 变成旋转节点的 右子节点。

右旋

以 某节点为旋转节点，其左子节点 变成 旋转节点的 父节点，左子节点的右子节点 变成旋转节点的 左子节点。

绕的有点晕😵‍💫， 只看平衡因子

情况一：

插入节点后仍然平衡，不做任何调整

情况二：

插入节点后不平衡

旋转节点

此时旋转的节点都是不平衡节点（定义中提到的 **平衡因子 **绝对值不是 1 的节点）

LL: $右旋$

在最小不平衡子树根节点 左子树 根节点的 左子树 上插入节点

RR: $左旋$

在最小不平衡子树根节点 右子树 根节点的 右子树 上插入节点

LR: $左旋$ + $右旋$

在最小不平衡子树根节点 左子树 根节点的 右子树 上插入节点

• 先 LL 不平衡节点的左孩子 , 根据类型 判定旋转方式 就是 硬记

• 再右旋不平衡节点， 一般将 左子树 的 左孩子 当作新插入的节点

RL: $右旋$ + $左旋$

在最小不平衡子树根节点 右子树 根节点的 左子树 上插入节点

• 先 RR 不平衡节点的右孩子, 根据类型首字母 判定 优先旋转方式 就是 硬记

• 再左旋不平衡节点， 一般将 右子树 的 右孩子 当作新插入的节点

删除

情况一：

删除后不影响平衡 （删除的是叶子节点）

情况二：

删除后不再是平衡二叉树 （删除的是叶子节点）

和插入同样的 操作

情况三：

删除节点只有左、右孩子

正常分析

情况四：

删除节点平衡因子是 0/1 （删除节点同时有左右孩子）

若要删除该节点，需要与中序前驱交换后删除

情况五：

删除节点平衡因子 = -1 （删除节点同时有左右孩子）

若要删除该节点，需要与中序后继交换后删除

红黑树

AVL 平衡二叉树的 改进

Tip

定义

1. 红黑树 中 红结点不连续 (在一个连续的黑结点路径上隔开插入红结点推 2)

2. 根结点的 黑高 唯一 (从根结点到 任意叶结点 的 黑结点数) $\ge \frac{h}{2}$

3. 有 $n$ 个内部结点的红黑树的高度 $h\le 2{\log }_2(n+1)$

4. 树的 前黑高 层一定是 满二叉树 $n\ge 2^{\frac{h}{2}-1}$

3、4 都是基于 只有黑结点的情况

最短路径： 全黑

最长路近： 黑红参半

不长不短： 折中

插入

妈的怎么和玩魔方一样，这么多要背的公式 

插入的结点是 红色的 ，根据其插入的 父节点 是否为红色，选择性染色

插入的 大情况

一、 插入空树

直接插入红结点，染红为黑，其外部 叶结点 也是黑色

二、 父结点 为 黑

直接插入红结点

三、

1. 父红且叔红（祖父是根结点）

2. 父红且叔红（祖父不是根结点）

删除

bok 没讲，说明这部分难度很大，考到的概率较低。

小结

红黑树的考察不会很深，了解以下概念即可：

1. 从根结点到叶结点的最长路径不大于最短路径的 2 倍。

2. 根结点和叶结点是黑色的。

3. 不存在两个相邻的红结点。

4. 对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数量相同。

B树（多路平衡查找树)

近几年热门考点 也就 考考计算。

应用

内存调用磁盘

常用于 数据库 以及 文件系统 的索引结构（磁盘结构）

特性

B 树具备以下两个主要特点：

• 多路搜索树：B 树是一种多路搜索树，意味着每个节点可以拥有多个子节点，而不仅仅是两个（如二叉搜索树）。

  • 阶（Order）：B 树的阶定义了每个节点可以拥有的 最大子节点数。

• 平衡性：B 树通过保持所有叶子节点在同一层，确保了树的平衡，从而保证了搜索效率。

一颗 m 阶 B 树，满足如下特性：

• 树中每个结点最多有 $m$ 棵 子树，最多有 $m-1$ 个 关键字。

• 若 根节点 不是 叶子结点，至少有 两个 子树。

• 除了 根节点 外的所有 非叶结点 最少有 $\lceil m/2\rceil$ 棵子树，即最少有 $\lceil m/2\rceil -1$ 个 关键字

概念

为什么 非叶节点 最少 有 $\lceil m/2\rceil$ 颗子树？

核心目标：高空间利用率

B 树被设计出来的主要目的是为了在磁盘等辅助存储设备中存储海量数据。为了**减少磁盘 I/O（读取次数）**，我们希望：

1. 每个节点尽量装满：如果一个节点只放一个关键字，那它就退化成了普通的二叉搜索树，树会变得非常深。

2. 规定下限：通过规定每个节点（除根节点外）至少要达到半满状态 (即 $\lceil m/2\rceil -1$) ，确保了整棵树的存储空间利用率至少在 50% 以上。

算法层面的“对称性”

B 树的生长和收缩逻辑决定了这个数值：

1. 分裂（Split）的产物：当一个节点满载（拥有 $m-1$ 个关键字）再插入新元素时，它会分裂。分裂的结果是把中间的元素提到父节点，剩下的元素平分给两个新节点。

例如

$m=5$ 时，满载是 4 个关键字。插入第 5 个触发分裂，中间元素上提，左右各留 2 个。 $2$ 恰好就是 $\lceil 5/2\rceil -1=3-1=2$。

2. 合并（Merge）的阈值：正如你之前看到的删除操作，当关键字少于这个下限时，节点就必须去“借”或者“合并”。这个下限保证了两个“半满”的节点合并后，刚好不会超过上限 $m-1$。

自推结论

推导技巧

利用等比公式，先算结点数量，再根据每个结点最多或最少的关键字乘以节点数 从而得到对应关键字个数

1. $m$ 阶树，$n$ 层，最少关键字个数

$S_{关键字}=1+2(\lceil m/2\rceil -1)\frac{\lceil m/2{\rceil }^{n-1}-1}{\lceil m/2\rceil -1}=2\lceil m/2{\rceil }^{n-1}-1$

---

2. $m$ 阶树，$n$ 层，最多关键字个数

$S_{关键字}=m^n-1$ 不做推导了，和上面最小关键字的推导一致

---

1. $n$ 个关键字，$m$ 阶树，最多节点个数

查找

B 树的 层次 决定了 其 查找效率

层次越小，树高越小，则查找快

B 树查找与普通二叉查找树相似，但在每个节点上，需要进行多次比较。

1. **从 *根节点 开始：

   • 检查当前节点的键列表，键按升序排列。

   • 比较目标键  $k$ 与节点中的键  $k_i$​：

     • 如果 $k=ki$ ，找到目标键，返回对应的值（若存储 KV 对）。

     • 如果 $k<k1$​ （第一个键），选择最左子节点。

     • 如果 $k_i<k<k_i+1$​ ，选择 $ki$ 和 $k_{i+1}$​ 之间的子节点。

     • 如果 $k>kn$​ （最后一个键），选择最右子节点。

2. 递归向下：

   • 根据比较结果，进入选定的 子节点。

   • 重复步骤 1，直到到达 叶节点 或找到目标键。

3. 处理结果：

   • 在节点中找到键：返回对应的值（或指针）。

   • 到达 叶节点 仍未找到：键不存在，返回空或失败标志。

注意

B 树允许键出现在内部节点，因此查找可能在 **内部节点结束 **，而无需到达 叶节点。

插入

B 树的插入过程如下所示：

1. 查找关键字位置：

   • 从 根结点 开始，比较键值与节点中的键，选择合适的 子节点 继续递归向下，直到找到合适的 叶节点（插入点）。

   • B 树的所有插入操作 都在叶节点进行。

2. 插入关键字：

   • 将新键插入到 叶节点 的正确位置（保持键的有序性）。

   • 如果插入后 叶节点 的键数量不超过最大限制（$m-1$），插入完成，过程结束。

   • 如果插入后键数量超过 $m-1$ （即节点溢出），需要进行 分裂。

3. 节点分裂：

   • 假设节点有 m 个键（超限），将其分裂为两个新节点：

     • 取中间键（第 $\lceil m/2\rceil$个键）作为分隔键。

     • 分隔键上移到 父节点。

     • 原节点分裂为两个新节点，分别包含中间键之前的键和之后的键。

   • 每个新节点的键数量约为 $\lceil m/2\rceil -1$ （满足 B 树的最小键数要求）。

   • 子节点指针也相应分配到两个新节点。

4. 更新 父节点

   • 将中间键插入到 父节点 中（保持有序）。

   • 如果 父节点 插入后也溢出，对 父节点 重复 分裂 操作（步骤 3）。

   • 分裂 可能递归向上传播，直到某个节点不再溢出或创建新的 根节点。

     • 如果 根结点 分裂的话，则树的层数会增加一层。

插入举例

从零开始插入的 三阶 B 树

bok 版 B 树插入分析

符合定义

不符合定义

需要分裂

若父节点也不符合， 则套娃 继续将多余 关键字发配到 $\frac{m}{2}$ 向上取整个位置与父节点替换 其余分裂

删除

Caution

由于 可能会随机借到 前驱结点 或者是 后继结点 ，会导致 删除后的 B 树可能不唯一。

B 树的删除过程如下所示：

1. 查找关键字：首先查找要删除的关键字 k 。

   • 叶子节点中的关键字：

     • 如果键 k 在 叶子节点，且节点键数大于  $\lceil m/2\rceil -1$ （最小键数），直接删除 k 。

     • 如果节点键数等于 $\lceil m/2\rceil -1$ ，删除后会导致键数不足，需进行 修复（步骤 2）。

   • 内部节点中的关键字：

     • 找到 k 的前驱或后继键（通常是左子树的最大键或右子树的最小键，位于 叶子节点）。用前驱/后继键替换 k ，然后在 叶子节点 中删除该前驱/后继键。

     • 如果替换后 叶子节点 键数不足，需 修复（步骤 2）。

2. 节点键数不足的 修复*：当删除键后，节点键数少于 $\lceil m/2\rceil -1$ ，需要调整以恢复 B 树性质：

   • 借键：如果左/右兄弟节点有多余键，借一个

     • 从 父节点 取一个键到当前节点。

     • 从兄弟节点取一个键到 父节点，相应调整 子树 指针。

   • 合并：如果兄弟节点也没有多余键：

     • 将当前节点与一个兄弟节点合并。

     • 从 父节点 取一个键作为合并节点的中间键。

     • 更新 父节点 的键和指针。

     • 如果 父节点 键数不足，递归对 父节点 应用 修复。

3. 递归处理

   • 删除操作可能引发多层节点调整，需递归处理 父节点 的键数不足问题，直到满足 B 树性质或到达 根节点。

特殊情况：删除操作可能引发多层节点调整，需递归处理 父节点 的键数不足问题，直到满足 B 树性质或到达 根节点。

下面以 3 阶 B 树 为例说明一下删除的多种情况：

关键

B 树的出现是为了减少 磁盘 I/O，所以合并操作是尽可能的让磁盘中每个节点的利用率最大化，并不是说分裂的次数越多越好，反而是让节点尽可能的 “满”。

错误示例： 删叶子节点时 ，出现 关键字小于节点要求最小值的情况，我可以让60、65、75、80做两次相互交换，最终可以得到如下图所示的 B 树。

但是实际不能这样，必须让两个根结点上的一个关键字和一个孩子结点的关键字合并

B+ 树

定义

B+ 树是 B 树 的一种扩展；在 B+ 树 中，只有 叶子节点 存储数据，内部节点 存键

数据记录都存储在 叶子节点 中，并且 叶子节点 通过指针连接形成一个有序链表。

如下图所示：

回顾 B 树和 B+ 树 的新发现

可以看到B+ 树中，非叶结点关键字有 $n$ 个 ，该结点就有对应 $n$ 个子树

而B 树中，非叶结点 $n$ 个，则对应的子树要有 $n+1$ 个

插入

要求：只从叶子结点插入 关键字，要求有序

删除

删除时 也会出现 满足定义 和 不满足定义 的情况

如果不满足定义，需要向兄弟结点借关键字 或者 合并结点里的所有关键字。——同时，若节点最大值更新，则需要递归把索引更新到最大值。

B 树 与 B+ 树对比

题目类型

一般是根据 已知节点的 关键字数，反推一个 B 树的 阶数

---

小结

树形查找时间复杂度

散列表

hash table  也叫哈希表

为了提高数据在数组中的 存储和读取效率 使用 键值 和 数据项 相关联，然后使用 散列函数 将键转换为数组的 索引 这样可以通过 键 快速找相应 数据项

性能指标： $装载因子=\frac{当前存储元素的数量}{散列表容量}$ 该指标数值越大，散列冲突的可能性越大

1.1 散列函数

散列函数（Hash Function）是一种函数，它接受一个输入（或“键”）并返回一个输出（或“值”），通常用作数组的索引。其主要目的是均匀地分布键到数组中，以便在可能的范围内平均分配值，从而最大限度地减少冲突。

1.1.1 直接定址法

1.1.2 除留余数法

选取一个 不超过 散列表长 m 的质数 p，可金丝等概率落在 散列空间 的个个位置

---

一个好的散列函数应具有以下特性：

• 均匀分布：无论输入数据的分布如何，散列函数都应该确保输出均匀分布在其范围内，以减少冲突。

• 计算速度：散列函数应该快速计算，这样就不会成为整个哈希过程的瓶颈。

• 确定性：对于同一输入，散列函数应始终产生相同的输出。

• 最小冲突：尽管冲突是不可避免的，但好的散列函数应该使它们降到最低。

同义词

在哈希表中，同义词（synonym）指的是多个不同的键（key）通过哈希函数计算后，映射到 同一个哈希表位置（即相同的哈希值或索引）。这通常会导致 冲突，因为哈希表的一个槽位（bucket）只能存储一个键值对。

• 例如：

  • 假设哈希函数是 h(key) = key % 10，键 15 和 25 都会映射到索引 5（因为 15 % 10 = 5 和 25 % 10 = 5）。

  • 在这种情况下，15 和 25 就是同义词，因为它们在哈希表中竞争同一个位置。

同理，非同义词（non-synonym）指的是通过哈希函数计算后，映射到不同哈希表位置（即不同哈希值或索引）的键（key）。这些键不会竞争同一个槽位，因此不会引发冲突。!

2.1 冲突处理方法

2.1.1 开放地址法

过于简单不做解释

线性探测法 容易出现 聚集 （二次堆积）现象， 大大降低了查找效率

二次堆积

即 非同义词之间的冲突： 在原先冲突下 将元素处理 到非同义词位置上 ，某个元素属于该非同义词位置 需要占位 就会发生 二次堆积

二次探测法 真题可能有 正负 平方的 左右探测， 有的没有，需要辨识

2.1.2 拉链法

拉链法（Seperate Chaining）使用数组与 链表 相结合的方式。散列表的每个 槽位 都包含一个链表（或其他数据结构，如平衡树）。当发生冲突时，键值对被添加到相应槽位的链表中。

• 操作：

  • 查找：通过散列函数找到对应的索引位置，在该索引的链表中顺序查找键。

  • 插入：通过散列函数找到对应的索引位置。若该键在链表中已存在，更新其值；否则，在链表中添加新的键值对。

  • 删除：通过散列函数找到对应的索引位置。在链表中查找并删除对应的键值对，若未找到则无操作。

3.1 平均查找长度

为查找而做比较的次数 决定因素

1. 散列函数

2. 处理冲突方法

3. 装填因子 （不是散列表长度） 看的是 散列表装的 满不满

做题 要素

分为 成功 + 失败

3.1.1 查找失败

在考题中常常需要计算散列表 查找失败 时的平均查找长度，这里举一个实例说明。

假设哈希表如下图所示，哈希表的长度为 11，哈希函数为H(key) = key % 7, 采用线性探测法检测冲突。

散列地址	0	1	2	3	4	5	6	7	8
关键字	98	22	30	87	11	40	6	20

假如根据哈希函数计算出的初始查询位置为 0，查询失败时根据线性探测法一直向后探测，查找到位置 8 发现该位置为空得出查找失败，查询次数为 9，其他位置可以以此类推计算出来。

当查找一个新的 key 时，初始查询位置根据哈希函数计算可能在 0 到 6 之间，对于每个位置，查询失败时，需要查找的长度如下表所示：

位置	0	1	2	3	4	5	6
查找次数	9	8	7	6	5	4	3

查找失败的 平均查找长度 为 6（(9 + 8 + 7 + 6 + 5 + 4 + 3) / 7 = 6）

说明

用的是线性探测法，即使已经查到 $m-1$ 位（散列表中最后一个单元），依旧需回到表头继续探测，只有遇到空单元时才停止。

空单元也要比较一次。

散列函数：

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

取模相当于做了一个循环。

失败的平均查找长度：只看映射到的位置，即 $0\sim (模长-1)$。公式中除数就是模长。

拉链法（带链表的散列表）：

• 成功 ASL 的除数 = 关键字的个数
• 失败 ASL 的除数 = 表长

原因：拉链法中模长 = 表长，可减少冲突。

3.1.2 查找成功

查找成功时的平均查找长度如何计算呢？

只有存储在散列表中的元素才能被成功查找，对于这些元素，查找成功的长度分为两种情况：

• 使用散列函数 H(key) 查找到某个位置，该位置存储的元素就是 key，查找次数为 1

• 对于上述情况，该位置存储的元素不是 key，则向下一个位置探测，直到找到元素 key，探测次数为 N，则查找次数为 1 + N

将散列表中的所有元素的查找次数求和，然后除以 元素个数，即得到 查找成功时的平均查找长度。

例题

注意 除数 是 分布空间大小 还是 表长

根据 不同 处理冲突的方法 失败 的平均查找长度 是不一样的

错题

错因 对二叉排序树的 查找不理解

知识点 折半查找 的最坏时间以及平均时间复杂度都是${\log }_2(n+1)$，一般情况下 1 可以省去，表征为 ${\log }_{2}n$