応用情報技術者 試験情報＆徹底解説

2分探索木は、2分木の各節にデータをもたせることで探索を行えるようにした木です。各節がもつデータは「その節から出る左部分木にあるどのデータよりも大きく、右部分木のどのデータよりも小さい」という条件があり、これを利用して効率的なデータ探索を可能にしています。
問題文の2分探索木からルートノード7を削除すると、2分探索木の性質を保つために7に最も近い6または8をルートノードとして再構成が行われます。6をルートノードとして、再び7を挿入する場合には次の比較手順で挿入場所が決定されます。

1. 7＞6　…右の節へ
2. 7＜9　…左の節へ
3. 7＜8　…8には子がないので、7を8の左の子とする

8をルートノードとした場合には、

1. 7＜8　…左の節へ
2. 7＞3　…右の節へ
3. 7＞5　…右の節へ
4. 7＞6　…6には子がないので、7を6の右の子とする

それぞれの場合で7を挿入した結果は次のようになります。選択肢の中でこの結果と一致している木は「イ」です。