基本情報技術者 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