基本情報技術者試験のサンプル問題（科目A）を解いてみよう。
今回のテーマは、「2 分探索木」である。
問５
2 分探索木になっている2 分木はどれか。
正解：イ
まずは、二分探索木（BST: Binary Search Tree）の定義を確認しよう。
✅ 二分探索木（BST）の定義
任意のノード（節）において、
- 左部分木のすべてのノード < 親ノード
- 右部分木のすべてのノード > 親ノード
- 各ノードで再帰的にこの条件を満たす
各選択肢を検討しよう。
【ア】
- ノード16:
- 左：15（✅）／右：19（✅）
- ノード15:
- 左：10（✅）
- 右：14（❌）→ 15より小さいので左にあるべきだが、右にある。
➡️ ❌ BST違反（ノード15の右に14がある）
【イ】
- ノード17:
- 左：14（✅）／右：19（✅）
- ノード14:
- 左：10（✅）／右：16（✅）※16 > 14 < 17なので適切
- ノード19:
- 左：18（✅）※18 > 17
➡️ ✅ すべてのノードでBSTの条件を満たしている
【ウ】
- ノード16の右：14（❌）→ 14 < 16 なので左にあるべき
➡️ ❌ BST違反（ノード16の右に14）
【エ】
- ノード20の右：19（✅）
- ノード19の左：15（✅）／右：16（❌）→ 16 < 20 なので19の右にあってはいけない
- ノード18の右：14（❌）→ 14 < 18 なのに右にある
➡️ ❌ 複数のBST違反
✅結論
正解は【イ】となる。
コメント