応用情報技術者 2013年 秋期 午前2 問06

完全二分木の節点関係【午前2解説】

正解の理由

解法ステップ

1. 問題文から木の種類を確認する：葉以外の節点が必ず2子を持ち、根から葉までの深さが等しい → 完全二分木（完璧二分木）。
2. 深さを $h$ と置く（深さは根→葉の枝の個数）。
3. 各深さにおける節点数は幾何級数：深さ0（根）に $2^0$、深さ1に $2^1$ … 深さ$h$に $2^h$。
4. 葉の個数 $L=2^h$、内部節点数 $I={\sum }_{i=0}^{h-1}{2}^i=2^h-1$、総節点数 $N=I+L=2^{h+1}-1$ を使って各選択肢を検証する。

選択肢別の誤答解説

• ア: 「枝の個数が $n$ ならば、節点の個数も $n$ である。」
  どの木でも（連結な木の定義により）枝の個数 $E$ と節点の個数 $N$ は $E=N-1$ の関係が成り立ちます。従って枝数が $n$ なら節点数は $n+1$ であり、選択肢は誤りです。例：単純な根付き木で枝1本なら節点は2個。
• イ: 「木の深さが $n$ ならば、葉の個数は $2^{n-1}$ である。」
  深さを $h$ とすると、葉の個数は $2^h$ です（根を深さ0とする場合）。選択肢は指数の指数部が1小さいため誤りです。例えば深さ1のとき葉は $2^1=2$ 個だが、選択肢は $2^0=1$ として矛盾します。
• ウ: 「節点の個数が $n$ ならば、深さは ${\log }_{2}n$ である。」
  完全二分木の総節点数は $N=2^{h+1}-1$ なので、深さ $h$ は次の式で与えられます：
  $$h={\log }_2(N+1)-1={\log }_2\frac{N+1}{2}.$$
  したがって ${\log }_{2}N$ とは異なります。たとえば $N=7$ のとき正しい深さは $h={\log }_2(8)-1=3-1=2$ だが、${\log }_{2}7\approx 2.807$ となり整数にならないため選択肢は誤りです。選択肢ウは近似的に似ていることがあっても（大きな $N$ では違いが相対的に小さく見える）厳密には誤りです。
• エ: 「葉の個数が $n$ ならば、葉以外の節点の個数は $n-1$ である。」
  深さ $h$ のとき葉 $L=2^h$、内部節点 $I=2^h-1$ より $I=L-1$ が成立します。したがって選択肢 エ は正しい説明です。

よくある誤解

• 深さ（depth）を「節点数で数えるか、枝の数で数えるか」を混同する。今回の定義は「根から葉までの枝の個数」であり、根を深さ0とする表現に対応する。
• 「完全（完璧）二分木」と「完全二分探索木（完全性の別概念）」を混同する人がいる。ここで扱うのは構造が全層で満たされた二分木のこと。
• 近似的な式（例：$h\approx {\log }_{2}N$）を厳密解として使ってしまう。整数性や定数項を忘れないこと。

補足コラム

• 葉: $L=2^h$
• 内部節点: $I=2^h-1$
• 総節点: $N=2^{h+1}-1$
• 枝の個数: $E=N-1=2^{h+1}-2$

def perfect_binary_tree(h):
    L = 2**h           # 葉
    I = 2**h - 1       # 内部節点
    N = 2**(h+1) - 1   # 総節点
    E = N - 1          # 枝
    return {'depth':h,'leaves':L,'internal':I,'nodes':N,'edges':E}

FAQ