すべての葉が同じ深さであり、かつ、葉以外のすべての節点が二つの子を持つ要素数nの完全2分岐がある。 どの部分木をとっても左の子孫は親よりも小さく、右の子孫は親よりも大きいという関係が保たれている。 2分木で探索する場合、ある要素を探索するときの最大比較回数のオーダはどれか。
答え ア
【解説】 完全2分木の探索では、要素の数が2m -1個の時、最大m 回の比較で探索が完了する。 図の例では、要素の数は15(=24-1)個のとき、比較回数は根、1段目、2段目、3段目の4回の比較で完了する。 この式を、変形すると比較回数のオーダはlog2n (ア)になる。
【キーワード】 ・2分木
戻る 一覧へ 次へ