2-3-4樹的上限和下限

Question

我要找到具有n個節點的2-3-4樹高度的上限和下限。坦率地說，我不知道如何開始。有這個公式嗎？我將不勝感激任何幫助和感謝！

Answer 1

最壞情況下，每個節點正好有2個兒子，所以你需要解決：

2^0 + 2^1 + 2^2 + ... + 2^h >= n 

尋找最小h滿足的條件爲您提供了「最壞情況」 2-3-4的高度樹。

用每個節點4個兒子重複該過程以獲得最佳情況高度。