【問題】
すべての葉が同じ深さであり、かつ、葉以外のすべての節点が二つの子を持つ要素数ｎの完全2分木がある。どの部分木をとっても左の子孫は親より小さく、右の子孫は親より大きいという関係が保たれている。2分木で探索する場合、ある要素を探索するときの最大比較回数のオーダはどれか。
ア．log2n
イ．nlog2n
ウ．n
エ．n2
【解答】
完全2分木であって、かつ左の子孫は親より小さく、右の子孫は親より大きいということは、１回の探索で対象の数を半数にすることが出来る、ということを意味する。
５
３ ７
１ ４ ６ ８
たとえば４を検索する場合、最初の選択で左の３に移動するが、その時点で６，７，８を捨てることに成功している。
とすると、要素数が2の何乗になるかを考えれば、答えに辿りつくかが分かるようになるから、
2x = n
という式が成立することになる。
とすると、xに着目した場合、
log22x = log2n
x・log22 = log2n
x・1 = log2n
x = log2n
となる。よって、解答はアとなる。
この問題は、数式を理解していなくても、昇順または降順に値が並んでいる場合は、2分探索が可能→１回の検索で値を半分に減らすことが出来る、という前知識と、値を半分に減らすことの出来るオーダはlog2nで表すことが出来る、という知識があれば、そのまま答えまでたどり着くことが出来る。