GabaritoD — O(log n).
Gabarito: letra D. A busca em uma árvore binária balanceada, como a árvore AVL, tem complexidade O(log n) no pior caso, pois a altura da árvore é mantida proporcional a log n, onde n é o número de nós. Essa é uma propriedade fundamental de estruturas balanceadas.
A questão testa o conhecimento sobre a notação Big-O e o comportamento de árvores balanceadas. Vamos analisar cada alternativa:
O(1) é a complexidade de busca em uma tabela hash (acesso direto), não em uma árvore. Em uma árvore balanceada, o número de comparações cresce com o logaritmo de n.
O(n) é o pior caso de uma árvore binária de busca não balanceada (degenerada em lista). Em uma árvore balanceada, a altura é limitada a O(log n).
O(n log n) é típico de algoritmos de ordenação eficientes (mergesort, heapsort), não de busca em árvores balanceadas.
O(log n) é a complexidade correta para busca, inserção e remoção em árvores binárias balanceadas, como AVL ou Rubro-Negra. É a resposta esperada.
O(log n²) é uma notação não padrão; matematicamente equivale a O(2 log n) = O(log n), mas a forma usual é O(log n). A banca considera essa alternativa incorreta por não ser a notação exata (provavelmente intencionando O(log n) apenas).
Conclusão: A complexidade de busca em árvore binária balanceada é O(log n), conforme alternativa D.
Link permanente: /questoes/qg615407