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

【正解】ウ

2分探索木では、各節の左部分木にその節より小さい値、右部分木に大きい値を配置します。画像では、削除する12の左部分木は10を根として9、11を含み、右部分木は14を根として13、15を含んでいます。二つの子をもつ節を削除するときは、左部分木の最大値又は右部分木の最小値を移すと大小関係を維持できます。右部分木の最小値は13であり、13は葉でもあるので、12の位置へ移して元の位置から削除するだけで再構成できます。移動後は左側の最大値11＜13、右側の最小値14＞13となるため、ウが適切です。

アの9は誤りです。9を移すと、左部分木に9より大きい10や11が残り、左部分木は親より小さいという条件に反します。 イの10は誤りです。10を移すと、その左部分木側に含まれる11が10より大きいため、大小関係を維持できません。 エの14は誤りです。14を移しただけでは、その右側に14より小さい13が残ることになり、右部分木は親より大きいという条件に反します。

【ポイント】 二つの子をもつ節の削除では、「左部分木の最大値」又は「右部分木の最小値」を後継として選びます。 この二つは、それぞれ削除対象の直前又は直後に位置する値です。 図では左部分木の最大値11も条件を満たしますが、選択肢の中では右部分木の最小値13が該当します。