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

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

 ア  log2n  イ  n log2n  ウ  n  エ  n2


答え ア


解説
完全2分木の探索では、要素の数が2m -1個の時、最大m 回の比較で探索が完了する。

図の例では、要素の数は15(=24-1)個のとき、比較回数は根、1段目、2段目、3段目の4回の比較で完了する。
この式を、変形すると比較回数のオーダはlog2n (ア)になる。


キーワード
・2分木

キーワードの解説
  • 2分木
    2分木とは下図のような図である。

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

もっと、「2分木」について調べてみよう。

戻る 一覧へ 次へ