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

すべての葉が同じ深さであり、かつ、葉以外のすべての節点が二つの子を持つ要素数nの完全2分岐がある。
どの部分木をとっても左の子孫は親よりも小さく、右の子孫は親よりも大きいという関係が保たれている。
2分木で探索する場合、ある要素を探索するときの最大比較回数のオーダはどれか。

【キーワード】
・2分木

• 2分木
  2分木とは下図のような図である。
  
  ○が節を表し、一番上の節を根、下に線で結ばれた節を子、上に節で結ばれた節を親と呼び、子のない節を葉と呼ぶ。
  親と子には関係があり、問題では左の子は親より小さく、右の子は親より大きくなっている。
  2分木の探索では根から比較を行い、根より大きかったら右の子、小さかったr左の子と移動しながら、等しい節が見つかるまで、これを繰り返す。
  等しい節が見つからなかった時は、葉の節までいって、等しい要素が見つからなかったことを返す。

戻る 一覧へ 次へ