algorithm - 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 个儿子，以获得最佳案例高度。