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

正解：ウ

AI解説

2分探索木からある節点を削除して1要素の移動だけで木を再構成するには、削除する節点の右部分木の最小値(中順の後続節)、または左部分木の最大値(中順の先行節)をその位置に移動させるのが基本的な手法である。本問ではこの条件を満たす要素は13である。 ア: 9は削除節点の位置に移動しても左右の大小関係(左<親<右)を保てない要素であり、正しい移動先ではない。 イ: 10も同様に、その位置に移動すると探索木としての大小関係の整合性が崩れるため、正しい移動先ではない。 ウ: 13は削除される要素12に対する中順の後続節(またはそれに相当する要素)であり、その位置に移動しても木全体の大小関係が保たれるため、正しい。 エ: 14も9・10と同様に、その位置へ移動すると木の大小関係の整合性が崩れるため、正しい移動先ではない。 💡 2分探索木の削除では「右部分木の最小値」か「左部分木の最大値」のどちらかを削除節点の位置に移動させれば、木全体の順序性(左<親<右)を保ったまま1要素の移動だけで再構成できるという性質を覚えておく。