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
- Em um projeto de monitoramento de rios, uma boia computacional organiza leituras de sensores antes de enviá-las por…
- Uma biblioteca escolar recebeu caixas de livros doados para uma feira de troca. Para registrar os exemplares, a equipe…
- Um centro cultural público oferece inscrições on-line para atividades com critérios variados. Na oficina de teatro…
- Uma escola está testando dois protótipos de aplicativo para que estudantes consultem mudanças de sala, horários e…
- Uma secretaria municipal de educação está digitalizando pedidos de transporte escolar e de atendimento em contraturno…
- — O cartaz não pode sair duas vezes, pois a feira começa em uma hora — alertou a coordenadora do centro cultural. No…
🔎 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