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

完全二分木の性質に関する問題【午前2 解説】

要点まとめ

• 結論：葉の数が$n$の完全二分木では、葉以外の節点数は必ず$n-1$となる。
• 根拠：完全二分木はすべての内部節点が2つの子を持ち、節点数と葉数の関係が明確に定まるため。
• 差がつくポイント：深さや節点数の対数的関係を誤解せず、葉と内部節点の数の基本的な関係を理解すること。

正解の理由

よくある誤解

• 深さと葉の数の関係を混同し、指数関数的な増加を誤って適用することがあります。
• 節点数と葉の数の関係を単純に等しいと考える誤りも多いです。

解法ステップ

1. 問題文の条件「葉以外の節点はすべて2つの子を持つ」「根から葉までの深さが等しい」を確認する。
2. 完全二分木の定義を思い出し、節点数と葉の数の関係式を導く。
3. 節点数$N$と葉の数$L$の関係式$N=2L-1$を用いて、内部節点数を計算する。
4. 選択肢の中でこの関係を満たすものを選ぶ。

選択肢別の誤答解説

• ア: 「枝の個数が$n$ならば、葉を含む節点の個数も$n$である。」
  → 枝の数は節点数より1少ないため、節点数と枝数が等しいことはない。
• イ: 「木の深さが$n$ならば、葉の個数は$2^{n-1}$である。」
  → 深さ$n$の完全二分木の葉の数は$2^n$であり、指数の部分が誤っている。
• ウ: 「節点の個数が$n$ならば、深さは${\log }_{2}n$である。」
  → 深さは${\log }_2(n+1)$に近いが、正確には${\log }_2$の整数部分であり、単純に${\log }_{2}n$とは言えない。
• エ: 「葉の個数が$n$ならば、葉以外の節点の個数は$n-1$である。」
  → 完全二分木の基本的な性質に合致し正解。

補足コラム

FAQ