空の2分探索木に、すでに昇順に整列された n 個のデータを先頭から順に挿入して木を作った。この木で値を探索するときの最悪時間計算量はどれか。

解説

正解は「$O(n)$」です。昇順のデータを順に挿入すると、新しい値は常にそれまでの最大値より大きいので、毎回右の子として追加されます。その結果、木は右にだけ伸びた一本の鎖のような形になり、高さが n−1 となります。最も深い節点の探索では根から全節点をたどる必要があるため $O(n)$ で、線形リストと同じ効率になります。「$O(\log n)$」は、木がバランスしていて高さが約 ${\log }_{2}n$ の場合の計算量です。AVL木や赤黒木などの平衡2分探索木は、回転操作で高さをこの程度に保ちます。「$O(1)$」はハッシュ表の平均的な探索時間です。「$O(n\log n)$」は、バランスのとれた木に n 個のデータを挿入する全体の時間で、1回の探索の時間ではありません。