基本情報技術者 2011年 春期 午前（科目A） 問05

二分探索木の構築【午前解説】

正解の理由

1. 8を挿入 → 根8
2. 12を挿入 → 12 > 8なので8の右子に12
3. 5を挿入 → 5 < 8なので8の左子に5
4. 3を挿入 → 3 < 8 → 3 < 5なので5の左子に3
5. 10を挿入 → 10 > 8 → 10 < 12なので12の左子に10
6. 7を挿入 → 7 < 8 → 7 > 5なので5の右子に7
7. 6を挿入 → 6 < 8 → 6 > 5 → 6 < 7なので7の左子に6

解法ステップ

1. 空の木に対して最初の値を根にする。ここでは8が根。
2. 次の値を根と比較し、より小さければ左へ、大きければ右へ移動する。空きがあればそこに挿入。
3. 挿入位置が見つかるまで手順2を繰り返す（再帰またはループで実装）。
4. 与えられた全値を順に処理すると最終構造が得られる（手作業なら各ステップをメモする）。

選択肢別の誤答解説

• ア：10が8の右直下になっているが、本来12が先に右に入り、10は12の左になるため不正。
• イ：10の位置が8の直下にあり、さらに12が10の子になっている構造で、挿入順（12が先）に反します。
• ウ：3の下に7がぶら下がっている等、7の位置が不自然であり、7は5の右子でかつ6を子に持つべきなので誤りです。
• エ：8を根に、左に5（その左に3、右に7、その7の左に6）、右に12（その左に10）という正しい構造であり、与えられた挿入順に一致します。→ 正解は エ

よくある誤解

• 「最後に見た親の左右に入れる」と思い込み、比較を途中で止めて誤った位置に挿入してしまう。必ずルートから比較を継続する必要があります。
• 10を8の右直下に置く誤り。12が先に挿入されているため、10は12の左になる点を見落とすことが多いです。
• 図の左右（描画上の位置）を見て大小を判断する誤り。左＝小、右＝大というルールを厳密に適用してください。

補足コラム

• この木の中順（in-order）走査は3, 5, 6, 7, 8, 10, 12の昇順を返します。BSTの性質確認に便利です。
• 挿入の計算量は平均O(log n)、最悪O(n)（偏った木）です。今回の挿入順は完全な平衡を作らず、やや偏りがあります。
• 実装例（概念）:

class Node:
    def __init__(self, v): self.v=v; self.left=None; self.right=None

def insert(root, v):
    if root is None: return Node(v)
    if v < root.v: root.left = insert(root.left, v)
    else: root.right = insert(root.right, v)
    return root

# 例: seq = [8,12,5,3,10,7,6]

FAQ