データ構造 (全40問中31問目)
No.31
すべての葉が同じ深さであり，かつ，葉以外のすべての節点が二つの子を持つ要素数nの完全2分木がある。どの部分木をとっても左の子孫は親よりも小さく，右の子孫は親よりも大きいという関係が保たれている。2分木で探索する場合，ある要素を探索するときの最大比較回数のオーダーはどれか。
出典：平成19年春期 問9
- log2n
- nlog2n
- n
- n2
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
ア
解説
設問の記述にある「完全2分木」と「どの部分木をとっても左の子孫は親よりも小さく，右の子孫は親よりも大きいという関係が保たれている」から、この木は次のような構造を持つ完全2分探索木であるとわかります。
2分探索木では節点の値と探索値を比較し、探索値が存在する範囲を1／2ずつに狭めながら要素の探索を行います。要素数が2倍になれば探索回数が1回、4倍では2回増え、要素数が半分になれば1回減ることになるので比較回数のオーダーは「log2n」になります。
※log2nは、n＝2pとなる指数pの値です。例.log28＝3、log2256＝8
※log2nは、n＝2pとなる指数pの値です。例.log28＝3、log2256＝8