平衡 B 树有多平衡

Question

假设我有一个 B 树，其节点采用 3-4 配置（3 个元素和 4 个指针）。假设我按照规则合法地建立了我的树，我是否有可能达到一层有两个节点，一个节点有4个退出指针，另一个节点只有两个退出指针的情况？

一般来说，对于正确使用的 B 树的平衡性有什么保证

Answer 1

平衡（在一般平衡树数据结构中）背后的想法是任何两个子树之间的深度差异为零或一（取决于树）。换句话说，用于查找叶节点的比较次数总是相似的。

所以是的，你最终可能会遇到你所描述的情况，仅仅因为深度是相同的。每个节点中的元素数量与平衡无关（但见下文）。

这是完全合法的，即使左节点中的项目比右节点多（未显示空指针）：

                 +---+---+---+
                 | 8 |   |   |
                 +---+---+---+
        ________/    |
       /             |
      |              |
+---+---+---+  +---+---+---+
| 1 | 2 | 3 |  | 9 |   |   |
+---+---+---+  +---+---+---+

但是，拥有 3-4 BTree 是非常不寻常的（有些人实际上会说这不是根本就是 BTree，而是其他一些数据结构）。

对于 BTree，每个节点中的键数通常为偶数（例如 4-5 树），这样拆分和组合就更容易。对于 4-5 树，当节点填满时决定提升哪个键很容易 - 它是五个键中的中间一个。对于 3-4 树来说，这不是一个明确的问题，因为它可能是两个之一（四个元素没有明确的中间位置）。

它还允许您遵循节点应包含在 n 和 2n 元素之间的规则。此外（对于“正确的”BTree），叶节点都处于相同深度，而不仅仅是彼此在其中。

如果将以下值添加到空 BTree，则最终可能会出现您所描述的情况：

Add           Tree Structure
---          ----------------
 1                  1

 2                 1,2

 5                1,2,5

 6               1,2,5,6

 7                  5
                   / \
                1,2   6,7

 8                  5
                   / \
                1,2   6,7,8

 9                  5
                   / \
                1,2   6,7,8,9