2分探索木からの削除
出典: 令和6年度 秋期 応用情報技術者試験 午前 問5 (IPA)
次の 2 分探索木から要素 12 を削除したとき，その位置に別の要素を移動するだけで 2 分探索木を再構成するには，削除された要素の位置にどの要素を移動すればよいか。
- ア 9
- イ 10
- ウ 13
- エ 14
正解と解説を見る
正解: ウ
- ア: 9 を移すと、右側に残る 10・11 が 9 より大きいのに左の部分木にあることになり、条件が崩れます。
- イ: 10 を移すと、左の部分木に残る 11 が 10 より大きくなり、条件が崩れます。
- ウ: 13 は右の部分木の最小値なので、12 の位置に移しても「左 ＜ 自分 ＜ 右」が保たれます。
- エ: 14 を移すと、右の部分木に残る 13 が 14 より小さくなり、条件が崩れます。
ポイント
- 2 分探索木では、どの節も「左の部分木の値 ＜ 自分 ＜ 右の部分木の値」を満たします。
- 子が 2 つある節を削除したときは、左の部分木の最大値 か 右の部分木の最小値 をその位置に移すと、条件を保てます。
- 12 の左の部分木の最大値は 11、右の部分木の最小値は 13 です。選択肢にあるのは 13 です。