爲什麼不能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），並且操作所需的時間會長於對數時間。