正答3
解説
正解は3です。
2分探索木から子を二つもつ節を削除するときの再構成方法を問う問題です。
図の木では、削除する12の左部分木に10、9、11があり、右部分木に14、13、15があります。
2分探索木では、各節の左側は自分より小さい値、右側は大きい値でなければなりません。
【選択肢別解説】
1：× 9を12の位置に移すと、左部分木に残る10や11が9より大きくなり、条件を満たしません。
2：× 10を移すと、元の位置に残る子の9と11を付け直す必要があります。
移動するだけでは再構成できません。
3：○ 13は右部分木の最小値で、葉なので移動しても空きが生じません。
12の位置に置くと、左側の9、10、11はすべて13より小さく、右側の14、15は大きいので条件を満たします。
4：× 14を移すと、子の13と15の付け直しが必要になります。
移動だけでは再構成できません。
【ポイント】
子を二つもつ節を削除するときは、左部分木の最大値か右部分木の最小値を移動します。
本問では左部分木の最大値11も候補ですが、選択肢にあるのは13です。