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

正解

ウ. 13

正答率 63.2%（1,305人中 825人が正解）

問題の解説

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

選択肢ごとの解説

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