木と探索 2分木、頂点の総数、高さの最小値、対数関数、ガウスの記号、整数部分

学習環境

情報系のための離散数学 (猪股俊光 (著)、南野謙一 (著)、共立出版)の第8章(木と探索)、章末問題8.2の解答を求めてみる。

根から可能な限り2つの子がある場合に木の高さが最小となるので、その最小の高さをhとおくと、

\begin{array}{l} 2^{h} \leq n \leq 2^{k + 1} - 1 \\ 2^{h} \leq n < 2^{h + 1} \\ \log_{2} 2^{h} \leq \log_{2} n < \log_{2} 2^{h + 1} \\ h \leq \log_{2} n < h + 1 \end{array}

よって、

h = [\log_{2} n]