Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — JVL Concursos 2025
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg572223
Banca
JVL Concursos
Órgão
Prefeitura de Regeneração - PI
Ano
2025
Nível
Superior
Cargo
Professor de Computação
Assinale a alternativa que relaciona corretamente limites de altura e impacto em consultas.
AAVL apresenta cota de altura assintoticamente menor que rubro-negra, o que tende a reduzir comparações em busca no pior caso, com custo de reequilíbrios mais frequentes em atualizações.
BRubro-negra mantém altura igual à de AVL em todas as inserções, o que elimina rotações em qualquer sequência de chaves.
CÁrvores não balanceadas mantêm altura próxima de log n em inserções crescentes, o que iguala o custo de busca ao de AVL em média.
DAVL garante altura linear por projeto, o que favorece atualizações longas e buscas constantes em todos os casos.
Revelar gabarito e comentário▾
GabaritoA — AVL apresenta cota de altura assintoticamente menor que rubro-negra, o que tende a reduzir comparações em busca no pior caso, com custo de reequilíbrios mais frequentes em atualizações.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Árvores Balanceadas: AVL × Rubro-Negra
Gabarito: letra A. A afirmação está correta ao comparar AVL e rubro-negra: a AVL possui cota de altura assintoticamente menor (~1.44 log n contra ~2 log n da rubro-negra), o que reduz comparações na busca, mas exige reequilíbrios mais frequentes (rotações) em inserções/remoções. É a relação clássica entre as duas estruturas.
A banca testa o conhecimento das características fundamentais das árvores balanceadas, especialmente o trade-off entre altura (impacto na busca) e custo de reequilíbrio.
Alternativa A — ✅ Correta ⟵ GABARITO
A AVL impõe um balanceamento mais rígido (diferença de altura ≤ 1 entre subárvores), resultando em altura máxima ≈ 1,44 log₂ n, enquanto a rubro-negra permite altura até 2 log₂ n. Isso diminui o número de comparações na busca no pior caso, porém a manutenção do equilíbrio exige rotações com maior frequência — exatamente o que a alternativa descreve.
Alternativa B — ❌ Incorreta
Afirma que a rubro-negra mantém altura igual à AVL em todas as inserções, eliminando rotações. Isso é falso: as duas estruturas têm diferentes critérios de balanceamento; a rubro-negra é menos estrita, portanto sua altura é maior no pior caso. Além disso, rotações sempre podem ser necessárias na rubro-negra (embora em número limitado, O(1) por operação).
Alternativa C — ❌ Incorreta
Diz que árvores não balanceadas mantêm altura próxima de log n em inserções crescentes. Na verdade, inserções em ordem crescente em uma árvore binária de busca simples (sem balanceamento) geram uma árvore degenerada em lista encadeada, com altura O(n), não O(log n). Portanto, o custo de busca não se equipara ao da AVL.
Alternativa D — ❌ Incorreta
Afirma que a AVL garante altura linear por projeto. Isso é o oposto da verdade: a AVL assegura altura O(log n) (logarítmica), não linear. A altura linear favoreceria atualizações longas, mas penalizaria severamente as buscas, o que contradiz o propósito da estrutura.
PEGA ESSA DICA!
Para diferenciar AVL de rubro-negra, lembre-se: AVL é mais balanceada (menor altura) → buscas mais rápidas, porém mais rotações. Rubro-negra é menos balanceada (maior altura) → buscas um pouco mais lentas, mas menos rotações. Nos concursos, perguntas sobre trade-off entre essas duas são frequentes.