分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：データ構造

設問の記述にある「完全2分木」と「どの部分木をとっても左の子孫は親よりも小さく，右の子孫は親よりも大きいという関係が保たれている」から、この木は次のような構造を持つ完全2分探索木であるとわかります。2分探索木では節点の値と探索値を比較し、探索値が存在する範囲を1／2ずつに狭めながら要素の探索を行います。要素数が2倍になれば探索回数が1回、4倍では2回増え、要素数が半分になれば1回減ることになるので比較回数のオーダーは「log₂n」になります。

※log₂nは、n＝2^pとなる指数pの値です。例.log₂8＝3、log₂256＝8