アルゴリズムとプログラミング
平成25年度 春期 基本情報技術者試験 午前 問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。
答えを選ぶ
出典：平成25年度 春期 基本情報技術者試験 午前 問5（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：ウ
覚える知識
2分探索木の要素削除(右部分木の最小値または左部分木の最大値で置換)
2分探索木で2つの子をもつ節点を削除する場合、右部分木の最小要素か左部分木の最大要素をその位置に移す。
この問題で必要なこと
子を2つもつ節点を削除するときは、右部分木の最小値(または左部分木の最大値)を移すと木が崩れない。12の右部分木の最小は13。
ひっかけ
左部分木の最大(11)ではなく右の最小を選ぶ必要がある点や、直下の子(10・14)を単純に移す誤りを誘う。
この知識の出題：本試験系 1 回・免除試験 3 回（公開問題での観測値）