平衡B-树的平衡程度

Question

假设我有一个B-Tree，它的节点是3-4个配置(3个元素和4个指针)。假设我根据规则合法地构建了我的树，我是否有可能达到这样的情况:一层中有两个节点，一个节点有4个退出指针，而另一个节点只有两个退出指针？

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

Answer 1

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

所以，是的，你可能会陷入你所描述的情况，因为深度是一样的。每个节点中的元素数量与余额无关(但请参见下文)。

这是完全合法的，即使左侧节点中的项目比右侧节点中的项目多(不显示空指针)：

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

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

使用BTrees，您通常在每个节点(例如，4-5个树)中有偶数个键作为最大值，以便拆分和合并更容易。对于4-5树，当节点填满时决定升级哪个键很容易-它是五个键中的中间一个。对于3-4树来说，这并不是一个明确的问题，因为它可能是两个元素中的一个(四个元素没有明确的中间)。

它还允许您遵循节点应包含在n和2n元素之间的规则。此外(对于“适当的”BTrees)，叶节点都在相同的深度，而不仅仅是彼此中的一个。

如果您将以下值添加到空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