Em uma árvore binária de busca balanceada com n nós, qual a complexidade temporal do algoritmo de busca em…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em uma árvore binária de busca balanceada com n nós, qual a complexidade temporal do algoritmo de busca em termos de n?
- A) A complexidade é O(n²) porque cada comparação requer múltiplos passos.
- B) A complexidade é O(n log n), pois a busca percorre n níveis logarítmicos.
- C) A complexidade é O(log n), pois a busca segue um só caminho.
- D) A complexidade é O(1), pois a busca é instantânea em árvores balanceadas.
- E) A complexidade é O(n), pois é preciso visitar todos os nós.
✅ Resposta correta: alternativa C
Resolução passo a passo
- Uma árvore binária de busca balanceada tem altura proporcional a log n, pois a cada nível a quantidade de nós dobra, e com n nós a altura é da ordem de log2 n.
- Na busca, em cada nó comparamos a chave procurada com o valor do nó e descemos somente para a subárvore esquerda ou direita, descartando metade da árvore a cada comparação. Logo, a busca segue um único caminho da raiz até uma folha, no pior caso.
- Como o número de comparações é proporcional à altura, a complexidade temporal é O(log n), no pior caso e em média.
- A alternativa A está errada, pois O(n²) não corresponde ao custo de percorrer um caminho com comparações constantes.
- A alternativa B está errada, pois a busca não percorre n níveis; percorre apenas os níveis do caminho, que são cerca de log n.
- A alternativa D está errada, pois O(1) só ocorreria se a chave estivesse sempre na raiz, o que não é garantido.
- A alternativa E está errada, pois visitar todos os nós é o que ocorre em uma busca em árvore não ordenada ou em uma varredura completa, não na busca em árvore binária de busca balanceada.
- Portanto, o gabarito oficial C está correto.
💡 Dica: Relacione o balanceamento da árvore à altura e ao caminho percorrido pela busca.
Alternativa por alternativa
O aluno imagina que cada comparação custa muitos passos e que o tempo cresce quadraticamente com o número de nós, confundindo a busca com operações de ordenação simples.
O aluno acredita que a busca percorre todos os níveis logarítmicos e multiplica isso por n, somando custos que não existem na busca, que descende apenas por um caminho.
Em uma árvore binária de busca balanceada, cada comparação elimina uma parte da árvore. Como sua altura cresce proporcionalmente a log n, a busca visita O(log n) nós.
O aluno supõe que, por estar balanceada, a árvore permite localizar a chave diretamente, sem percorrer caminho algum, confundindo balanceamento com acesso direto como em uma tabela hash.
O aluno pensa que é preciso examinar todos os nós para encontrar um valor, como em uma lista não ordenada, esquecendo que a propriedade de ordenação permite descartar metade da árvore a cada comparação.
Por que engana: Confundir a busca com uma visita a todos os nós e escolher O(n), sem considerar que, em uma árvore balanceada, ela segue apenas um caminho de altura logarítmica.
Raio-X da questão
Busca em árvore balanceada
avaliacao
Árvores binárias de busca · Notação Big O
Revise a relação entre a altura de uma árvore balanceada e a complexidade de busca.
Confundir a busca com uma visita a todos os nós e escolher O(n), sem considerar que, em uma árvore balanceada, ela segue apenas um caminho de altura logarítmica.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Um algoritmo de busca binária em uma lista ordenada de n elementos reduz o espaço de busca pela metade a cada passo…
- Um algoritmo percorre uma lista de n elementos e atualiza um dicionário/hashtable com a frequência de cada elemento em…
- Dado um vetor (array) não ordenado com n elementos, qual é a complexidade temporal, no pior caso, do algoritmo que…
- O que caracteriza um algoritmo de busca binária?
- Em um algoritmo, qual a vantagem de usar uma árvore binária para organizar dados?
- Para um algoritmo que percorre um vetor dados de tamanho N verificando cada elemento até achar um alvo, qual a…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog