Árvore balanceada

Prévia do material em texto

Árvore balanceada 
Qual e a principal caracteristica de uma arvore balanceada?
a) Ter todos os nos com o mesmo valor
b) Possuir todos os niveis completamente preenchidos
c) Manter a altura minima possivel para o numero de nos
d) Nao permitir nos duplicados
Resposta: c) Manter a altura minima possivel para o numero de nos
Explicacao: Uma arvore balanceada e estruturada de forma a reduzir a altura total da arvore,
garantindo que a diferenca de altura entre subarvores filhas de qualquer no seja limitada, o que
otimiza o desempenho em operacoes como busca, insercao e remocao.
Qual das seguintes arvores e um exemplo classico de arvore balanceada?
a) Arvore binaria de busca desbalanceada
b) Arvore AVL
c) Arvore linear
d) Arvore generica
Resposta: b) Arvore AVL
Explicacao: A arvore AVL e um tipo de arvore binaria de busca que mantem o balanceamento
atraves da verificacao do fator de balanceamento (diferenca entre alturas das subarvores esquerda
e direita) a cada insercao ou remocao, realizando rotacoes quando necessario.
O que e fator de balanceamento em uma arvore AVL?
a) Diferenca entre o maior e o menor valor da arvore
b) Diferenca de altura entre as subarvores esquerda e direita de um no
c) Numero de folhas da arvore
d) Quantidade de nos na subarvore direita
Resposta: b) Diferenca de altura entre as subarvores esquerda e direita de um no
Explicacao: O fator de balanceamento de um no em uma arvore AVL e calculado como a altura da
subarvore esquerda menos a altura da subarvore direita. Valores aceitaveis sao -1, 0 ou 1; valores
fora desse intervalo indicam que a arvore precisa ser ajustada.
Qual operacao e utilizada para manter o balanceamento de uma arvore AVL apos insercao ou
remocao de um no?
a) Divisao
b) Rotacao
c) Juncao
d) Remocao de folha
Resposta: b) Rotacao
Explicacao: As rotacoes sao operacoes fundamentais em arvores AVL. Elas reorganizam os nos
para restaurar o balanceamento sem violar a propriedade de busca binaria. Existem rotacoes
simples (a esquerda ou a direita) e duplas (esquerda-direita e direita-esquerda).
Em uma arvore AVL, qual e o fator de balanceamento de um no que possui subarvore esquerda de
altura 4 e subarvore direita de altura 2?
a) -2
b) 2
c) 0
d) -1
Resposta: b) 2
Explicacao: O fator de balanceamento e calculado como altura da subarvore esquerda menos
altura da subarvore direita: 4 - 2 = 2. Como o valor esta fora do intervalo aceitavel (-1, 0, 1), esse no
exige uma rotacao para reequilibrar a arvore.
Qual e a complexidade de busca em uma arvore AVL balanceada?
a) O(n)
b) O(log n)
c) O(n2)
d) O(1)
Resposta: b) O(log n)
Explicacao: Por ser balanceada, a altura da arvore AVL e aproximadamente logaritmica em relacao
ao numero de nos, garantindo que operacoes de busca, insercao e remocao sejam realizadas em
tempo O(log n).
Qual das seguintes afirmativas sobre arvores rubro-negras (Red-Black Trees) e verdadeira?
a) Sempre tem todos os niveis completamente preenchidos
b) Nao garantem balanceamento, apenas respeitam a ordem binaria
c) Mantem balanceamento aproximado com regras de cores nos nos
d) Sao iguais as arvores AVL
Resposta: c) Mantem balanceamento aproximado com regras de cores nos nos
Explicacao: Arvores rubro-negras usam propriedades de cores para manter um balanceamento
aproximado. Cada caminho da raiz ate uma folha tem o mesmo numero de nos negros, garantindo
que a altura maxima nao seja muito maior que a minima, o que mantem buscas eficientes.
Qual e a diferenca principal entre arvores AVL e arvores rubro-negras em termos de
balanceamento?
a) Arvores AVL sao sempre mais altas que rubro-negras
b) Arvores AVL mantem balanceamento estrito, enquanto rubro-negras permitem um
balanceamento mais flexivel
c) Rubro-negras nao permitem remocao de nos
d) Arvores AVL nao suportam insercao
Resposta: b) Arvores AVL mantem balanceamento estrito, enquanto rubro-negras permitem um
balanceamento mais flexivel
Explicacao: Arvores AVL garantem que o fator de balanceamento seja sempre -1, 0 ou 1, mantendo
uma altura minima rigorosa. Arvores rubro-negras permitem variacoes maiores na altura,
proporcionando menos rotacoes durante insercoes e remocoes.
Quando ocorre uma rotacao dupla esquerda-direita em uma arvore AVL?
a) Quando o no desbalanceado possui subarvore direita pesada
b) Quando o no desbalanceado possui subarvore esquerda pesada e o filho esquerdo possui
subarvore direita mais alta
c) Quando todos os nos possuem fator de balanceamento 0
d) Quando a arvore esta vazia
Resposta: b) Quando o no desbalanceado possui subarvore esquerda pesada e o filho esquerdo
possui subarvore direita mais alta
Explicacao: A rotacao dupla esquerda-direita corrige casos de desbalanceamento onde uma
simples rotacao a direita nao e suficiente, reorganizando os nos de forma que a arvore recupere o
equilibrio.
Qual e a vantagem principal de manter uma arvore balanceada?
a) Aumentar o numero de folhas
b) Reduzir a altura da arvore para acelerar operacoes
c) Permitir duplicidade de valores
d) Facilitar a impressao grafica da arvore
Resposta: b) Reduzir a altura da arvore para acelerar operacoes
Explicacao: Ao reduzir a altura da arvore, operacoes de busca, insercao e remocao sao realizadas
de forma mais eficiente, mantendo o desempenho proximo do ideal logaritmico, independentemente
da quantidade de nos.
Em arvores AVL, o que acontece se voce inserir um no que provoca fator de balanceamento igual a
-2?
a) Nada, a arvore continua balanceada
b) E necessario realizar rotacao simples ou dupla para restaurar o balanceamento
c) Todos os nos sao reorganizados
d) O no e descartado
Resposta: b) E necessario realizar rotacao simples ou dupla para restaurar o balanceamento
Explicacao: Um fator de balanceamento fora do intervalo permitido (-1, 0, 1) indica
desbalanceamento. Dependendo da configuracao das subarvores, aplica-se rotacao simples ou
dupla para manter a propriedade de arvore AVL.
Qual e a altura maxima de uma arvore rubro-negra com 15 nos?
a) 3
b) 7
c) 8
d) 15
Resposta: c) 8
Explicacao: Arvores rubro-negras garantem que a altura nao exceda 2 * log2(n+1). Para n = 15,
log2(16) = 4, e o maximo de altura e aproximadamente 2 * 4 = 8.
O que significa dizer que uma arvore esta desbalanceada a direita?
a) Que nao possui subarvore esquerda
b) Que a subarvore direita tem altura maior que a esquerda por mais de 1
c) Que a raiz esta errada
d) Que os nos a esquerda sao menores que os da direita
Resposta: b) Que a subarvore direita tem altura maior que a esquerda por mais de 1
Explicacao: Uma arvore esta desbalanceada a direita quando a diferenca de altura entre subarvore
direita e esquerda e maior que 1, exigindo rotacoes a esquerda ou rotacoes duplas para corrigir.
Qual e a diferenca entre uma arvore binaria de busca e uma arvore AVL?
a) AVL e sempre maior
b) AVL e balanceada para manter altura minima, enquanto binaria de busca simples pode se
desbalancear
c) Binaria de busca nao permite insercoes
d) AVL nao possui raiz
Resposta: b) AVL e balanceada para manter altura minima, enquanto binaria de busca simples
pode se desbalancear
Explicacao: Enquanto toda arvore AVL e uma arvore binaria de busca, nem toda arvore binaria de
busca e AVL. O balanceamento garante operacoes mais rapidas e previsiveis.
Qual caso de insercao exige uma rotacao dupla direita-esquerda em uma arvore AVL?
a) Insercao a direita da subarvore direita
b) Insercao a esquerda da subarvore direita
c) Insercao a esquerda da subarvore esquerda
d) Insercao a direita da raiz
Resposta: b) Insercao a esquerda da subarvore direita
Explicacao: Quando a subarvore direita do no desbalanceado tem uma insercao na esquerda, a
simples rotacao a esquerda nao resolve; entao aplica-se uma rotacao dupla direita-esquerda para
restaurar o balanceamento.
Em uma arvore AVL, se uma rotacao simples a direita e aplicada, qual caracteristica e alterada?
a) O valor dos nos
b) A altura do no desbalanceado e seus filhos
c) O numerode folhas
d) O fator de balanceamento dos nos da arvore inteira
Resposta: b) A altura do no desbalanceado e seus filhos
Explicacao: A rotacao simples a direita reorganiza a estrutura da subarvore afetada, ajustando a
altura do no desbalanceado e de seus filhos, restaurando o fator de balanceamento adequado.
Qual das alternativas a seguir e uma vantagem de arvores rubro-negras sobre arvores AVL?
a) Balanceamento estrito
b) Menor numero de rotacoes durante insercoes e remocoes
c) Garantia de fator de balanceamento -1, 0, 1
d) Altura minima exata
Resposta: b) Menor numero de rotacoes durante insercoes e remocoes
Explicacao: Arvores rubro-negras permitem maior flexibilidade no balanceamento, resultando em
menos rotacoes comparadas as arvores AVL, o que e vantajoso em cenarios com muitas insercoes
e remocoes.
O que e necessario verificar apos cada insercao em uma arvore AVL?
a) Se a arvore esta vazia
b) O fator de balanceamento de todos os ancestrais do no inserido
c) Se a raiz mudou de posicao
d) Se a arvore tem folhas suficientes
Resposta: b) O fator de balanceamento de todos os ancestrais do no inserido
Explicacao: Apos a insercao, qualquer no ancestral pode ficar desbalanceado. Por isso, o fator de
balanceamento de cada ancestral e verificado, e rotacoes sao aplicadas quando necessario para
manter a arvore AVL.
Qual das seguintes afirmacoes sobre arvores balanceadas e falsa?
a) Elas minimizam a altura da arvore
b) Garantem complexidade logaritmica em operacoes de busca
c) Sempre possuem numero par de nos
d) Utilizam rotacoes para restaurar balanceamento
Resposta: c) Sempre possuem numero par de nos
Explicacao: Arvores balanceadas nao possuem restricao quanto ao numero de nos; podem ter
qualquer quantidade. O foco esta na altura e no balanceamento entre subarvores, nao na paridade
do numero de nos.
Por que arvores AVL nao sao sempre a escolha ideal para bancos de dados?
a) Porque nao suportam valores duplicados
b) Porque insercoes e remocoes frequentes exigem muitas rotacoes
c) Porque a busca e lenta
d) Porque nao mantem a ordem dos elementos
Resposta: b) Porque insercoes e remocoes frequentes exigem muitas rotacoes
Explicacao: Arvores AVL mantem balanceamento rigoroso, mas isso gera custo extra em ambientes
com muitas insercoes e remocoes. Arvores rubro-negras, com balanceamento mais flexivel, sao
preferidas em bancos de dados por reduzir o numero de rotacoes necessarias.
Se voce quiser, posso continuar criando mais 40 ou 50 perguntas detalhadas ate chegarmos
facilmente a um documento de mais de 1000 palavras, mantendo o mesmo estilo humano e
explicativo. Quer que eu faca isso?