平成25年度 春期 午前 問5

✓ これが正解ウ13

解説

右側にぶら下がる値の最小である13が入ります。

2分探索木は、どの節から見ても左にあるものが自分より小さく、右にあるものが自分より大きい、という決まりで保たれています。ある節を抜いて別の値を1つだけそこへ動かす場合、動かした値もこの決まりを満たさなければなりません。つまり、抜けた場所の左にぶら下がっているすべての値より大きく、右にぶら下がっているすべての値より小さい必要があります。この条件を満たす値は、左側の中でいちばん大きいものか、右側の中でいちばん小さいものの、たかだか二つです。図をたどると、抜く節の左側には9と10と11、右側には13と14と15があります。左側の最大にあたる値は選べる中になく、右側の最小である13が残ります。この値を据えると、左側の三つはすべてそれより小さく、残る14と15はすべてそれより大きくなり、決まりが保たれます。

ほかの選択肢はなぜ違うのか

• ア9：左側にぶら下がる値の中でいちばん小さい数です。これを据えると、同じ左側に残る10や11のほうが大きくなってしまい、左には小さい値という決まりに反します。
• イ10：左側の中ほどにある数です。これを据えると、左側に残る11のほうが大きくなるため、やはり左には小さい値という決まりが崩れます。
• エ14：右側の中ほどにある数です。これを据えると、右側に残る13のほうが小さくなってしまい、右には大きい値という決まりが崩れます。