完全 2 分木の性質
出典: 平成30年度 秋期 応用情報技術者試験 午前 問6 (IPA)
葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，木の深さとは根から葉に至るまでの枝の個数を表す。また，節点には根及び葉も含まれる。
- ア 枝の個数が n ならば，節点の個数も n である。
- イ 木の深さが n ならば，葉の個数は 2ⁿ⁻¹ である。
- ウ 節点の個数が n ならば，木の深さは log₂n である。
- エ 葉の個数が n ならば，葉以外の節点の個数は n－1 である。
正解と解説を見る
正解: エ
- ア: 木では、枝の数は節点の数より 1 少なくなります (節点 7 個なら枝 6 本)。
- イ: 深さが n のとき、葉の数は 2ⁿ です (深さ 1 で葉は 2 個)。
- ウ: 節点の数が n のとき、深さは log₂(n ＋ 1) − 1 です (節点 7 個で深さ 2)。
- エ: 葉の数が n なら、葉以外の節点の数は n − 1 です (葉 4 個なら葉以外 3 個)。正しい記述です。
ポイント
葉以外の節点が全て子を 2 つ持ち、深さがそろった木 (完全 2 分木) では、深さを d とすると次のようになります。
- 葉の数: 2ᵈ
- 葉以外の節点の数: 1 ＋ 2 ＋ … ＋ 2ᵈ⁻¹ = 2ᵈ − 1 (= 葉の数 − 1)
- 節点の数: 2ᵈ⁺¹ − 1、枝の数: 節点の数 − 1
例: 深さ 2 なら、葉 4 個、葉以外 3 個、節点 7 個、枝 6 本です。