树形查找

★★★ 树二叉树

⭐ 中优先级

在选择题中会考查，重点掌握两点：1. m 阶 B 树的特性 。2. B 树和 B+ 树的不同点和适用场景。

基于 BST 的查找

在 二叉查找树 以及它的改进版本 AVL 树、红黑树 中，查找操作 都遵循相同的基本原则：利用 二叉树的有序性 来快速定位目标元素。

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

  • 左子树中所有节点的值 小于 根节点的值。
  • 右子树中所有节点的值 大于 根节点的值。
  • 这种「左小右大」的有序性，使得查找可以逐层缩小范围。

所以在基于二叉查找树进行查找时，过程如下：

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

查找过程可以通过以下图示进行理解：

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

  • 树的高度越小，查找路径越短，效率越高。
  • 树的高度越大（越“瘦长”），查找路径越长，效率越低。
树类型平均情况时间复杂度最坏情况时间复杂度说明
BST\(O(\log_2{n})\)\(O(n)\)如果树接近平衡，高度约为 \(\log_2{n}\)；但如果不断插入有序数据，可能退化为链表。
AVL\(O(\log_2{n})\)\(O(\log_2{n})\)通过严格的平衡条件保证树的高度始终在 \(\log_2{n}\) 量级。
红黑树\(O(\log_2{n})\)\(O(\log_2{n})\)相比 AVL，平衡条件更宽松，但依旧能保证树的高度不超过 \(2\log_2{n}\)。

B 树

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

特性

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

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

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

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

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

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

对于 3 阶 B 树 ，阶数 m=3 ，最小键数 = ⌈m/2⌉−1=2−1=1

3 阶 B 树 的非根节点（包括 叶子节点 和内部节点）最少有 1 个关键字 。

对于 5 阶 B 树 ，阶数 m=5 ，最小键数 = ⌈m/2⌉−1=3−1=2

5 阶 B 树 的非根节点（包括 叶子节点 和内部节点）最少有 2 个关键字 。

B 树 结点结构如下：

其中

  • n 为结点中 关键字 的个数
  • Ki​(i=1,2,⋯,n) 为结点中存储的 关键字 ，且满足 K1​<K2​<⋯<Kn​
  • Pi​(i=0,1,⋯,n) 为指向 子树 根结点的指针，且指针 Pi−1​ 所指 子树 中所有结点的 关键字 均小于 Ki​ ， Pi​ 所指 子树 中所有结点的 关键字 均大于 Ki​

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

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

提示

关于 B 树 的查找、插入、删除操作，可以借助 B 树交互演示 来帮助自己理解。

查找

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

  1. 从根节点** 开始**：
  • 检查当前节点的键列表，键按升序排列。
  • 比较目标键 k 与节点中的键 ki​ ：
    • 如果 k=ki​ ，找到目标键，返回对应的值（若存储 KV 对）。
    • 如果 k<k1​ （第一个键），选择最左子节点。
    • 如果 ki​<k<ki+1​ ，选择 ki​ 和 ki+1​ 之间的子节点。
    • 如果 k>kn​ （最后一个键），选择最右子节点。
  1. 递归向下 ：
  • 根据比较结果，进入选定的 子节点 。
  • 重复步骤 1，直到到达 叶节点 或找到目标键。
  1. 处理结果 ：
  • 在节点中找到键：返回对应的值（或指针）。
  • 到达 叶节点 仍未找到：键不存在，返回空或失败标志。

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

插入

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

  1. 查找关键字位置 ：
  • 从 根结点 开始，比较键值与节点中的键，选择合适的 子节点 继续递归向下，直到找到合适的 叶节点 （插入点）。
  • B 树 的所有插入操作 都在叶节点进行 。
  1. 插入关键字 ：
  • 将新键插入到 叶节点 的正确位置（保持键的有序性）。
  • 如果插入后 叶节点 的键数量不超过最大限制（ m−1 ），插入完成，过程结束。
  • 如果插入后键数量超过 m−1 （即节点溢出），需要进行 分裂 。
  1. 节点分裂 ：
  • 假设节点有 m 个键（超限），将其分裂为两个新节点：
    • 取中间键（第 ⌈m/2⌉ 个键）作为分隔键。
    • 分隔键上移到 父节点 。
    • 原节点分裂为两个新节点，分别包含中间键之前的键和之后的键。
  • 每个新节点的键数量约为 ⌈m/2⌉−1 （满足 B 树 的最小键数要求）。
  • 子节点 指针也相应分配到两个新节点。

3 阶 B 树中的插入操作

  1. 更新父节点****
  • 将中间键插入到 父节点 中（保持有序）。
  • 如果 父节点 插入后也溢出，对 父节点 重复 分裂 操作（步骤 3）。
  • 分裂 可能递归向上传播 ，直到某个节点不再溢出或创建新的 根节点 。
    • 如果 根结点 分裂的话，则树的层数会增加一层。

下图展示了一个三阶 B 树 的多次插入过程：

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

  1. 查找关键字 ：首先查找要删除的关键字 k 。
  • 叶子节点 中的关键字：
    • 如果键 k 在 叶子节点 ，且节点键数大于 ⌈m/2⌉−1 （最小键数），直接删除 k 。
    • 如果节点键数等于 ⌈m/2⌉−1 ，删除后会导致键数不足，需进行 修复 （步骤 2）。
  • 内部节点 中的关键字：
    • 找到 k 的前驱或后继键（通常是左子树的最大键或右子树的最小键，位于 叶子节点 ）。用前驱/后继键替换 k ，然后在 叶子节点 中删除该前驱/后继键。
    • 如果替换后 叶子节点 键数不足，需 修复 （步骤 2）。
  1. 节点键数不足的修复**** ：当删除键后，节点键数少于 ⌈m/2⌉−1 ，需要调整以恢复 B 树 性质：
  • 借键 ：如果左/右兄弟节点有多余键，借一个
    • 从 父节点 取一个键到当前节点。
    • 从兄弟节点取一个键到 父节点 ，相应调整 子树 指针。
  • 合并 ：如果兄弟节点也没有多余键：
    • 将当前节点与一个兄弟节点合并。
    • 从 父节点 取一个键作为合并节点的中间键。
    • 更新 父节点 的键和指针。
    • 如果 父节点 键数不足，递归对 父节点 应用 修复 。
  1. 递归处理
  • 删除操作可能引发多层节点调整，需递归处理 父节点 的键数不足问题，直到满足 B 树 性质或到达 根节点 。

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

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

B 树 删除过程细节过多，这里建议还是和学习平衡二叉树时采用相同方法，通过实际例子建立直觉即可。

B+ 树

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

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

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

特性

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

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

操作

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

  • 查找 ：

  • B 树 ：所有节点（包括内部节点）存储 KV 对 ，查找可能在内部节点结束。

  • B+ 树 ：只有 叶节点 存储 KV 对 ，查找必须到达 叶节点 。

    • 插入 ：

  • B 树 ：所有节点存储 KV 对 ，分裂时中间键值对整体上移。

  • B+ 树 ：只有 叶节点 存储 KV 对 ，分裂时中间键复制到 父节点 （仅键，不带值），叶节点 保留所有键。

    • 删除 ：

  • B 树 ：内部节点存储 KV 对 ，删除内部节点键需用后继/前驱替换，可能复杂。

  • B+ 树 ：删除只发生在 叶节点 ，内部节点键仅需调整（复制 叶节点 键），操作更简单。

B 和 B+ 树对比

特性B 树B+ 树
数据存储位置关键字和数据存在于内部和 叶子节点所有数据都存储在 叶子节点 ，内部节点只保存关键值和子节点的指针
叶子节点结构叶子节点与内部节点类似，保存关键字和数据所有 叶子节点 通过指针链接成链表
分支因子由于同时保存数据和关键字，可能较小通常较大，因为内部节点只保存关键字和指针
稳定性关键字位置可能会频繁变动数据位置相对稳定
应用场景适用于小至中等规模的数据存储系统更常见于大型数据库系统和文件系统
查找效率在内部节点找到关键字后，查找即完成查找必须遍历到 叶子节点 ，但由于通常高度较低，效率也很高

相关笔记

  • 图的算法和应用
  • 图的定义
  • 图概述
← 返回知识点列表