アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20111218 実施分 問5
次の2分探索木から要素12を削除したとき，その位置に別の要素を移動するだけで2分探索木を再構成するには，削除された要素の位置にどの要素を移動すればよいか。
2分探索木（削除対象の12は太枠の円）。
6
├左 4
│ ├左 2
│ │ ├左 1
│ │ └右 3
│ └右 5
└右 8
├左 7
└右 12（太枠）
├左 10
│ ├左 9
│ └右 11
└右 14
├左 13
└右 15
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 20111218 実施分 問5（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：ウ
覚える知識
2分探索木の要素削除(右部分木の最小値または左部分木の最大値で置換)
2分探索木の節点削除では右部分木の最小値か左部分木の最大値で置き換える。
この問題で必要なこと
削除位置には右部分木の最小値(13)か左部分木の最大値(11)を移せば木の条件を保つ。選択肢には13のみある。
ひっかけ
14や10など直下の子を単に移すと大小関係が崩れる。
この知識の出題：本試験系 1 回・免除試験 3 回（公開問題での観測値）