2分探索木とは？基本情報技術者試験 平成31年度 春期 午前 問5を解説

問題文

2分探索木として適切なものはどれか。ここで，数字 1〜9 は，各ノード（節）の値を表す。

この問題の出題ポイント

• 2分探索木の定義だけでなく、問題文中の条件がどの選択肢に当てはまるかを確認する。
• アルゴリズム分野では、用語の目的・主体・責任範囲の違いが選択肢で問われやすい。

選択肢

1. ア図ア: 根=1。右部分木に 2,3,...,9 を配置するが、内部で左部分木<親<右部分木の条件に違反するノードがある二分木。
2. イ図イ: 根=4、左部分木 = {2 を根とし 1,3 を子}、右部分木 = {8 を根とし 6,9 を子、6 の子に 5,7}。全ノードで左<親<右が成立する正しい二分探索木。正解
3. ウ図ウ: 根=7。左右配置に二分探索木の順序条件を満たさないノードを含む二分木。
4. エ図エ: 根=9。右部分木に根より小さい値があり、左<親<右の条件に違反する二分木。

解説

なぜ他の選択肢が違うのか

• ア

  根=1 の右に 2,3 を配置 (1<2,1<3 OK) だが、その下に 4-9 を配置する構造で条件が成立しない箇所がある。

• イ（正解）

  根=4、左=2(<4)、右=8(>4)、各部分木でも順序が保たれる。2分探索木の条件を満たし正解。

• ウ

  根=7、左=6(<7)、右=8(>7) は OK だが、左部分木の下に 4,5,3 配置で順序矛盾がある。

• エ

  根=9、左=7(<9)、右=8(>9 でない) — 右部分木の値が根より小さく矛盾。

解き方の整理

2分探索木の問題では、選択肢のキーワードだけで判断せず、問題文が示す条件と正解選択肢の説明が一致しているかを見ます。誤答選択肢は、似た用語を混ぜる、主体を入れ替える、目的や範囲を広げすぎる、という形で作られることが多いため、選択肢別解説まで確認しておくと復習効率が上がります。

関連問題

前後の問題

平成31年度 春期 午前 の関連する問題

平成31年度 春期 午前の問題一覧 基本情報技術者試験の解説一覧