Sob quais condições o tempo de busca numa árvore binária se torna superior ao logarítmico?

O tempo de pesquisa numa árvore binária é normalmente logarítmico (O(log n)) desde que a árvore esteja balanceada, ou seja, que a altura da árvore seja proporcional ao logaritmo do número de nós. No entanto, se a árvore não estiver balanceada e se degenerar numa estrutura semelhante a uma lista ligada (por exemplo, todos os nós tendo apenas um filho), a altura da árvore torna-se linear (O(n)). Nesse caso, o tempo de pesquisa deteriora-se para linear, superando o tempo logarítmico.

Exemplo: se ao inserir sequencialmente dados ordenados numa árvore binária de pesquisa sem aplicar balanceamento, a árvore transformará-se numa cadeia, e a pesquisa funcionará em O(n).