AP過去問 令和6年度秋期 午前 問5
問5(問題文)
次の2分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで2分探索木を再構成するには、削除された要素の位置にどの要素を移動すればよいか。
|
6
4
8
2
5
7
12
1
3
10
14
9
11
13
15
|
ア 9
イ 10
ウ 13
エ 14
回答・解説
2分探索木は自ノードの左側は全て小さい値である必要があり、右側は全て大きい値である必要があります。9を移動すると左に9より大きい10や11が残り駄目です。10を移動すると11をどこにつけるかという問題も生じますが、どこに付けたとしても、10より大きい11が左の残るので駄目です。14も同じようなことで、13をどこにつけるかという問題が生じつつ、どこに付けたとしても、14より小さい13が右に残るので駄目です。したがって、13がうまく行きます。11でもうまく行きますが、11は選択肢にないので、答えになりません。したがって、
ウ 13
が答えとなります。