応用情報技術者試験 応用情報技術者試験 令和6年度秋期 午前 問5: 次の 2 分探索木から要素 12 を削除したとき，その位置に別の要素を移動するだけで 2 分探索木を再構成するには，削除された要素の位置にどの要素を移動すればよ

問題本文

次の 2 分探索木から要素 12 を削除したとき，その位置に別の要素を移動するだけで 2 分探索木を再構成するには，削除された要素の位置にどの要素を移動すればよいか。

選択肢

• ア.9
• イ.10
• ウ.13
• エ.14

正解

ウ. 13

解説

2 分探索木は「左部分木の全要素＜節点の値＜右部分木の全要素」を常に満たす木で、ある節点を削除しても他の値を 1 つだけ動かして条件を保つには、削除した値の直前か直後の値（中間順での隣の値）を入れる。図の 12 は左部分木に｛10,9,11｝、右部分木に｛14,13,15｝を持ち、削除位置に入れられるのは左部分木の最大値 11 か右部分木の最小値 13 だけである。選択肢にあるのは 13 のみで、13 を移すと「12 より小さい左部分木＜13＜右部分木の残り 14,15」を満たし条件が保たれるため、正解はウである。

選択肢ごとの解説

• ア.9 は左部分木の最小値で、ここに移すと右部分木の 13・14・15 が 9 より大きいまま矛盾はないが、移動後に 10 や 11 が 9 より大きくなり左部分木側の整合が崩れ、1 要素の移動だけでは再構成できないため誤りである。
• イ.10 を削除位置に移すと、その元の子であった 9 と 11 の扱いが残り、10 の右部分木に 11（10 より大きい）が来るなど 1 要素の移動だけでは木が再構成できないため誤りである。
• ウ.13 は右部分木の最小値（12 の直後の値）で、削除位置に移すと左部分木の全要素＜13＜右部分木に残る 14・15 を満たし、他の節点を動かさずに 2 分探索木を再構成できるため正解である。
• エ.14 を削除位置に移すと、その左部分木にあった 13 が 14 より小さいまま右側に残るなど条件が崩れ、1 要素の移動だけでは再構成できないため誤りである。