Mika Field Notes

Article

算法导论-CH18-B树

算法导论-CH18-B树，待补充摘要。

May 21, 2026 修考 16 min read

CS61B 课程笔记：B-Trees (2-3 & 2-3-4 Trees)

一、 BST 高度危机与渐进性能分析 (BST Height & Worst Case)

1. 树的形态：Bushy (矮胖) vs. Spindly (单支)

二叉搜索树（BST）的性能与其形态息息相关。对于含有 NN 个节点的 BST：

  • Bushy Tree (矮胖/丰满型)：节点分布均匀，左右子树高度平衡。其高度 H=Θ(log⁡N)H = \Theta(\log N)。
  • Spindly Tree (单支/退化型)：节点退化为单链表结构。其高度 H=Θ(N)H = \Theta(N)。

Bushy Case:H=Θ(log⁡N)Spindly Case:H=Θ(N)\begin{aligned} &\text{Bushy Case:} \quad H = \Theta(\log N) \\ &\text{Spindly Case:} \quad H = \Theta(N) \end{aligned}

image-20260521135850815

💡 概念修正与补充：高度与平均深度对性能的影响

  • 高度 (Height)：定义为根节点到最深叶子节点的距离。高度决定了查找一个元素的最坏情况 (Worst Case) 运行时间。
    • 例如：执行 contains(x)，若元素不存在或在最深处，最坏需要比较 H+1H + 1 次。如果树是 spindly 的，其运行时间会退化至 Θ(N)\Theta(N)。
  • 平均深度 (Average Depth)：定义为树中所有节点深度的平均值。平均深度决定了查找一个元素的平均情况 (Average Case) 运行时间。

2. 随机插入的优秀性质 vs. 现实数据的有序痛点

  • 随机插入性质：如果我们将 NN 个不同的 key 以完全随机的顺序插入一个 BST 中：
    • 其期望的平均深度约为 ∼2ln⁡N=Θ(log⁡N)\sim 2 \ln N = \Theta(\log N)。
    • 其期望的树高度约为 ∼4.311ln⁡N=Θ(log⁡N)\sim 4.311 \ln N = \Theta(\log N)。
    • 这意味着随机插入可以让我们以极大概率得到一个 bushy tree，性能维持在 O(log⁡N)O(\log N)。
  • 现实痛点：在实际应用中，数据往往是有序或高度局部有序的（例如：按时间戳、自增 ID、字母表顺序输入）。如果直接按顺序插入 BST（如 1, 2, 3, 4, 5, 6, 7），BST 将不可避免地退化为一条 spindly tree，性能急剧变差。

二、 B-Tree 的核心设计：避免失衡 (Avoiding Imbalance)

1. 疯狂的直觉：永不添加新的底层叶子 (Overstuffing)

BST 失去平衡的根本原因在于：我们在底部不断地添加新的叶子节点，导致某些分支越长越深。

如果我们采取一个极端的想法：永远不往底部添加新叶子。当有新数据插入时，直接把数据塞入（Overstuff）现有的叶子节点中。

  • 优点：由于没有产生新的底层节点，树的高度（各分支的最大深度）永远不会改变，树保持完美的高度平衡。
  • 缺点：如果只塞不拆，单个节点中包含的元素数量会无限增长。这会导致我们在单个节点内进行线性查找的时间复杂度爆炸。

2. 解决方案：设定上限与节点分裂 (Node Splitting)

为了防止节点过于臃肿（Too juicy），我们引入 限额机制 与 分裂机制：

  1. 设定每个节点能容纳的最大元素上限 LL。
  2. 节点分裂 (Splitting)：
    • 当新元素插入后，若该叶子节点的元素个数超过了 LL（即含有 L+1L+1 个元素），我们需要将其中间元素（如中位数）向上提拔 (Give to parent)。
    • 被提拔的元素会将原节点一分为二，分裂为左、右两个子节点。
    • 提拔上去的元素会被融入父节点中。

3. 多路搜索特性：为什么 2 个元素的节点可以有 3 个孩子？

在传统的二叉树中，一个节点只有 1 个元素和 2 个孩子。在 B-Tree 中，一个节点如果有 2 个元素（设为 AA 和 BB，且 A<BA < B），它将拥有 3 个子树指针：

       [ A   B ]
      /    |    \
   < A   A~B     > B
  • 中间孩子 (Middle Child) 指针 指向的子树中，所有元素的值都在 [A,B][A, B] 之间。
  • 这种多路搜索树的性质保证了：若一个非叶节点拥有 kk 个键，它就必须恰好拥有 k+1k+1 个子指针。

三、 链式反应分裂与完美平衡 (Chain Reaction & Perfect Balance)

当节点分裂时，中间元素被提拔给父节点。如果此时父节点也已经达到上限 LL，那么父节点也会因为“过载”而发生分裂，并将中间元素继续向上提拔。

这种提拔会像多米诺骨牌一样，引发链式反应分裂 (Chain Reaction Splitting)。

🚨 终极挑战：如果根节点 (Root) 也满了怎么办？

如果根节点因为链式反应也被塞满（含有 L+1L+1 个元素），我们对根节点执行同样的分裂：

  1. 提取根节点的中间元素，创建一任全新的、只有一个元素的根节点。
  2. 将原根节点分裂为左、右两个孩子，挂在新的根节点下。

💡 完美平衡的核心秘密： 在整个 B-Tree 的生命周期中，只有当根节点发生分裂时，树的高度才会增加 1。而且，根节点分裂会将所有子树统一向下推一级，因此所有叶子节点到根节点的距离依然是完全相同的。这确保了 B-Tree 的完美平衡。

一道例题

image-20260521135958954

image-20260521140023602

image-20260521140034624

四、 B-Tree 的分类、不变量与最坏情况性能

1. 常见术语与分类

B-Tree 根据节点最大允许元素数 LL 的不同，有以下常见变体：

  • 2-3 Tree：L=2L = 2。每个非叶子节点可以有 2 个孩子（含 1 个元素）或 3 个孩子（含 2 个元素）。
  • 2-3-4 Tree（也称 2-4 树）：L=3L = 3。每个非叶子节点可以有 2、3 或 4 个孩子。

2. B-Tree 的两大核心不变量 (Invariants)

任何合法的 B-Tree 必须时刻满足以下两条钢性规则：

  1. 完美平衡：所有叶子节点到根节点的距离（即深度）必须完全相同。
  2. 非叶节点元素与孩子数对应：一个拥有 kk 个元素的非叶子节点，必须拥有恰好 k+1k+1 个非空孩子指针。

3. 性能分析 (Performance)

假设树中含有 NN 个元素，每个节点上限为 LL。

  • 树的高度 HH：介于 ∼log⁡L+1(N)\sim \log_{L+1}(N)（最 bushy 的最好情况，节点全满）与 ∼log⁡2(N)\sim \log_2(N)（最 spindly 的最坏情况，节点元素最少）之间。
  • 查找/插入时间复杂度：
    • 最坏需要检查 H+1H+1 个节点。
    • 在每个节点内，最多需要检查 LL 个元素（LL 是常数）。
    • 故整体时间复杂度：

Runtime=O(H⋅L)=O(Llog⁡N)=O(log⁡N)\text{Runtime} = O(H \cdot L) = O(L \log N) = O(\log N)

这证明了：B-Tree 能够无视任何糟糕的输入顺序，强制保证 O(log⁡N)O(\log N) 的高效查找与插入性能！

五、 B-Tree 插入例题精解 (以 2-3 Tree, L=2L=2 为例)

📝 例题 1：按顺序插入 1, 2, 3, 4, 5, 6, 7

我们向一个初始为空的 2-3 树（限制 L=2L=2，若出现 3 个元素，提拔中间元素）依次插入 1, 2, 3, 4, 5, 6, 7：

  1. 插入 1, 2： 直接装入根节点。

    [ 1   2 ]

  2. 插入 3： 节点满，元素变为 1, 2, 3。中间元素为 2。

    • 分裂：2 向上提拔作为新的根，1 和 3 成为其左右孩子。
        [ 2 ]
   /     \
 [1]     [3]

  3. 插入 4： 4 应该落入右侧叶子节点，右叶子未满。

        [ 2 ]
   /     \
 [1]    [3  4]

  4. 插入 5： 5 落入右侧叶子，使叶子过载为 3, 4, 5。

    • 局部叶子分裂：提取中间元素 4 提拔至父节点。
    • 父节点 [2] 吸收 4 变为 [2 4]。原本的孩子也被正确拆分。
        [ 2   4 ]
   /    |    \
 [1]   [3]   [5]

  5. 插入 6： 6 落入最右叶子。

        [ 2   4 ]
   /    |    \
 [1]   [3]  [5  6]

  6. 插入 7： 7 落入最右叶子，使之变为 5, 6, 7。

    • 第一次分裂 (叶子)：中间元素 6 提拔至父节点。
    • 此时父节点变为了 [2 4 6]（过载！）。
    • 第二次分裂 (父节点链式反应)：父节点 [2 4 6] 将中间元素 4 提拔，由于没有更上级的父节点，[4] 成为全新的根。原父节点分裂为 [2] 和 [6]。
             [ 4 ]
       /       \
    [ 2 ]     [ 6 ]
   /     \   /     \
 [1]     [3] [5]   [7]

    【分析】：瞧！在普通 BST 中会退化为单链表的数据，在 2-3 树中依然保持了完美的高度平衡（高度为 2，所有叶子都在同一层）！

六、 B-Tree 删除操作详解 (Deletion - Bonus)

删除操作是 B-Tree 最具挑战性的部分。我们需要分步骤处理，并遵守不变量规则。

1. 删除的基本前奏 (Reduction to Leaf Deletion)

正如普通 BST 删除拥有两个孩子的节点一样：

  1. 寻找后继元素 (Successor)：在待删元素 α\alpha 的右子树中找到其“后继”（即右子树中的最小元素）。由于 B-Tree 的性质，后继元素一定位于某个底部的叶子节点中。
  2. 交换与转化：将 α\alpha 的值与后继元素的值进行交换。
  3. 转化为叶子删除：现在，我们只需要将换到叶子节点中的 α\alpha 删掉。因此，所有删除问题最终都转化为“如何从叶子节点中删除一个元素”。

2. 核心挑战：如何填补空节点？ (Filling in Empty Nodes - FIEN)

  • 如果待删除的叶子节点中含有多个键（即删除一个元素后，节点内仍然至少有 1 个元素），我们直接删掉，大功告成。
  • 如果叶子节点中只有一个键（删除后，该节点变为空节点 XX）。由于空节点打破了 B-Tree 的不变量，我们必须进行填补。

填补空节点主要有以下三个 Case：

🟥 FIEN Case 1A：向富裕的兄弟“借”元素 (Multi-Key Sibling)

  • 适用场景：空节点 XX 的相邻兄弟节点拥有多个键（有多余的元素可以借）。
  • 操作逻辑：空节点 XX 抢夺父节点的某个键，而父节点则从富裕的兄弟节点那里抢来一个键补位。 (如果 XX 不是叶子节点，还需要相应地把兄弟节点的一棵子树转移给 XX)。
📝 练习题 1：在下树中删除 17
            [ 15   21 ]
           /    |     \
         ...  [18 19] [22 23]
  1. 待删元素为 17（未在图里标出，假设其是某个非叶子节点，经 successor 交换后已经变到右叶子 18 19 处的 17）。假设待删节点已经成了叶子节点中的 17（空节点 XX 出现，其相邻右兄弟为富裕的 [22 23]）。
  2. 逻辑推导：
    • XX 抢夺父亲的 21。
    • 父亲 21 从富裕的右兄弟抢走 22。
  3. FIEN 调整后的结果：
            [ 15   22 ]
           /    |     \
         ...   [21]  [23]

🟧 FIEN Case 2A：合并到富裕的父亲 (Multi-Key Parent, Single-Key Sibling)

  • 适用场景：空节点 XX 的所有兄弟都只有一个键（没得借），但是父节点比较富裕（拥有多个键）。
  • 操作逻辑：父节点拿出一个键，与 XX 以及它的穷兄弟进行三合一，合并成一个含有 2 个键的饱满新节点。原父节点失去一个键，但由于它本身富裕，所以依然保持合法。
📝 练习题 2：在下树中删除 3
           [ 1 ]
          /     \
       [ 5   8 ]
      /    |    \
    [3]   [6]   [9]
  1. 删去叶子节点 [3] 之后，原本的左孩子处留下一个空洞 XX。
  2. 分析状态：
    • XX 的相邻右兄弟为 [6]，只有一个键（无法出借）。
    • XX 的父节点为 [5 8]，拥有两个键（非常富裕！）。
  3. 逻辑推导：
    • 我们将空洞 XX 的兄弟 [6] 与父节点的键 5 拉下来，与 XX 合并。
    • 原合并处产生新叶子节点 [5 6]。
    • 父节点失去键 5，变为了单键节点 [8]。
  4. FIEN 调整后的结果：
           [ 1 ]
          /     \
        [ 8 ]
       /     \
    [5  6]   [9]

⬛ FIEN Case 3：全穷局面下的链式合并 (Single-Key Parent & Sibling)

  • 适用场景：空节点 XX 发现自己孤立无援：兄弟和父亲都只有一个键！
  • 操作逻辑：
    1. 将“单键父亲的唯一元素”、“单键兄弟”以及空洞合并成一个饱满的节点。
    2. 原来的父节点此时被掏空，从而在父节点层产生了一个新的空节点 XX。
    3. 向上递归：将这个空洞 XX 顺着父辈向上推。直到：
      • 某一层碰到了 Case 1A 或 Case 2A，停止递归。
      • 或者空洞一直推到了根节点。此时我们直接删除空根节点，整棵树的高度统一减少 1。
📝 练习题 3：在上图树中执行 delete(4)

原始树结构：

            [ 4 ]
          /       \
       [ 2 ]     [ 6 ]
      /     \   /     \
    [1]     [3] [5]   [7]

  1. 步骤一：交换后继

    • 4 是个非叶节点。找到其右子树的最小后继 5。
    • 交换 4 与 5 的值。原位置变成了 5，4 移动至右侧叶子节点中。
             [ 5 ]
       /       \
    [ 2 ]     [ 6 ]
   /     \   /     \
 [1]     [3] [4]   [7]

  2. 步骤二：删除叶子 4

    • 直接抹去 [4]，该叶子节点变为空洞 XX。
             [ 5 ]
       /       \
    [ 2 ]     [ 6 ]
   /     \   /     \
 [1]     [3]  X    [7]

  3. 步骤三：应用 FIEN 填补 XX

    • 观察：空洞 XX 的兄弟 [7] 是单键，父节点 [6] 也是单键。符合 Case 3。
    • 合并：将父节点键 6、兄弟键 7 合并在一起，代替 XX，生成新叶子 [6 7]。
    • 向上传递空洞：原父节点位置现在变为了一个空洞 XX。
             [ 5 ]
       /       \
    [ 2 ]       X
   /     \     /
 [1]     [3] [6 7]

  4. 步骤四：再次处理更高层的空洞 XX

    • 观察：现在空洞 XX 位于第一层。它的左兄弟是 [2]（单键），它的父节点是根节点 [5]（单键）。依然符合 Case 3！
    • 合并：将单键根 5、左兄弟 [2] 融合为新节点 [2 5]，它的子树被重新正确挂载（左子挂 [1]，中子挂 [3]，右子挂 [6 7]）。
    • 向上传递空洞：原根节点层产生了一个空洞 XX。
              X
          |
       [ 2   5 ]
      /    |    \
    [1]   [3]  [6  7]

  5. 步骤五：消除空根，高度减一

    • 空洞到达根部。我们直接舍弃这个多余的空根。
    • 最终整棵树缩减一层。
           [ 2   5 ]
      /    |    \
    [1]   [3]  [6  7]

    【分析】：经历如此剧烈的删除后，2-3 树成功重组，且所有叶子仍在同一高度，完美平衡规则依然无懈可击！