如果 B 树的内部节点的子节点的键数最少，如何删除该节点的键？

Question

原来的树

我有一棵5阶B树。如果我想删除键120，一位消息人士告诉我，如果该键的两个子节点都具有最小数量的键，那么删除后这些子节点将合并为一个节点。

所以 93 的右子节点应该是键为 96,115,125,141 的节点。

但是当我创建树并尝试使用这个可视化工具删除键 120 时，它给了我这棵树： 删除键120后的树

可视化工具

有人可以解释一下吗？

Answer 1

有多种算法可以执行删除。

Wikipedia - B-tree 中描述的过程有从 internal 节点删除密钥的过程，这就是您的情况：

1. 选择一个新的分隔符（左子树中最大的元素或右子树中最小的元素），将其从其所在的叶节点中删除，并用新分隔符替换要删除的元素。

2. 上一步从叶节点中删除了一个元素（新的分隔符）。如果该叶节点现在不足（节点数少于所需数量），则从该叶节点开始重新平衡树。

如果我们将此应用于您的场景，我们可以重点关注树的这一部分：

                  ┌─────┬─────┬─────┐
                  │  85 │  93 │ 120 │
                  ├─────┼─────┼─────┤
      ┌───────────┘ ┌───┘     └───┐ └───────────┐
┌─────┼─────┐ ┌─────┼─────┐ ┌─────┼─────┐ ┌─────┼─────┐
│  82 │  84 │ │  87 │  90 │ │  96 │ 115 │ │ 125 │ 141 │ 
└─────┴─────┘ └─────┴─────┘ └─────┴─────┘ └─────┴─────┘

在步骤 1 中，我们将键 115 标识为新的分隔符，因为它是键 120 下面的左子树中最大的元素。我们将其从叶子中删除，并将 120 替换为 115：

                  ┌─────┬─────┬─────┐
                  │  85 │  93 │ 115 │
                  ├─────┼─────┼─────┤
      ┌───────────┘ ┌───┘     └┐    └─────┐
┌─────┼─────┐ ┌─────┼─────┐ ┌──┴──┐ ┌─────┼─────┐
│  82 │  84 │ │  87 │  90 │ │  96 │ │ 125 │ 141 │ 
└─────┴─────┘ └─────┴─────┘ └─────┘ └─────┴─────┘

在第2步中我们确实发现密钥为96的叶子是“有缺陷的”，因此需要进行重新平衡操作。维基百科也描述了这个过程：

重新平衡从叶子开始，向根方向进行，直到树达到平衡。如果从节点中删除元素使其低于最小大小，则必须重新分配某些元素以使所有节点达到最小值。通常，重新分配涉及从节点数超过最小数量的同级节点中移动元素。这种重新分配操作称为轮换。如果没有兄弟节点可以腾出一个元素，则必须将有缺陷的节点与兄弟节点合并。

由于我们有缺陷的叶子的左兄弟或右兄弟都不会丢失密钥，因此在后一种情况下，必须合并有缺陷的节点。

其过程描述如下：

...如果两个直系兄弟姐妹都只有最少数量的元素，则与夹着从父级取下的分隔符的兄弟姐妹合并

我们可以与 96 左边的节点合并，将分隔符 93 夹在中间：

                  ┌─────┬─────┐
                  │  85 │ 115 │
                  ├─────┼─────┤
      ┌───────────┘     └─┐   └───────────────┐
┌─────┼─────┐ ┌─────┬─────┼─────┬─────┐ ┌─────┼─────┐
│  82 │  84 │ │  87 │  90 │  93 │  96 │ │ 125 │ 141 │ 
└─────┴─────┘ └─────┴─────┴─────┴─────┘ └─────┴─────┘

这就是您在模拟器中看到的结果。

您所描述的合并操作也是有效的：它需要额外的检查，因为它只能在合并的叶子不会超出最大容量时才能完成。如果不能保证这一点，您仍然需要遵循另一种算法，就像上面描述的那样。