問題プレビューID: e26ab2b7基本情報技術者試験 午前免除試験 2011年12月18日

問 5
基本情報技術者試験 午前免除試験 2011年12月18日

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

解説

正解は「ウ」です。

2 分探索木から要素を削除するとき,その位置に別の要素を 1 つ移動するだけで再構成するには,削除する要素の左部分木の最大値,又は右部分木の最小値を移動します。

削除する要素 12 の左部分木は {10, 9, 11} で最大値は 11,右部分木は {14, 13, 15} で最小値は 13 です。選択肢にあるのは 13 なので,12 の位置には 13 を移動します。

  • ア・イ: 9 や 10 は 12 の左部分木に属し,移動すると大小関係が崩れる。
  • ウ: 13 は 12 の右部分木の最小値であり,12 の位置に移動しても 2 分探索木の条件を満たす。正しい。
  • エ: 14 は 12 の右の子であり,これを 12 の位置に移動すると 13 を正しく配置できなくなる。

関連問題

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