基本情報技術者 2025年 科目A 問03

二分探索木の値順序【午前解説】

正解の理由

解法ステップ

1. 二分探索木の定義を確認：左部分木の値 < 自ノードの値 < 右部分木の値。
2. 図の各部分木ごとに局所的な順序を決める：
   • 左部分木（根 b）：左子 d、右子 e → $d<b<e$。
   • 右部分木（根 c）：左子 f、右子 g → $f<c<g$。
3. 左部分木全体は a より小さく、右部分木全体は a より大きいので、左右を結合：
   • 結果の順序：$d<b<e<a<f<c<g$。
4. 各選択肢と比較して一致するものを選ぶ（イ）。

選択肢別の誤答解説

• ア: a < b < d < e < c < f < g
  根 a が左子 b より小さいとするが、BSTでは左子を含む左部分木は根 a より小さいはずで矛盾する（a < b は不適）。
• イ: d < b < e < a < f < c < g
  中順走査から得られる正しい順序。図の配置とBSTの条件に一致する。
• ウ: d < e < f < g < b < c < a
  左部分木内の順序が誤っている（d と e の関係は d < b < e であり、d < e としても b の位置が不正）。また a が最大とするが、右部分木が a より大きいことに反する。
• エ: g < f < c < e < d < b < a
  ほとんどが逆順になっており、左・右の関係や部分木内の順序がすべて矛盾する。BST の定義と合致しない。

よくある誤解

• 「左側のノード＝必ず小さい」はノード単体だけを見て判断しがちで、部分木全体の関係（左部分木のすべてが根より小さい）を忘れると間違える。
• 中順走査（左→根→右）を知らないと、ノードの左右位置と大小関係の対応が分かりにくい。図の左右と大小を混同しやすい。
• 兄弟ノードの左右順が値の大小順と同一とは限らない（位置は値そのものを決めない）。必ず部分木の規則に基づいて評価する。

補足コラム

• 中順（in-order）走査は二分探索木の値を昇順で出力する性質があります。実装的には再帰で左→根→右をたどるだけで、出力配列が昇順であればその木はBSTの条件を満たしていることを確認できます。
• BST の妥当性検査は、各ノードに対して許容範囲（min, max）を持たせる方法で効率よく O(n) で行えます。疑似コード：

def is_bst(node, low=-inf, high=inf):
    if node is None:
        return True
    if not (low < node.val < high):
        return False
    return (is_bst(node.left, low, node.val) and
            is_bst(node.right, node.val, high))

• 問題では値の重複がないと明示されているので不等号はすべて厳密（<）で扱えます。

FAQ