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

二分探索木の要素削除【午前解説】

正解の理由

解法ステップ

1. 削除するノード（12）を確認し、子の有無を調べる。ここでは左右両方に子がある。
2. 両子がある場合は置換候補を決める。通常は右部分木の最小値（in-order successor）または左部分木の最大値（in-order predecessor）。
3. 右部分木（14を根とする部分木）の最小値を探索する：14の左子が13で、13は左にさらなる子がないため最小。
4. 候補（13）を削除ノード（12）の位置にコピーまたは移動し、元の13のノードを削除（葉なので単に取り除く）。
5. 結果として得られる木は二分探索木の性質（左は小さい、右は大きい）を満たす。

選択肢別の誤答解説

• ア: 9 — 9は12の左部分木の奥（10の左）にあり、小さすぎて12の元の右部分木（14やその部分）よりも小さいため、12の位置に移すと右部分木との大小関係を保てず不適。
• イ: 10 — 10は12の左部分木の根であり子（9,11）を持つため、10をそのまま12の位置に移すと元の10の位置の再接続が必要になり「移動するだけ」で済まない。
• ウ: 13 — 正解。12の右部分木の最小値であり元の位置は葉なので、13を移動しても他の再接続が最小限で済み、BSTの順序性が保たれる。
• エ: 14 — 14を上げるとその右部分木（15）は問題ないが、14は12より大きく、12の元の左部分木（10など）よりも適切に収まらない配置となる場合があるため不適切。

よくある誤解

• 近い数値を選べばよい：数値が12に近い（例えば11や13）だけで正解とは限らず、木構造上の位置と元のノードの子の有無が重要です。
• 親ノード（14や8）をそのまま上げれば良い：親や兄弟を移すと部分木の範囲が崩れる場合があり、単純に位置交換できるとは限りません。
• 左部分木の最大値しか使えないと思い込む：どちらの方法（左の最大 / 右の最小）でも置換は可能だが、候補が葉や単子であるかを確認する必要があります。

補足コラム

• 削除アルゴリズムの時間計算量は深さhに比例して $O(h)$（平衡木なら $O(\log n)$）。
• 置換候補が「直接右子」である場合（例：削除ノードの右子に左子が存在しない）、その右子をそのまま上に持ってくる手法が最も単純です。
• in-order successor（右最小）と in-order predecessor（左最大）はどちらを使ってもよいが、実装上は片方を選んで一貫して処理することが多いです。
• 問題文の条件「その位置に別の要素を移動するだけで再構成する」では、移動元ノードが葉である候補が理想です。今回13は葉だったため最短手順で完了します。

FAQ