3.3.4

3.3.4 #

解答 #

一棵高度为 $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$ 。