平衡化されていない二分探索木に、すでに昇順にソートされたn個の値を順番に挿入した場合、その後の探索の最悪計算量はどれですか。

昇順のデータを順に挿入すると、各要素は常に直前の要素の右の子になり、木が一本の連なり（連結リストのような形）に退化します。その結果、木の高さはn-1となり、探索では最悪すべてのノードをたどる必要があるためO(n)になります。AVL木や赤黒木のような自己平衡二分探索木は、挿入時に回転操作で高さを保ち、最悪でもO(log n)を保証します。