データ構造 (全29問中26問目)

No.26

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

分類

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

正解

解説

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

Pagetop