応用情報技術者 2011年 春期 午前2 問06

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

正解の理由

• 深さが $h$ の完全二分木では葉 $L=2^h$。
• 内部節点 $I=2^h-1=L-1$。よって葉が $n$ なら内部は $n-1$。

解法ステップ

1. 「完全二分木」の定義を確認する：各内部節点はちょうど2つの子をもち、すべての葉が同じ深さ $h$ にある。
2. レベルごとの節点数を考える：根のレベル0に1個、レベル1に2個、… レベル$h$に$2^h$個（葉）。
3. 葉の個数は最下層の節点数なので $L=2^h$。
4. 全節点数は各レベルを合計して $T={\sum }_{i=0}^h{2}^i=2^{h+1}-1$。
5. 内部節点数は $I=T-L=(2^{h+1}-1)-2^h=2^h-1=L-1$。
6. 各選択肢と上の関係式を照らし合わせて正誤を判断する（結果：エが正しい）。

選択肢別の誤答解説

• ア: 「枝の個数が $n$ ならば、葉を含む節点の個数も $n$ である。」
  • 木一般で枝（辺）数 $E$ と節点数 $T$ の関係は $E=T-1$。したがって枝が $n$ なら節点は $n+1$。よって誤り。
• イ: 「木の深さが $n$ ならば、葉の個数は $2^{n-1}$ である。」
  • 深さを $n$（枝の数）とすると、最下層の節点数は $2^n$。選択肢はべき乗が一つ小さく誤っている。
• ウ: 「節点の個数が $n$ ならば、深さは ${\log }_{2}n$ である。」
  • 完全二分木の全節点数を $T$ とすると $T=2^{h+1}-1$。これを解くと $$h={\log }_2(T+1)-1.$$ 単に ${\log }_{2}n$ とするのは誤り（定数のずれがある）。また $h$ は整数で、$T+1$ は2の冪でなければならない点も重要（$T$ の任意の $n$ に対して成立しない）。
• エ: 「葉の個数が $n$ ならば、葉以外の節点の個数は $n-1$」
  • 上述の通り $I=L-1$ であり正しい。

よくある誤解

1. 「深さ $n$ の葉は $2^{n-1}$」とする勘違い
   • レベル数（節点の列）と枝の数（深さ）の混同。深さ $h$ の最下層の節点数は $2^h$。
2. 「節点数 $n$ から深さは ${\log }_{2}n$」とする単純化
   • 全節点数は $2^{h+1}-1$ の形。逆に求めるときは $h={\log }_2(n+1)-1$ で、$n+1$ が2の冪である必要がある。
3. 木の一般的性質（任意の木）と完全二分木の特殊性を混同する
   • 「内部節点が必ず1つ少ない」という関係は完全（満たされた）二分木の特性。一般の木では成立しない。

補足コラム

• 代表的な式のまとめ（深さ $h$, 葉 $L$, 内部 $I$, 全節点 $T$, 枝 $E$）：
  • $L=2^h$
  • $T=2^{h+1}-1=2L-1$
  • $I=L-1$
  • $E=T-1=2L-2=2I$
• 逆算の注意点：節点数 $T$ が与えられたときに深さ $h$ を求めるには $T+1$ が2の冪である必要がある。例えば $T=15$ の場合 $T+1=16=2^4$ であり $h=3$。
• 「完全二分木」と「完全（complete）二分木」「満二分木（perfect）」という用語にはずれがある場合がある。ここで扱ったのは「各内部節点が2子を持ち、すべての葉が同じ深さにある」いわゆる満（perfect）二分木。

FAQ