問題プレビューID: 535d5ef8応用情報技術者試験 2024年(令和6年度)秋期 午前

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

次の 2 分探索木から要素 12 を削除したとき,その位置に別の要素を移動するだけで 2 分探索木を再構成するには,削除された要素の位置にどの要素を移動すればよいか。

解説

正解は「ウ」です。

2 分探索木で子を 2 つもつ節点を削除する場合,その位置には「左部分木の最大値」又は「右部分木の最小値」を移動させると,2 分探索木の性質(左部分木 < 節点 < 右部分木)を保ったまま再構成できます。どちらも,中順巡回で削除する節点の直前又は直後に現れる要素です。

削除する節点 12 の左部分木の最大値は 11,右部分木の最小値は 13 です。選択肢には 11 がないため,右部分木の最小値である 13 を 12 の位置へ移動します。13 は左の子をもたないので,13 を移動しても残りの部分木の構造を変える必要がなく,1 回の移動だけで 2 分探索木を再構成できます。

  • ア・イ: 9 や 10 を 12 の位置へ移すと,左部分木に 11 が残るなど大小関係が崩れ,2 分探索木になりません。
  • エ: 14 を 12 の位置へ移すと,右部分木に 13(14 より小さい要素)が残るため,2 分探索木の性質が保てません。

関連問題

本文が同じ・似ている問題を表示しています