オリジナル模擬試験3 問5

問5

次の2分探索木からルートノード7を削除し,再び7を追加した2分探索木はどれか。
05.gif/image-size:186×116
  • 05a.gif/image-size:205×115
  • 05i.gif/image-size:186×115
  • 05u.gif/image-size:187×116
  • 05e.gif/image-size:187×150
  • [出典]
  • ソフトウェア開発技術者 H17秋期 問9

分類

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

正解

解説

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

Pagetop