data-structures - 为什么 2-3 树不能“允许” 1 级

Question

我一直在努力解决的一个问题......为什么2-3棵树的实现不允许节点的度数为1？

我认为它可能与它（作为 B 树家族的成员）想要保留的 O(log(n)) 有关，如果允许 1 级，我们可以得到这样的树：

1
 \
  2
   \
    3
     \
      4
       \
        5

例如，然后一些操作将采用 O(n) 而不是 O(log(n)) 但我看不出在这个答案中我提到了 2-3 树的位置以及为什么它不能允许度数为 1 .. . :-/

谢谢！;-)

Answer 1

你已经有了正确的答案，但也许你想这样说：

B-tree 变体将所有叶子保持在相同的深度（树的高度），并且操作通常花费与该高度成比例的时间。

由于内部节点必须至少有 2 个子节点，因此每个级别包含的节点数至少是父级别的两倍，并且树的高度为 O(log N)。

如果允许内部节点包含少于 2 个子节点，则高度可能大于 O(log N)，并且操作将花费比对数时间更长的时间。