Árvore balanceada

Prévia do material em texto

Árvore balanceada 
O que caracteriza uma arvore balanceada?
a) Uma arvore onde todos os nos tem o mesmo numero de filhos
b) Uma arvore em que a diferenca de altura entre as subarvores de qualquer no e minima
c) Uma arvore em que todas as folhas estao no mesmo nivel
d) Uma arvore que nao possui nos filhos
Resposta explicativa:
Uma arvore balanceada e estruturada de forma que a diferenca de altura entre as subarvores
esquerda e direita de qualquer no seja pequena, geralmente 1 ou 0, dependendo do tipo de arvore.
Isso garante operacoes de busca, insercao e remocao mais eficientes, com complexidade proxima
de O(log n).
Qual e a principal vantagem de uma arvore balanceada em relacao a uma arvore binaria comum?
a) Ocupa menos memoria
b) Permite operacoes com complexidade garantida O(log n)
c) Nao possui folhas
d) Nao precisa de ponteiros
Resposta explicativa:
O principal beneficio de uma arvore balanceada e que ela mantem a altura minima possivel,
garantindo que buscas, insercoes e remocoes sejam realizadas em tempo O(log n). Arvores
binarias comuns podem se degenerar em listas se nao forem balanceadas, aumentando a
complexidade para O(n).
Qual das seguintes arvores e um exemplo classico de arvore balanceada?
a) Arvore Binaria de Busca sem balanceamento
b) Arvore AVL
c) Lista encadeada
d) Pilha
Resposta explicativa:
A Arvore AVL e um exemplo classico de arvore balanceada. Ela mantem a diferenca de altura entre
as subarvores de qualquer no em no maximo 1, realizando rotacoes quando necessario para
preservar o balanceamento apos insercoes ou remocoes.
Em uma arvore AVL, o que acontece quando a diferenca de altura entre subarvores excede 1 apos
uma insercao?
a) O no e removido
b) Sao realizadas rotacoes para restaurar o balanceamento
c) Nada acontece
d) Todas as folhas sao deslocadas para a raiz
Resposta explicativa:
Quando a diferenca de altura excede 1 em uma arvore AVL, realiza-se uma rotacao simples ou
dupla para restaurar o balanceamento. Esse processo garante que a altura da arvore continue
proxima de log2(n), mantendo a eficiencia das operacoes.
Qual e a diferenca entre uma arvore AVL e uma arvore Red-Black?
a) Arvores AVL nao permitem remocoes
b) Arvores Red-Black permitem diferenca de altura maior, oferecendo balanceamento relaxado
c) Arvores AVL nao sao binarias
d) Arvores Red-Black nao possuem folhas
Resposta explicativa:
Arvores Red-Black sao balanceadas de forma mais flexivel do que AVL. Enquanto AVL garante
diferenca maxima de 1 na altura das subarvores, Red-Black permite diferenca maior, o que resulta
em menos rotacoes e menor custo em insercoes e remocoes, embora a altura maxima seja um
pouco maior.
Qual e a complexidade de busca em uma arvore balanceada com n nos?
a) O(n)
b) O(log n)
c) O(1)
d) O(n2)
Resposta explicativa:
Em uma arvore balanceada, a altura e mantida proxima de log2(n), garantindo que a busca
percorra no maximo O(log n) niveis. Isso representa uma grande melhoria em relacao a arvores
desbalanceadas, que podem ter complexidade O(n) no pior caso.
Em arvores AVL, quais sao os tipos de rotacoes utilizadas para manter o balanceamento?
a) Rotacoes simples e duplas
b) Rotacoes circulares apenas
c) Rotacoes lineares apenas
d) Nenhuma rotacao e utilizada
Resposta explicativa:
Para restaurar o balanceamento em uma arvore AVL, utilizam-se rotacoes simples (a esquerda ou
a direita) e rotacoes duplas (combinacao de duas rotacoes). Essas rotacoes ajustam a estrutura da
arvore mantendo a propriedade de diferenca de altura 1.
Qual e a diferenca principal entre arvores AVL e arvores B?
a) Arvores AVL sao binarias; arvores B podem ter multiplos filhos por no
b) Arvores B sao sempre menores
c) Arvores AVL nao permitem insercao
d) Arvores B nao armazenam dados
Resposta explicativa:
Arvores AVL sao arvores binarias balanceadas, onde cada no tem no maximo dois filhos. Arvores B
permitem multiplos filhos e multiplas chaves por no, sendo especialmente uteis para
armazenamento em disco e grandes volumes de dados.
Por que e importante que uma arvore esteja balanceada para operacoes de insercao e remocao?
a) Evita que a arvore cresca demais
b) Garante que a complexidade dessas operacoes permaneca O(log n)
c) Reduz o numero de folhas
d) Aumenta a quantidade de nos internos
Resposta explicativa:
O balanceamento garante que a altura da arvore permaneca minima, permitindo que insercoes e
remocoes sejam feitas de forma eficiente em O(log n). Arvores desbalanceadas podem degenerar,
aumentando drasticamente o tempo necessario para essas operacoes.
Em uma arvore AVL, qual e a condicao para que uma rotacao dupla seja necessaria?
a) Quando a subarvore esquerda esta vazia
b) Quando a insercao ocorre na subarvore externa de um filho desbalanceado
c) Quando a arvore possui apenas um no
d) Sempre apos qualquer insercao
Resposta explicativa:
Uma rotacao dupla e necessaria quando a insercao ocorre na subarvore interna do filho
desbalanceado (por exemplo, insercao no filho direito da subarvore esquerda ou no filho esquerdo
da subarvore direita). A rotacao dupla corrige o desequilibrio mantendo a propriedade de diferenca
de altura 1.
Qual e a diferenca de complexidade de insercao entre arvores AVL e arvores binarias de busca nao
balanceadas?
a) AVL: O(log n), Binaria: O(n) no pior caso
b) AVL: O(n2), Binaria: O(log n)
c) Ambas tem O(1)
d) Nao ha diferenca significativa
Resposta explicativa:
A insercao em uma arvore AVL e O(log n) porque a altura e mantida baixa. Em uma arvore binaria
nao balanceada, a altura pode ser O(n) no pior caso (como uma lista encadeada), tornando a
insercao menos eficiente.
O que significa o fator de balanceamento em uma arvore AVL?
a) A diferenca entre o numero de filhos esquerdo e direito
b) A diferenca de altura entre a subarvore esquerda e a subarvore direita de um no
c) A soma de todas as alturas da arvore
d) O numero de rotacoes realizadas
Resposta explicativa:
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 -1, 0 ou 1 indicam que o no esta
balanceado. Se o fator estiver fora desse intervalo, a arvore precisa de rotacoes.
Em arvores Red-Black, qual propriedade garante que a arvore permaneca balanceada?
a) Todos os nos tem a mesma quantidade de filhos
b) As regras de cores e caminhos negros garantem altura maxima de 2 log2(n+1)
c) Todos os nos folha armazenam dados reais
d) Nenhuma propriedade especifica
Resposta explicativa:
Arvores Red-Black utilizam cores (vermelho e preto) e regras especificas para garantir que nenhum
caminho da raiz ate uma folha seja mais que o dobro de outro, limitando a altura maxima a 2
log2(n+1). Isso garante balanceamento relaxado e eficiencia em busca e insercao.
Qual e a vantagem de arvores Red-Black em comparacao com AVL em sistemas que realizam
muitas insercoes e remocoes?
a) Red-Black nunca realiza rotacoes
b) Red-Black realiza menos rotacoes, sendo mais eficiente em atualizacoes frequentes
c) AVL nao permite remocoes
d) AVL e mais simples de implementar
Resposta explicativa:
Arvores Red-Black sao mais tolerantes a pequenas desbalanceamentos, realizando menos
rotacoes que AVL durante insercoes e remocoes. Isso torna Red-Black mais eficiente em sistemas
com muitas atualizacoes, embora a altura possa ser ligeiramente maior que AVL.
Qual e a principal consequencia de nao balancear uma arvore binaria de busca?
a) A arvore se transforma em grafo
b) A arvore pode degenerar em uma lista, aumentando a complexidade das operacoes para O(n)
c) A arvore cresce infinitamente
d) Nao ha consequencias
Resposta explicativa:
Se uma arvore binaria de busca nao for balanceada, insercoes ordenadas podem fazer com que
todos os nos fiquem em uma unica direcao, transformando a arvore praticamente em uma lista
ligada. Isso aumenta a complexidade de busca, insercao e remocao de O(log n) para O(n).
Como uma arvore Splay mantem balanceamentoamortizado?
a) Realiza rotacoes frequentes para trazer nos acessados recentemente para a raiz
b) Mantem todos os nos folha na mesma altura
c) Nao realiza nenhuma operacao de balanceamento
d) Apenas remove nos repetidos
Resposta explicativa:
Arvores Splay realizam rotacoes para trazer o no acessado recentemente para a raiz, equilibrando
a arvore ao longo do tempo. O balanceamento e amortizado, garantindo complexidade media O(log
n) para uma sequencia de operacoes, embora um unico acesso possa ser mais custoso.
Qual e a vantagem de arvores AVL em aplicacoes que realizam muitas buscas em comparacao
com muitas insercoes?
a) AVL oferece consultas mais rapidas devido ao balanceamento estrito
b) AVL nao permite remocoes
c) AVL e mais simples que Red-Black
d) Nao ha vantagem especifica
Resposta explicativa:
O balanceamento estrito da arvore AVL garante altura minima, tornando buscas muito eficientes,
mesmo que insercoes e remocoes exijam rotacoes. Por isso, AVL e ideal para aplicacoes com
muitas consultas e poucas atualizacoes.
O que acontece se uma arvore Red-Black nao respeitar as propriedades de cor apos uma
insercao?
a) A arvore se torna AVL
b) Sao realizadas rotacoes e mudancas de cor para restaurar as propriedades
c) A arvore e destruida
d) Nada acontece
Resposta explicativa:
Apos uma insercao que viola as propriedades de cor, a arvore Red-Black realiza rotacoes e ajustes
de cor para restaurar o balanceamento. Essas operacoes garantem que a altura da arvore
permaneca limitada e que buscas continuem eficientes.
Em arvores balanceadas, por que e importante manter a altura minima possivel?
a) Reduz o numero de folhas
b) Reduz o numero de niveis a serem percorridos em operacoes de busca, insercao e remocao
c) Garante que nao haja nos duplicados
d) Evita o uso de ponteiros
Resposta explicativa:
Manter a altura minima permite que qualquer operacao percorra o menor numero possivel de niveis,
mantendo a complexidade de busca, insercao e remocao em O(log n). Isso aumenta
significativamente a eficiencia da estrutura de dados.
Qual e a relacao entre arvores B e arvores balanceadas binarias como AVL?
a) Ambas garantem balanceamento, mas B e multiway e otimizada para armazenamento externo
b) Ambas sao arvores binarias estritas
c) Arvores B nao permitem balanceamento
d) AVL e multiway, B e binaria
Resposta explicativa:
Arvores B e AVL garantem balanceamento, mas de formas diferentes. AVL e binaria e mantem
diferenca de altura 1, enquanto arvores B permitem multiplas chaves por no, mantendo a arvore
baixa e eficiente para armazenamento externo, como em discos e bancos de dados.
Posso continuar criando mais 30 perguntas detalhadas sobre arvores balanceadas para ultrapassar
1000 palavras, mantendo o mesmo estilo explicativo natural. Quer que eu faca isso?