ソフトウェア開発技術者平成17年秋期 午前問9

問9

次の2分探索木からルートノード7を削除し,再び7を追加した2分探索木はどれか。
09.png/image-size:192×119
  • 09a.png/image-size:211×119
  • 09i.png/image-size:192×118
  • 09u.png/image-size:193×120
  • 09e.png/image-size:192×154

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

2分探索木は、2分木の各節にデータをもたせることで探索を行えるようにした木です。各節がもつデータは「その節から出る左部分木にあるどのデータよりも大きく、右部分木のどのデータよりも小さい」という条件があり、これを利用して効率的なデータ探索を可能にしています。
問題文の2分探索木からルートノード7を削除すると、2分探索木の性質を保つために7に最も近い6または8をルートノードとして再構成が行われます。
09_1.png/image-size:399×132
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.png/image-size:405×161
選択肢の中でこの結果と一致している木は「イ」です。
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop