平成17年秋期試験問題 午前問9

次の2分探索木からルートノード7を削除し,再び7を追加した2分探索木はどれか。
09.gif

  • 09a.gif
  • 09i.gif
  • 09u.gif
  • 09e.gif
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
解説
2分探索木は、2分木の各節にデータをもたせることで探索を行えるようにした木です。各節がもつデータは「その節から出る左部分木にあるどのデータよりも大きく、右部分木のどのデータよりも小さい」という条件があり、これを利用して効率的なデータ探索を可能にしています。
問題文の2分探索木からルートノード7を削除すると、2分探索木の性質を保つために7に最も近い6または8をルートノードとして再構成が行われます。
09_1.gif
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を挿入した結果は次のようになります。
09_2.gif
選択肢の中でこの結果と一致している木は「イ」です。

Pagetop