平成25年度 春期 基本情報技術者試験 午前 問5

解説

12を削除した後もBSTを保つには，削除位置に「12の直前の値（左部分木の最大値）」か「12の直後の値（右部分木の最小値）」を移動させる必要があります。12の右部分木（14を根とする部分木）の最小値は13であり，13は子をもたない葉なので，そのまま12の位置に移動させるだけで大小関係を保った木に再構成できます。

選択肢ごとの解説

• ア誤り。9は12の左部分木の中でも最小の値であり，12の位置に移動すると9より小さいはずの値との大小関係を保てず，正しい2分探索木になりません。
• イ誤り。10は子（9と11）をもつため，10だけを12の位置に移動すると9と11の行き場がなくなり，単純な移動だけでは木を再構成できません。
• ウ正しい。12の右部分木（14配下）の中の最小値は13で，13は子をもたない葉なので，13を12の位置に移動するだけで大小関係を保ったまま木を再構成できます。
• エ誤り。14は子（13と15）をもつため，14だけを移動すると13と15の行き場がなくなり，単純な移動だけでは再構成できません。