Árvore AVL

Prévia do material em texto

Árvore AVL 
O que caracteriza uma arvore AVL?
a) E uma arvore binaria de busca sem restricoes de altura
b) E uma arvore binaria de busca balanceada, onde a diferenca de altura entre subarvores nao e
maior que 1
c) E uma arvore que armazena apenas numeros pares
d) E uma arvore usada apenas para grafos
Resposta explicativa: Uma arvore AVL e uma arvore binaria de busca balanceada. O
balanceamento garante que, para cada no, a diferenca entre a altura da subarvore esquerda e da
direita seja no maximo 1, garantindo operacoes eficientes.
Qual e o principal objetivo do balanceamento em uma arvore AVL?
a) Aumentar o numero de nos
b) Garantir que operacoes de busca, insercao e remocao sejam rapidas, com complexidade O(log
n)
c) Tornar a arvore visualmente simetrica
d) Evitar que a arvore tenha folhas
Resposta explicativa: O balanceamento mantem a altura da arvore proxima de logaritmica em
relacao ao numero de nos, garantindo que operacoes de busca, insercao e remocao permanecam
eficientes.
Qual e o fator de balanceamento de um no em uma arvore AVL?
a) A soma dos valores da subarvore esquerda com a direita
b) A diferenca entre as alturas da subarvore direita e esquerda
c) O numero de folhas abaixo do no
d) O valor armazenado no no multiplicado pela altura
Resposta explicativa: O fator de balanceamento e calculado subtraindo a altura da subarvore
esquerda da altura da subarvore direita. Valores possiveis sao -1, 0 ou 1 para uma arvore AVL
balanceada.
O que ocorre quando o fator de balanceamento de um no em uma AVL e maior que 1 ou menor
que -1?
a) Nada, a arvore permanece balanceada
b) A arvore precisa realizar rotacoes para restaurar o balanceamento
c) O no e deletado automaticamente
d) O no passa a armazenar mais dados
Resposta explicativa: Quando o fator de balanceamento ultrapassa 1 ou -1, a arvore esta
desbalanceada e deve realizar rotacoes (simples ou duplas) para restaurar o balanceamento e
manter eficiencia nas operacoes.
Qual e o tipo de rotacao usada para corrigir um desbalanceamento causado por insercao na
subarvore esquerda da subarvore esquerda?
a) Rotacao simples a direita
b) Rotacao simples a esquerda
c) Rotacao dupla esquerda-direita
d) Rotacao dupla direita-esquerda
Resposta explicativa: Este e o caso do desequilibrio esquerda-esquerda (LL), que e corrigido com
uma rotacao simples a direita no no desbalanceado.
Qual rotacao e utilizada para corrigir o desequilibrio direita-direita (RR) em uma arvore AVL?
a) Rotacao simples a esquerda
b) Rotacao simples a direita
c) Rotacao dupla esquerda-direita
d) Rotacao dupla direita-esquerda
Resposta explicativa: Para o desequilibrio RR, onde a insercao ocorreu na subarvore direita da
subarvore direita, a correcao e feita com uma rotacao simples a esquerda no no desbalanceado.
Qual e a sequencia correta de rotacoes para corrigir o desequilibrio esquerda-direita (LR)?
a) Rotacao simples a direita seguida de rotacao simples a esquerda
b) Rotacao simples a esquerda seguida de rotacao simples a direita
c) Dupla rotacao direita-esquerda
d) Dupla rotacao esquerda-direita
Resposta explicativa: Para desequilibrio LR, primeiro realiza-se uma rotacao simples a esquerda na
subarvore esquerda, seguida de uma rotacao simples a direita no no desbalanceado, restaurando o
balanceamento.
Para o desequilibrio direita-esquerda (RL), quais rotacoes sao aplicadas?
a) Rotacao simples a esquerda seguida de rotacao simples a direita
b) Rotacao simples a direita seguida de rotacao simples a esquerda
c) Rotacao simples a direita duas vezes
d) Rotacao simples a esquerda duas vezes
Resposta explicativa: Para o caso RL, aplica-se primeiro uma rotacao simples a direita na
subarvore direita, seguida de uma rotacao simples a esquerda no no desbalanceado, equilibrando a
arvore.
Qual e a complexidade de tempo de busca em uma arvore AVL com n nos?
a) O(n)
b) O(log n)
c) O(n^2)
d) O(1)
Resposta explicativa: Como a arvore AVL e balanceada, a altura maxima e aproximadamente
log2(n), tornando a complexidade de busca O(log n). Isso garante eficiencia mesmo em arvores
grandes.
Como a insercao de um novo no afeta o fator de balanceamento em uma arvore AVL?
a) Sempre mantem o fator igual a zero
b) Pode causar desbalanceamento nos ancestrais do no inserido
c) Nao afeta o balanceamento
d) Elimina a necessidade de rotacoes futuras
Resposta explicativa: A insercao pode alterar as alturas dos nos ancestrais, provocando fatores de
balanceamento fora do intervalo [-1,1]. Se isso ocorrer, rotacoes sao aplicadas para restaurar o
balanceamento.
Em uma arvore AVL, qual e a relacao entre altura h e numero maximo de nos n?
a) n = h
b) n 2^(h+1) - 1
c) n h2
d) n = log(h)
Resposta explicativa: O numero maximo de nos em uma arvore AVL de altura h e n 2^(h+1) - 1,
devido a restricao de balanceamento que mantem a altura proxima de logaritmica em relacao ao
numero de nos.
Qual e a relacao entre altura e numero minimo de nos em uma arvore AVL de altura h?
a) n F(h+2) - 1, onde F e a sequencia de Fibonacci
b) n = h2
c) n h
d) n = 2^h
Resposta explicativa: O numero minimo de nos em uma AVL de altura h segue a relacao n F(h+2) -
1, sendo F(h) o h-esimo termo da sequencia de Fibonacci, demonstrando que mesmo arvores
esparsas ainda tem altura limitada.
Ao remover um no de uma arvore AVL, qual acao e necessaria caso o balanceamento seja
afetado?
a) Nenhuma acao e necessaria
b) Aplicar rotacoes nos nos ancestrais ate restaurar o equilibrio
c) Recriar toda a arvore
d) Apenas atualizar os valores dos nos
Resposta explicativa: A remocao pode desbalancear a arvore, e e necessario atualizar fatores de
balanceamento e aplicar rotacoes apropriadas nos nos afetados para restaurar a propriedade AVL.
Por que arvores AVL sao preferidas em comparacao com arvores binarias de busca simples em
aplicacoes que exigem muitas buscas?
a) Porque tem maior numero de folhas
b) Porque garantem busca, insercao e remocao em O(log n)
c) Porque nao usam memoria
d) Porque sao mais faceis de desenhar
Resposta explicativa: A vantagem das arvores AVL esta no balanceamento, que mantem a altura
proxima de log n, garantindo operacoes eficientes mesmo apos multiplas insercoes e remocoes, ao
contrario de arvores binarias de busca simples que podem degenerar em lista.
Qual e a diferenca entre uma arvore AVL e uma arvore Rubro-Negra?
a) AVL nao e balanceada, enquanto Rubro-Negra e
b) AVL mantem balanceamento estrito com altura minima, enquanto Rubro-Negra permite
desequilibrios leves para simplificar insercoes e remocoes
c) Rubro-Negra armazena apenas numeros pares
d) Nao ha diferenca
Resposta explicativa: AVL mantem balanceamento estrito, garantindo altura minima e eficiencia
maxima em buscas, mas exige mais rotacoes. Arvores Rubro-Negras permitem desequilibrios
leves, facilitando insercoes e remocoes com menos rotacoes.
Qual e o fator determinante para escolher o tipo de rotacao a ser aplicada em uma AVL?
a) Altura da subarvore esquerda apenas
b) Fator de balanceamento e posicao do no inserido ou removido
c) Valor do no
d) Numero de folhas
Resposta explicativa: A rotacao depende do fator de balanceamento do no desbalanceado e da
posicao do no recem-inserido ou removido, determinando se a rotacao sera simples ou dupla.
Em que cenario a rotacao dupla esquerda-direita e necessaria?
a) Quando ocorre desequilibrio esquerda-esquerda
b) Quando ocorre desequilibrio esquerda-direita
c) Quando ocorre desequilibrio direita-direita
d) Quando ocorre desequilibrio direita-esquerda
Resposta explicativa: Desequilibrio LR (esquerda-direita) ocorre quando um no e inserido na
subarvore direita da subarvore esquerda do no desbalanceado. Isso requer rotacao dupla
esquerda-direita para restaurar o balanceamento.
Qual e a vantagem de utilizar uma arvore AVL em memoria limitada?
a) Ocupa menos memoria que uma lista
b) Mantem altura minima, reduzindo percursos desnecessarios e otimizando acesso
c) Nao requer ponteiros
d) Naopermite remocao de nos
Resposta explicativa: Mantendo a altura minima, a AVL reduz o numero de comparacoes em busca,
insercao e remocao, economizando processamento e memoria em sistemas limitados.
Qual propriedade e obrigatoria em todas as arvores AVL?
a) Todos os nos tem dois filhos
b) O fator de balanceamento de cada no e -1, 0 ou 1
c) Todos os nos armazenam numeros consecutivos
d) Todas as folhas tem a mesma profundidade
Resposta explicativa: O fator de balanceamento restrito a -1, 0 ou 1 e o que define a propriedade
AVL, garantindo que a arvore permaneca balanceada.
Qual e a diferenca entre uma rotacao simples e uma rotacao dupla em arvores AVL?
a) Simples altera apenas um no; dupla altera dois nos
b) Simples resolve desequilibrios LL ou RR; dupla resolve desequilibrios LR ou RL
c) Simples aumenta altura; dupla diminui altura
d) Nao existe diferenca
Resposta explicativa: Rotacoes simples corrigem desequilibrios de um lado apenas (LL ou RR).
Rotacoes duplas sao compostas de duas rotacoes simples aplicadas em sequencia para resolver
desequilibrios cruzados (LR ou RL).
Em qual operacao de uma arvore AVL e mais frequente a necessidade de rotacoes?
a) Impressao da arvore
b) Insercao e remocao de nos
c) Consulta de valor
d) Contagem de folhas
Resposta explicativa: Insercoes e remocoes alteram a altura de subarvores e podem desbalancear
a arvore, tornando rotacoes necessarias para manter a propriedade AVL.
Qual e a vantagem de manter uma arvore AVL em uma aplicacao de dicionario de palavras?
a) Permite armazenamento de palavras duplicadas
b) Garante busca rapida, mesmo apos muitas insercoes e delecoes
c) Reduz o tamanho das palavras
d) Evita a necessidade de memoria RAM
Resposta explicativa: Em um dicionario, buscas frequentes sao comuns. O balanceamento da AVL
garante operacoes O(log n), mantendo o acesso eficiente independentemente de alteracoes na
estrutura.
Qual e a consequencia de nao balancear uma arvore binaria de busca?
a) Operacoes podem se tornar O(log n)
b) Operacoes podem degenerar para O(n), parecendo uma lista encadeada
c) A arvore desaparece
d) A arvore se torna uma AVL automaticamente
Resposta explicativa: Sem balanceamento, a arvore pode se tornar desequilibrada, aumentando a
altura e degradando a eficiencia de busca, insercao e remocao, atingindo complexidade linear.
Qual e o criterio usado para decidir a direcao da rotacao em uma arvore AVL?
a) Valor do no desbalanceado
b) Comparacao do fator de balanceamento e direcao do novo no inserido ou removido
c) Numero de folhas da arvore
d) Profundidade da arvore
Resposta explicativa: O criterio envolve o fator de balanceamento do no desbalanceado e a posicao
do no que causou o desequilibrio, determinando se a rotacao sera a esquerda, a direita ou dupla.
Qual e o efeito da rotacao simples a direita em uma arvore AVL?
a) Troca os valores de dois nos quaisquer
b) Eleva a subarvore esquerda e reduz altura da subarvore direita do no desbalanceado
c) Remove o no desbalanceado
d) Duplica a subarvore direita
Resposta explicativa: A rotacao simples a direita corrige desequilibrios LL, promovendo o filho
esquerdo do no desbalanceado e ajustando as alturas das subarvores para restaurar o
balanceamento.
Como uma arvore AVL se comporta apos multiplas insercoes em ordem crescente?
a) Torna-se automaticamente uma lista encadeada
b) Executa rotacoes para manter a altura minima e O(log n) nas operacoes
c) Desbalanceia permanentemente
d) Nao permite insercoes adicionais
Resposta explicativa: Sem balanceamento, insercoes em ordem crescente gerariam uma lista. A
AVL aplica rotacoes para manter a arvore balanceada, preservando complexidade O(log n).
Em arvores AVL, qual operacao e mais custosa em termos de atualizacao do fator de
balanceamento?
a) Busca de um valor
b) Insercao e remocao, pois pode afetar todos os ancestrais ate a raiz
c) Impressao em ordem
d) Contagem de nos
Resposta explicativa: Insercoes e remocoes podem alterar alturas de multiplos nos ancestrais,
exigindo atualizacao de fatores de balanceamento e possivelmente rotacoes, enquanto buscas nao
alteram a estrutura.
Qual e a altura maxima de uma arvore AVL com 15 nos?
a) 3
b) 4
c) 15
d) 7
Resposta explicativa: Para 15 nos, a altura maxima h segue a formula da sequencia de Fibonacci
aproximada. A altura maxima de uma AVL de 15 nos e 5, garantindo que a arvore permaneca
balanceada.
Por que arvores AVL nao sao sempre usadas em bancos de dados?
a) Porque nao permitem duplicatas
b) Porque outras estruturas, como arvores B ou B+, podem ser mais eficientes em memoria
secundaria
c) Porque AVL nao suporta chaves inteiras
d) Porque nao podem ser balanceadas
Resposta explicativa: Em bancos de dados, AVL pode exigir muitas rotacoes e nao otimiza acesso
em disco. Arvores B ou B+ sao mais adequadas para armazenamento secundario e operacoes em
blocos grandes.
Em uma AVL, se uma rotacao simples a esquerda e aplicada, o que acontece com o fator de
balanceamento do no que foi elevado?
a) Permanece igual
b) E recalculado com base nas alturas atualizadas das subarvores
c) Torna-se 0 automaticamente
d) Nao precisa de atualizacao
Resposta explicativa: Apos a rotacao, os fatores de balanceamento dos nos afetados devem ser
recalculados de acordo com as novas alturas das subarvores para garantir que a arvore continue
balanceada.
Qual e a diferenca fundamental entre uma arvore AVL e uma arvore binaria de busca nao
balanceada ao realizar 1000 insercoes aleatorias?
a) AVL pode degenerar, enquanto binaria permanece balanceada
b) AVL mantem altura logaritmica, enquanto a arvore binaria nao balanceada pode crescer
linearmente
c) AVL nao permite remocao
d) Nao ha diferenca pratica
Resposta explicativa: A AVL mantem altura O(log n) atraves de rotacoes, garantindo eficiencia
mesmo com muitas insercoes, enquanto a arvore binaria de busca pode se desbalancear e ter
operacoes O(n).
Por que o fator de balanceamento e limitado a -1, 0 ou 1 em arvores AVL?
a) Para simplificar a codificacao
b) Para garantir que a arvore permaneca aproximadamente balanceada
c) Para evitar insercao de novos nos
d) Para armazenar apenas numeros pares
Resposta explicativa: Limitar o fator de balanceamento garante que nenhuma subarvore seja
demasiadamente mais alta que a outra, preservando altura minima e eficiencia nas operacoes.
Qual e a consequencia de uma rotacao dupla aplicada incorretamente em uma arvore AVL?
a) A arvore pode permanecer balanceada
b) A arvore pode se desbalancear, comprometendo eficiencia de busca
c) O no removido e recuperado
d) A arvore vira uma lista ligada
Resposta explicativa: Rotacoes aplicadas incorretamente podem criar desbalanceamento adicional,
aumentando a altura da arvore e degradando complexidade das operacoes de O(log n) para O(n).
Em arvores AVL, por que e importante atualizar os fatores de balanceamento do no pai apos uma
rotacao?
a) Porque o pai pode ter ficado desbalanceado
b) Para duplicar os valores da subarvore
c) Para deletar o no inserido
d) Para transformar a arvore em lista
Resposta explicativa: A rotacao altera alturas das subarvores, podendo afetar o fator de
balanceamento do no pai, que deve ser atualizado para manter a propriedade AVL.
Qual e a complexidade de tempo para inserir n elementos em uma arvore AVL ja vazia?
a) O(n2)
b) O(n log n)
c) O(n)
d) O(log n)
Resposta explicativa: Cada insercao em uma AVL leva O(log n), entao inserir n elementos tem
complexidade O(n log n), considerando o balanceamento e rotacoes necessarias.
Em uma AVL, qual operacao garante que a altura da arvore nao ultrapasse 1,44*log2(n+2) - 0,328
aproximadamente?
a) Insercao sem rotacao
b) Insercao e remocao com rotacoes para manter balanceamento
c) Apenas remocao
d) Impressao em ordem
Resposta explicativa: Manter rotacoes apos insercao ou remocao garante que a altura da arvore
permaneca limitada, garantindo eficiencia O(log n) para todas as operacoes.
Por que arvores AVL sao chamadasde arvores balanceadas?
a) Porque possuem igual numero de nos em cada lado
b) Porque mantem diferenca maxima