为什么不能2-3树“允许”度1

Question

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

我想这可能是涉及到O（日志（N））它（如B树家族的一员）要保持，如果度1被允许，我们可以得到这样的一棵树：

1 
 
\ 
 
    2 
 
    \ 
 
    3 
 
    \ 
 
     4 
 
     \ 
 
     5

例如，然后有些操作需要O（N），而不是为O（log（n））的 ，但我看不出在这个答案我称之为2-3树以及为什么它不能允许1级...： -/

谢谢！ ;-)

Answer 1

你已经拥有了正确的答案，但也许你要说它是这样的：

的B-tree的变体保持在同一深度的所有叶子（树 高度），和运营通常需要与高度成比例的时间。

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

如果允许内部节点包含 少于2个孩子，则高度可能大于O（log N），并且操作所需的时间会长于对数时间。