NO IMAGE

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

【問題】 すべての葉が同じ深さであり、かつ、葉以外のすべての節点が二つの子を持つ要素数nの完全2分木がある。どの部分木をとっても左の...