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

問題本文

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

選択肢

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

正解

ウ. 13

解説

2分探索木で内部ノードを削除する場合、その位置に置けるのは「左部分木の最大値」または「右部分木の最小値」です。要素12の右部分木の最小値は13（14の左部分木の最も左）であり、これを移動すると2分探索木の大小関係が維持されます。よってウが正解です。

選択肢ごとの解説

• ア.9は12の左部分木にある葉ですが、削除位置に置くと右部分木の最小値10より小さくなり、木の大小関係を維持できません。
• イ.10は左部分木の最大値ですが、それを12の位置に置くと右部分木との関係（10と11）が崩れ再構成が必要になります。
• ウ.13は12の右部分木の最小値であり、12の位置に置くと「左部分木のすべて < 13 < 右部分木のすべて」が満たされ正解です。
• エ.14は右部分木の根で、移動するとその子13と15の整合が崩れ、複数ノードの再配置が必要になります。