树形查找

基于 BST 的查找

BST, AVL, 红黑树定义

使用 BST、AVL 或 红黑树 来存储数据，查询方式如下：

1. 从 根节点 开始。
2. 如果查询的值 等于 当前节点的值，返回 当前节点。
3. 如果查询的值 小于 当前节点的值，向 左子树 查询。
4. 如果查询的值 大于 当前节点的值，向 右子树 查询。
5. 如果到达 空节点，则查询失败，返回 NULL。

对于 BST，如果树是极度不平衡的（例如，成为链状结构），查询的 最坏时间复杂度 为 O(n)。

B 树

B 树，也叫做多路平衡查找树。
是一种自平衡的树形数据结构，它广泛应用于数据库和文件系统中，用于高效地存储和检索大量有序数据。

特性

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

• 多路搜索树：B 树是一种多路搜索树，意味着每个节点可以拥有多个子节点，而不仅仅是两个（如二叉搜索树）。
  • 阶（Order）：B 树的阶定义了每个节点可以拥有的 最大子节点数。
• 平衡性：B 树通过保持所有叶子节点在同一层，确保了树的平衡，从而保证了搜索效率。

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

• 树中每个结点最多有 $m$ 棵 子树，最多有 $m-1$ 个 关键字。
• 若 根节点 不是 叶子结点，至少有 两个 子树。
• 除了 根节点 外的所有 非叶结点 最少有 $\lceil m / 2 \rceil$ 棵子树，即最少有 $\lceil m/2 \rceil - 1$ 个 关键字。

B 树结点结构如下：

其中

• $n$ 为结点中 关键字 的个数
• $K_i (i = 1,2,\cdots,n)$ 为结点中存储的 关键字，且满足 $K_1 \lt K_2 \lt \cdots \lt K_n$
• $P_i (i = 0,1,\cdots,n)$ 为指向 子树 根结点的指针，且指针 $P_{i-1}$ 所指 子树 中所有结点的 关键字 均小于 $K_i$，$P_i$ 所指 子树 中所有结点的 关键字 均大于 $K_i$

以上图中的 5 阶 B 树 为例，说明 B 树的性质：

• 结点中的 孩子个数 等于结点中 关键字 的个数加 1。
• 除根节点外所有 非叶子结点 最少有 $\lceil m / 2 \rceil = \lceil 5 / 2 \rceil = 3$ 棵 子树（2 个 关键字），最多有 5 颗 子树（4 个 关键字）。
• 结点中 关键字 从左到右递增有序，关键字 左侧 指针所指子树的所有关键字均 小于 该关键字，右侧 指针所指子树的所有关键字均 大于 该关键字。

查找

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

1. 从 根节点 开始：
   • 检查当前节点的键列表，键按升序排列。
   • 比较目标键 $k$ 与节点中的键 $k_i$：
     • 如果 $k = k_i$，找到目标键，返回对应的值（若存储 KV 对）。
     • 如果 $k < k_1$（第一个键），选择最左子节点。
     • 如果 $k_i < k < k_{i+1}$，选择 $k_i$ 和 $k_{i+1}$ 之间的子节点。
     • 如果 $k > k_n$（最后一个键），选择最右子节点。
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 树的多次插入过程：

删除

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+ 树

在实际应用中，B 树和 B+ 树通常存储的是键值对（Key-Value），例如在数据库索引或文件系统中，键用于定位记录，值可以是数据本身或指向数据的指针。在上文关于 B 树的说明中，为了突出算法逻辑，我们将 B 树中的元素表示为单个键，省略值的部分。

实际上存储有 KV 对 的 B 树的结构如下图所示：

B+ 树是 B 树的一种扩展。
在 B+ 树中，只有 叶子节点 存储数据，而内部节点只存储键。所有的数据记录都存储在 叶子节点 中，并且 叶子节点 通过指针连接形成一个有序链表，如下图所示：

特性

一颗 $m$ 阶 B+ 树满足如下条件：

1. 节点的容量限制
   • 每个 非叶子节点（分支节点）最多有 $m$ 棵 子树。
   • 除 根节点 外，每个 非叶子节点 至少有 ⌈$m/2$⌉ 棵 子树。
2. 关键字与子树的关系
   • 在一个 非叶子节点 中，如果有 $k$ 个关键字，那么它会有 $k + 1$ 棵 子树。
   • 关键字起到分隔值域的作用，子树对应这些分隔区间。
3. 数据存储位置
   • 所有 数据记录（或指向数据的指针）都存储在 叶子节点 中。
   • 非叶子节点 只存储关键字，用于索引和导航，不直接存放数据。
4. 叶子节点的顺序结构
   • 所有 叶子节点 之间通过链表指针相连。
   • 这种顺序结构可以支持高效的范围查询和顺序遍历。

操作

B+ 树的操作考察不多，了解与 B 树相应操作的不同之处即可：

• 查找：
  • B 树：所有节点（包括内部节点）存储 KV 对，查找可能在内部节点结束。
  • B+ 树：只有 叶节点 存储 KV 对，查找必须到达 叶节点。
• 插入：
  • B 树：所有节点存储 KV 对，分裂时中间键值对整体上移。
  • B+ 树：只有 叶节点 存储 KV 对，分裂时中间键复制到 父节点（仅键，不带值），叶节点保留所有键。
• 删除：
  • B 树：内部节点存储 KV 对，删除内部节点键需用后继/前驱替换，可能复杂。
  • B+ 树：删除只发生在 叶节点，内部节点键仅需调整（复制 叶节点 键），操作更简单。

B 和 B+ 树对比