アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20171210 実施分 問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。
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 20171210 実施分 問5（問題文は IPA の公開問題。解説は当サイト作成）
解説に誤りを見つけたら、解説の誤りを報告してください。
答えと解説を見る
正解：ウ
覚える知識
2分探索木の要素削除(右部分木の最小値または左部分木の最大値で置換)
2分探索木の節削除では、左部分木の最大値または右部分木の最小値を削除位置に移して順序を保つ。
この問題で必要なこと
節12を削除して木を再構成するには、左部分木の最大値か右部分木の最小値で置換する。左部分木(10,9,11)の最大は11、右部分木(14,13,15)の最小は13で、選択肢にあるのは13。
ひっかけ
9・10・14は左右部分木の最大/最小ではなく、移すと大小関係が崩れる。
この知識の出題：本試験系 1 回・免除試験 3 回（公開問題での観測値）。頻出知識ランキング561位（全1,254件中）。