データ構造(全39問中30問目)

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

出典:平成19年春期 問 9

  • log2n
  • nlog2n
  • n
  • n2
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
解説
設問の記述にある「完全2分木」と「どの部分木をとっても左の子孫は親よりも小さく,右の子孫は親よりも大きいという関係が保たれている」から、この木は次のような構造を持つ完全2分探索木であるとわかります。
09.gif
2分探索木では節点の値と探索値を比較し、探索値が存在する範囲を1/2ずつに狭めながら要素の探索を行います。要素数が2倍になれば探索回数が1回、4倍では2回増え、要素数が半分になれば1回減ることになるので比較回数のオーダーは「log2n」になります。

※log2nは、n=2pとなる指数pの値です。例.log28=3、log2256=8

Pagetop