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$。