令和6年度 秋期 応用情報技術者試験 午前 問5

解説

12を削除した位置には，子をもたない要素のうち，2分探索木の順序を保てる値（12の直前値11か直後値13）だけを単純な移動で補えます。選択肢に11がないため，12の右部分木で最小の要素である13に着目すると，13は左側の部分木（9,10,11）より大きく，右側に残る14・15より小さいため順序が保たれ，かつ13自身は子をもたないため移動元に穴が残る心配もありません。

選択肢ごとの解説

• ア誤り。9は子をもちませんが，移動すると9より大きい10や11が9の右側（大きい側）の部分木に残ってしまい，探索木の順序が崩れます。
• イ誤り。10は9と11という二つの子をもつため，10だけを移動すると9と11の行き場がなくなり，単純な移動では再構成できません。
• ウ正しい。13は子をもたない要素であり，左側の部分木の最大値11より大きく，右側に残る15より小さいため，そのまま12の位置に移動しても順序が保たれます。
• エ誤り。14は13と15という二つの子をもつため，14だけを移動すると13と15の行き場がなくなり，単純な移動では再構成できません。