Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — Instituto Consulplan 2022

Complexidade de busca em árvores binárias de busca

Gabarito: letra A. A complexidade de busca em uma árvore binária de busca (ABB) no pior caso é O(n) — e, nesse caso, o número de comparações é igual à altura da árvore. Em uma ABB degenerada (que se comporta como uma lista encadeada), a altura é exatamente n, então O(n) = altura. A banca explora o fato de que a operação de busca percorre um caminho da raiz até a folha, e o comprimento desse caminho é a altura.

A complexidade O(n) indica que o tempo de execução cresce linearmente com o tamanho da entrada. Em uma árvore, o número de comparações realizadas na busca é, no pior caso, igual à altura, não ao número total de elementos (pois a busca não visita todos os nós). Por isso, a alternativa correta é a letra A.

Alternativa A — ✅ Correta ⟵ GABARITO

A altura de uma árvore binária de busca é a distância máxima entre a raiz e uma folha. No pior caso (árvore degenerada, em que cada nó tem um único filho), a altura é igual ao número de elementos n, e a busca percorre todos os n nós, resultando em O(n). Assim, a complexidade da busca é diretamente proporcional à altura. A definição formal: a altura determina o número de passos da busca, e no pior caso O(n) = altura.

Alternativa B — ❌ Incorreta

O valor do elemento na raiz não influencia a complexidade da busca. A raiz pode conter qualquer valor, e isso não altera o número de comparações realizadas. A complexidade depende apenas da estrutura (altura) e do número de elementos, não do valor armazenado.

Alternativa C — ❌ Incorreta

Embora O(n) use o n de número de elementos, a complexidade não é igual ao número de elementos. A busca não percorre todos os nós — ela segue um único caminho da raiz até a folha. Em uma árvore balanceada, a altura é log n, e o número de visitas é log n, não n. Apenas no caso particular da árvore degenerada altura = n, mas ainda assim a grandeza que rege a complexidade é a altura, não o total de elementos. A alternativa confunde o significado do parâmetro n com a métrica de desempenho real.

Alternativa D — ❌ Incorreta

Metade do número de elementos (n/2) não tem relação com a complexidade de busca em árvores binárias. O tempo de busca não é uma fração constante do número de elementos, mas depende da altura. Em nenhum caso a complexidade é O(n/2), pois constantes são abstraídas na notação O.