応用情報技術者 予想問題｜練習問題 第9問

解説

2分木では、根をレベル0として各レベルiに最大2^i個のノードを配置できる。高さhまで全レベルが埋まった完全2分木のノード総数は、2^0+2^1+…+2^hという初項1・公比2の等比数列の和であり、和の公式から(2^(h+1)−1)÷(2−1)=2^(h+1)−1個となる。例えば高さ2なら1+2+4=7=2^3−1で確認できる。2^hは最下層（レベルh）のノード数のみを表し全体の合計ではないため誤り。hや2hは高さに比例する値で、レベルが下がるごとにノード数が倍々で増える指数的性質を捉えていない。逆に、ノード数nの完全2分木の高さが約log₂nになるという対応関係は、2分探索木やヒープの計算量O(log n)の根拠になるので併せて覚えておきたい。