アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20160612 実施分 問5
次の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。
- ア 9
- イ 10
- ウ 13
- エ 14
出典：基本情報技術者試験 科目A免除 修了試験 20160612 実施分 問5
答えと解説を見る
正解：ウ
覚える知識
2分探索木の要素削除(右部分木の最小値または左部分木の最大値で置換)
2分探索木で子を2つ持つ節を削除するには、左部分木の最大値か右部分木の最小値でその節を置き換える。
この問題で必要なこと
2分探索木の節を削除するときは、左部分木の最大値か右部分木の最小値を移動すれば大小関係を保てる。要素12では左部分木の最大値の11か、右部分木の最小値の13が候補になり、選択肢にあるのは13。
ひっかけ
左右の子(10や14)を単純に繰り上げると大小関係が崩れる。
この知識の出題：本試験系 1 回・免除試験 3 回（公開問題での観測値）