基本情報技術者 2016年 秋期 午前（科目A） 問06

2分探索木になっている2分木はどれか。【午前2 解説】

要点まとめ

• 結論：選択肢イが正解。全てのノードが「左部分木の値は小、右部分木の値は大」という二分探索木の条件を満たすため。
• 根拠：根17の左部分木（10,14,16）は17未満、右部分木（19,18）は17より大で、部分木ごとの範囲制約も矛盾しないため。
• 差がつくポイント：親子の大小だけでなく「部分木全体が親の範囲に収まるか」をチェックし、右に小さい値がないかを確認すること。

正解の理由

• 根17：左に14（およびその部分木10,16）はすべて17未満、右に19（およびその左子18）は全て17より大きい。
• 部分木内でも14の右子が16（14 < 16 < 17）や、19の左子が18（17 < 18 < 19）といった範囲制約を満たしています。
  したがって全体としてBSTの条件を満たすため正解です。

よくある誤解

• 親と直接の子の大小関係だけ確認して合格とする：部分木全体の最大・最小範囲も確認しないと見落としが生じます。
• 「左右の向き」を図の向きだけで判断してしまう：右子だから常に親より大、左子だから常に親より小、ではなく部分木全体の範囲で判断します。
• 同じ値（重複）の扱いを曖昧にする：問題文で扱いが示されていない場合は通常「左は小、右は大」の厳密不等号で判定します。

解法ステップ

1. 二分探索木の定義を再確認する：「左部分木 < ノード < 右部分木」。
2. 根から順に各ノードに「許容される最小値と最大値（範囲）」を割り当てる。初期は $(-\infty ,+\infty )$。
3. 左子なら上限を親の値未満に、右子なら下限を親の値より大に更新して再帰チェックする。
4. 全ノードがそれぞれの許容範囲に収まるかを確認すればBSTである。
5. 速く確認したい場合は中間順（in-order）巡回を行い、得られる値列が昇順になっていればBST。

# 範囲チェックでBST判定
def is_bst(node, low=float('-inf'), high=float('inf')):
    if node is None:
        return True
    val = node.value
    if not (low < val < high):
        return False
    return (is_bst(node.left, low, val) and
            is_bst(node.right, val, high))

選択肢別の誤答解説

• ア：根16の左部分木に15があり、15の右子が14になっている点が誤り。右子は親より大であるべきだが 14 < 15 なのでBST違反。
• イ：全ノードが範囲制約を満たし、in-orderで昇順（10,14,16,17,18,19）になるため正解。
• ウ：根18の左子16の右子が14になっている点で違反。16の右子は16より大きくなければならないが 14 < 16 で矛盾。
• エ：根20の右子が19になっており、右部分木の値が根より小さいため根で即違反。また右部分木のノード（15,16）も右側にあるべきではない値。

補足コラム

• 中間順（in-order）巡回の性質：BSTなら in-order の結果は昇順の並びになります。各選択肢の in-order を見ると、イのみが昇順になります。
  • アの in-order: [10, 15, 14, 16, 19]（昇順でない）
  • イの in-order: [10, 14, 16, 17, 18, 19]（昇順）
  • ウの in-order: [15, 16, 14, 18, 19, 20]（昇順でない）
  • エの in-order: [10, 18, 14, 20, 15, 19, 16]（昇順でない）
• 実装面では再帰的に範囲を伝播する方法が最も確実で O(n) の時間で判定可能です。

FAQ