3.3.4

上次更新:2021-10-25
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

一棵高度为 $ h $ 的完美二叉树有:$ 1 + 2 + 2^2 + … + 2^{h}= 2^{h+1} - 1 $ 个结点,反向得到 $ N $ 个结点的完美二叉树高度为 $ \log_2{(N+1)} -1 $。

一棵高度为 $ h $ 的完美三叉树有:$ 1+3+3^2+…+3^h= \frac{3^{h+1} - 1}{2} $ 个结点,反向得到 $ N $ 个结点的完美三叉树高度为 $ \log_3{(2N+1) - 1} $。

由于 2-3 树本身介于完美二叉树和完美三叉树之间,$N$ 个结点的 2-3 树高度就会介于 $N$ 个结点的完美二叉树和完美三叉树之间,即:$ \sim\lfloor log_3N \rfloor \le h \le \sim\lfloor log_2{N} \rfloor $。

另请参阅

完美二叉树, 完全二叉树和完满二叉树 - veli - 博客园 (cnblogs.com)

上一题