Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FUNDATEC 2026
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg685512
Banca
FUNDATEC
Órgão
IFC-SC
Ano
2026
Nível
Superior
Cargo
Professor EBTT - Computação
Uma Árvore Binária de Pesquisa (ABP) organiza chaves de forma que, para cada nó, todos os valores na subárvore esquerda são menores e todos na subárvore direita são maiores. A Árvore AVL é uma ABP autoequilibrada que mantém, em cada nodo, a invariante de que as alturas das subárvores esquerda e direita diferem em, no máximo, 1. Nesse contexto, assinale a alternativa correta.
AUma ABP construída pela inserção de n elementos em ordem estritamente crescente mantém altura O(log n), pois a propriedade de busca binária distribui as chaves de forma equilibrada entre as subárvores.
BA operação de busca em uma AVL tem complexidade O(n) no pior caso, pois o rebalanceamento pode deslocar nodos de posição imprevisível durante a travessia.
CA inserção em uma AVL pode violar temporariamente a invariante de equilíbrio no ancestral mais baixo do nodo inserido; o desequilíbrio é corrigido por uma rotação simples (caso LL ou RR) ou uma rotação dupla (caso LR ou RL), restaurando a invariante e mantendo a altura garantida O(log n).
DO fator de balanceamento de um nó AVL é definido como a diferença entre o número total de nodos das subárvores esquerda e direita e deve ser igual a zero em todos os nodos da árvore.
EA remoção de um elemento em uma AVL nunca exige rotações, pois a substituição do nodo removido pelo seu sucessor in-order preserva automaticamente a invariante de balanceamento.
Revelar gabarito e comentário▾
GabaritoC — A inserção em uma AVL pode violar temporariamente a invariante de equilíbrio no ancestral mais baixo do nodo inserido; o desequilíbrio é corrigido por uma rotação simples (caso LL ou RR) ou uma rotação dupla (caso LR ou RL), restaurando a invariante e mantendo a altura garantida O(log n).
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”.
Árvore Binária de Pesquisa e Árvore AVL
Gabarito: letra C. A inserção em uma AVL pode violar temporariamente a invariante de equilíbrio no ancestral mais baixo do nó inserido, e o desequilíbrio é corrigido por rotação simples (casos LL ou RR) ou rotação dupla (casos LR ou RL), restaurando a invariante e mantendo a altura garantida O(log n). As demais alternativas contêm erros conceituais importantes.
Característica
Árvore Binária de Pesquisa (ABP)
Árvore AVL
Definição
Para cada nó, valores na subárvore esquerda são menores e na direita são maiores
ABP autoequilibrada que mantém, em cada nó, a diferença de altura entre subárvores ≤ 1
Altura (pior caso)
O(n) (ex.: inserção em ordem crescente)
O(log n) (garantida pelo balanceamento)
Busca (complexidade)
O(n) no pior caso
O(log n) no pior caso
Inserção
Sem rebalanceamento
Pode violar invariante; corrigida por rotação simples (LL/RR) ou dupla (LR/RL)
Fator de balanceamento
Não se aplica
Diferença entre alturas das subárvores; valores permitidos: -1, 0 ou 1
Remoção
Simples substituição
Pode exigir rotações para restaurar equilíbrio
Árvore AVL
1Propriedade
2ABP autoequilibrada
3Altura O(log n)
4Fator de balanceamento
5Altura direita − altura esquerda
6Valores: -1, 0 ou 1
7Inserção
8Pode violar invariante
9Corrige com rotações
10Simples (LL ou RR)
11Dupla (LR ou RL)
12Busca
13O(log n) no pior caso
14Sem rebalanceamento
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Afirma que uma ABP construída pela inserção de n elementos em ordem estritamente crescente mantém altura O(log n). Na realidade, quando as chaves são inseridas em ordem crescente, a árvore degenera em uma lista encadeada (todos os nós à direita), resultando em altura O(n). A propriedade de busca binária não garante equilíbrio; ela apenas organiza as chaves de forma que a subárvore esquerda seja menor e a direita maior, mas sem balanceamento a altura pode ser linear.
Alternativa B — ❌ Incorreta
Afirma que a busca em uma AVL tem complexidade O(n) no pior caso, supostamente porque o rebalanceamento desloca nós de forma imprevisível. Na verdade, a busca em uma AVL é idêntica à busca em uma ABP, e como a AVL é balanceada, sua altura é O(log n). Portanto, a busca tem complexidade O(log n) no pior caso, e não O(n). O rebalanceamento ocorre apenas durante inserções e remoções, não durante a busca.
Alternativa C — ✅ Correta ⟵ GABARITO
Exata descrição da inserção em uma árvore AVL. Após inserir um nó, o fator de balanceamento é atualizado subindo até a raiz; se um nó se torna desbalanceado (fator ±2), o desequilíbrio é corrigido com rotações: rotação simples à direita (LL) ou à esquerda (RR) se o filho estiver no mesmo sentido, ou rotação dupla (LR ou RL) se o filho estiver no sentido oposto. Após a rotação, a invariante é restaurada e a altura permanece O(log n).
Alternativa D — ❌ Incorreta
Define o fator de balanceamento como a diferença entre o número total de nós das subárvores esquerda e direita, devendo ser zero em todos os nós. O fator de balanceamento é a diferença entre as alturas das subárvores (altura da direita menos altura da esquerda), e seus valores permitidos são -1, 0 ou 1, não necessariamente zero. A definição correta está em.
Alternativa E — ❌ Incorreta
Afirma que a remoção em uma AVL nunca exige rotações, pois a substituição pelo sucessor in-order preserva o balanceamento. Na realidade, a remoção pode causar desbalanceamento, exigindo rotações para reequilibrar a árvore, assim como na inserção. A substituição pelo sucessor ou predecessor é apenas uma técnica para remover nós com dois filhos, mas o reequilíbrio posterior é necessário.