平衡的B树是如何平衡的

Question

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

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

Answer 1

平衡背后的想法(通常是平衡树数据结构)是任何两个子树之间的深度差异为零或一(取决于树).换句话说,用于查找叶节点的比较数总是相似的.

所以,是的,你可以最终处理你描述的情况,因为深度是相同的.每个节点中的元素数量不是余额的关注点(但见下文).

这是完全合法的,即使左侧节点中的项目多于右侧(未显示空指针):

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

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

使用BTrees,您通常在每个节点中具有偶数个键(例如,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