問題プレビューID: 35227fc0基本情報技術者試験 午前免除試験 2017年12月10日

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

次の2分探索木から要素12を削除したとき,その位置に別の要素を移動するだけで2分探索木を再構成するには,削除された要素の位置にどの要素を移動すればよいか。ここで,2分探索木は,根を6とし,6の左の子を4,右の子を8とする。4の左の子を2,右の子を5とし,2の左の子を1,右の子を3とする。8の左の子を7,右の子を12とし,12の左の子を10,右の子を14とする。10の左の子を9,右の子を11とし,14の左の子を13,右の子を15とする。

解説

正解は「ウ」です。

2分探索木から要素を削除するとき,その位置に1つの要素を移動するだけで再構成するには,削除する要素の左部分木の最大値(中順後続の直前)または右部分木の最小値(中順後続)を移動します。移動する要素が葉であれば,他の部分木の構造を変えずに済みます。

削除する12の右部分木は14(子に13,15)で,その最小値は13です。13は葉であるため,12の位置に移動しても,左部分木(10を根とし9,11を含む)の値より大きく,右部分木(14,15)の値より小さいという2分探索木の条件を保てます。

  • ア: 9 は12の左部分木に属するため,12の位置に移動すると右部分木との大小関係が崩れます。
  • イ: 10 を移動すると,その子(9,11)の配置し直しが必要となり,「別の要素を移動するだけ」では済みません。
  • ウ: 13 は12の右部分木の最小値であり,葉なので移動するだけで再構成できます。
  • エ: 14 を移動すると,その子(13,15)の配置し直しが必要となり,条件を満たせません。

関連問題

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