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

【正解】ウ

【解説】 2分探索木から要素12を削除する場合，削除するノードに左右両方の子がある場合は，左部分木の最大値か右部分木の最小値で置き換えます。

要素12の右部分木の最小値は13です。13を12の位置に移動すれば，2分探索木の性質（左の子 < 親 < 右の子）が維持されます。

よって，ウの「13」が正解です。

アの「9」は12の左部分木に含まれる値ですが，最大値ではないため不適切です。 イの「10」は12の左の子ですが，10を移動すると10の部分木の再構成が必要になります。 エの「14」は12の右の子ですが，14を移動すると14の部分木の再構成が必要になります。

【ポイント】 2分探索木の削除では，「左部分木の最大値」または「右部分木の最小値」で置き換える方法が基本です。