応用情報技術者 2024年 秋期 午前2 問05

2分探索木から要素12を削除したときの再構成【午前2 解説】

要点まとめ

• 結論：削除したノード12の位置には、その右部分木の最小値である13を移動させるのが正解です。
• 根拠：2分探索木の性質を保つため、削除ノードの右部分木の中で最小の値を代わりに配置する必要があります。
• 差がつくポイント：削除ノードの左右部分木のどちらから代替ノードを選ぶか、またそのノードが部分木の最小・最大かを正確に理解することが重要です。

正解の理由

よくある誤解

解法ステップ

1. 削除対象ノード（12）の左右部分木を確認する。
2. 右部分木が存在する場合、その部分木の最小値を探す。
3. 右部分木の最小値ノード（13）を削除ノードの位置に移動する。
4. 移動したノードの元の位置は空になるため、必要に応じて部分木を再接続する。
5. 2分探索木の条件が保たれているか最終確認する。

選択肢別の誤答解説

• ア: 9 → 9は12の左部分木の左側にあり、12の右部分木の最小値ではないため不適切。
• イ: 10 → 10は12の左子の子であり、12の右部分木の最小値ではない。
• ウ: 13 → 正解。12の右部分木の最小値であり、2分探索木の条件を保つ。
• エ: 14 → 14は12の右子だが、右部分木の最小値ではなく、13より大きいため不適切。

補足コラム

1. 葉ノードの削除：単純に削除。
2. 子が1つのノードの削除：子ノードを親に繋ぎ直す。
3. 子が2つのノードの削除：右部分木の最小値（後継ノード）または左部分木の最大値（前任ノード）を移動させる。
   今回の問題は3番目のケースに該当します。

FAQ