問題 No.3967
データ構造として2分木を用いる場合において、根から各葉までの経路長のうち最大の値が最小となるように構築された、左右の部分木の高さの差が1以下である2分探索木を構築することになった。要素数が7の完全2分木の状態にあるとき、中間順巡回（インオーダー）で得られるキーの並びが昇順であるならば、この2分木に対する特定のキーの探索における最大比較回数（根から対象ノードに到達するまでのエッジ数の最大値に1を加えたもの）はいくつになるか。
【正解の解説】
3
これは電話帳をめくるときに、まず真ん中を開いて目的の名前が前か後ろかを探し、それを繰り返して目的のページにたどり着くようなものです。要素数7個の完全2分木はちょうど3階建てのビル（高さが3）のような構造になり、一番上の1階から一番奥の部屋まで探すとしても、階段を降りる回数を含めて最大で3回の比較で必ず見つかります。
スポンサーリンク
【その他の選択肢の解説】
2
高さが2の2分木が収容できる最大の要素数は3個（根に1個、その下に2個）までです。したがって、7個のデータをすべてきれいに収納して検索するには高さがどうしても3必要になるため、2回という数字は要素の数と木の構造のルール上から見て小さすぎて不正解となります。
4
問題文では左右の部分木の高さの差が1以下であるバランスの取れた完全2分木を指定しています。もし木が片側にだけダラダラと伸びて一本道のようになってしまうと4回以上の比較が必要になりますが、今回はきれいにバランスよく整えられているため、そこまで無駄に深くはなりません。
7
要素数が7個だからといって、必ずしも7回すべてを比較しなければならないわけではありません。2分探索木は賢く枝分かれして不要なデータを一瞬で除外していく仕組みなので、すべてのデータを順番になめるリニアサーチと混同して要素数をそのまま回数にしてしまうのは典型的な勘違いです。