問題プレビューID: 39f37eae基本情報技術者試験 午前免除試験 2016年6月12日

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

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

解説

正解は「ウ」です。

2 分探索木で子を 2 つもつ節点(ここでは 12)を削除し,その位置に 1 つの要素を移動させて再構成するには,左部分木の最大値(中間順巡回で直前の値)または右部分木の最小値(中間順巡回で直後の値)を移動させます。

  • 節点 12 の左部分木は {10, 9, 11} で,最大値は 11 です。
  • 節点 12 の右部分木は {14, 13, 15} で,最小値は 13 です。

このうち選択肢に含まれるのは 13 です。13 を 12 の位置に移動すると,左部分木の値はすべて 13 より小さく,右部分木の値はすべて 13 より大きいので,2 分探索木の性質が保たれます。よって,正解は「ウ」です。

  • ア・イ: 9,10 は 12 の左部分木にあり,移動しても大小関係が崩れます。
  • エ: 14 は 12 の右部分木の根であり,これを移動すると右部分木の他の要素(13,15)との関係が崩れます。

関連問題

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