応用情報技術者試験 応用情報技術者試験 令和6年度秋期 午前 問5: 次の 2 分探索木から要素 12 を削除したとき，その位置に別の要素を移動するだけで 2 分探索木を再構成するには，削除された要素の位置にどの要素を移動すればよ

正解

ウ. 13

正答率 81.5%（660人中 538人が正解）

問題の解説

2分探索木では、各要素の左側の部分木は全て小さく、右側は全て大きい。子を二つもつ 12 を削除したときは、左側で最大の 11 か、右側で最小の 13 を移せば順序が保たれる。選択肢にあるのは 13 で、14 を根とする右側の部分木の最小の葉であり、移しても穴が残らない。

選択肢ごとの解説

• ア9 は左側の部分木(10 を根とする)で最小の要素である。移すと、9 より大きい 10 と 11 が左側に残り、条件に反する。
• イ10 は左側の部分木の根である。移すと、10 より大きい 11 が左側に残って条件に反し、子の 9 と 11 の付け替えも要る。
• ウ正しい。13 は右側の部分木で最小で、左側の 9、10、11 より大きく、右側の 14、15 より小さい。葉なので他を直す必要もない。
• エ14 は右側の部分木の根である。移すと、14 より小さい 13 が右側に残って条件に反し、子の付け替えも要る。