Sejam [3, 1, 2, 7, 5, 4, 6], [3, 1, 2, 6, 4, 5, 7] e [4, 2, ...

Próximas questões
Com base no mesmo assunto
Q946466
Algoritmos e Estrutura de Dados Estrutura de Dados , Árvores ,
Ano: 2018 Banca: FADESP Órgão: IF-PA Prova: FADESP - 2018 - IF-PA - Professor - Informática |
Q946466 Algoritmos e Estrutura de Dados
Sejam [3, 1, 2, 7, 5, 4, 6], [3, 1, 2, 6, 4, 5, 7] e [4, 2, 1, 3, 6, 5, 7] as sequências produzidas pelo percurso em pré-ordem das árvores binárias de busca T1, T2 e T3, respectivamente, é correto afirmar que é(são) árvore(s) balanceada(s) do tipo AVL (Adelson-Velski e Landis)
Alternativas

Gabarito comentado

Confira o gabarito comentado por um dos nossos professores

Gabarito: D

Fundamento decisivo: O elemento decisivo é que as sequências foram dadas como pré-ordem de BSTs, o que permite reconstrução recursiva pela regra de separação entre menores e maiores que a raiz. Após essa reconstrução, o critério AVL exige que, em todo nó, |altura(esquerda) - altura(direita)| <= 1. Pela análise indicada na base, T2 e T3 atendem a esse critério e T1 o viola; por isso, o gabarito é D.

Tema central: BST e AVL
Análise das alternativas
A
Errada
Incorreta porque considera apenas T1, mas T1 viola o critério AVL na raiz, enquanto T2 e T3 satisfazem o balanceamento exigido.
B
Errada
Incorreta porque inclui T1. A presença de T1 invalida a alternativa, já que essa árvore não atende ao critério AVL.
C
Errada
Incorreta porque inclui T1 e exclui T2. T1 não é AVL e T2 satisfaz o critério de balanceamento.
D
Certa
A alternativa D é correta porque, ao reconstruir as árvores binárias de busca a partir das pré-ordens dadas, verifica-se o balanceamento AVL em todos os nós. Em T2 e T3, a diferença entre as alturas das subárvores esquerda e direita permanece no máximo 1 em toda a árvore. Em T3, a estrutura é perfeitamente balanceada, com raiz 4, filhos 2 e 6, e folhas 1, 3, 5 e 7. Já T1 viola o critério AVL na raiz, pois a diferença entre as alturas de suas subárvores ultrapassa 1.
E
Errada
Incorreta porque afirma que todas as árvores são AVL. Basta T1 violar o critério para tornar a alternativa falsa, e isso ocorre na raiz.
Pegadinha da questão
A armadilha é confundir ser BST com ser AVL, ou analisar apenas a ordem da pré-ordem sem reconstruir a árvore e conferir o balanceamento em todos os nós.
Dica para questões semelhantes
  • Quando a questão informar pré-ordem de uma BST, reconstrua a árvore pela regra: raiz primeiro, menores à esquerda e maiores à direita.
  • Para AVL, verifique o fator de balanceamento em todos os nós, não apenas na raiz.
  • Use sempre o mesmo critério de altura ao comparar as subárvores.

Clique para visualizar este gabarito

Visualize o gabarito desta questão clicando no botão abaixo

Comentários

Veja os comentários dos nossos alunos

Não entendi pq a arvore t2 , está na resposta montando sua estrutura e depois percorrendo em pre ordem não consegui chegar a essa ordenação, o t1 realmente nao eh um t1, o t3 em pré-ordem bate certinho. Questão complicada de entender.

Essa questão tá sem coerência. Não tem como dizer que o T2 é uma árvore binária balanceada.

Gabarito, letra D

Primeiramente devemos entender qual a sequência de pré-ordem que seria:

Visitar a raiz;

Percorrer sua subárvore esquerda, em pré-ordem;

percorrer sua subárvore direita, me pré-ordem;

Seguindo a percurso de pré-ordem em árvores binárias (maiores valores para subárvores direita e menores para subárvores esquerda. Lembrando que para ser uma árvore AVL, precisa ser uma árvore binária de busca onde seu Fator de Balanceamento - FB (diferença em altura da subárvore da direita pela esquerda) seja no máximo 1. :

Agora construímos a árvore T1 [3, 1, 2, 7, 5, 4, 6]:

...........................................................3.................................... FB = +1 (3 - 2)

..................................................../.............. \....

FB = +1 (1 - 0)........................1..................7 ......................... FB = -2 (0 - 2)

...................................................\................/....

FB = 0 (folha).............................2............5............................. FB = 0 (1 - 1)

............................................................./..........\...

FB = 0 (folha)...................................4.............6.......................FB = 0 (folha)

Não é uma AVL pois, FB da subárvore 7 > 1

Agora construímos a árvore T2 [3, 1, 2, 6, 4, 5, 7]

...........................................................3.................................. FB = +1 (3 - 2)

..................................................../.............. \...

FB = +1 (1 - 0)........................1...................6 ..................... FB = -1 (1 - 2)

...................................................\............../........\..

FB [2] = 0 (folha)... ....................2.........4............7............... FB [7] = 0 (folha)

FB [4] = +1 (1 - 0)...................................\...

..................................................................5...........................FB = 0 (folha)

É uma AVL pois todas FB das subárvores são no máximo +1

o mesmo se segue para a árvore T3 [4, 2, 1, 3, 6, 5, 7]

...........................................................4................................. FB = 0 (2 - 2)

..................................................../.............\...

FB = 0 (1 - 0)........................2....................6 .................... FB = 0 (1 - 1)

............................................/.......\............../........\..

FB [1,3] = 0 (folhas).........1..........3..........5..........7............... FB [5,7] = 0 (folhas)

fonte: Estrutura de dados e seus algoritmos, Jayme Szwarcfiter. 3ª Ed.

instagram: @papirobizurado

Gabarito = D

Uma árvore binária T é denominada AVL quando, para qualquer nó de T, as alturas de suas duas subárvores, esquerda e direita, diferem em módulo de até uma unidade.

Fonte: Wikipédia

Usem esse simulador, é possível ver claramente que as árvores T2 e T3 estão balanceadas.

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

Clique para visualizar este comentário

Visualize os comentários desta questão clicando no botão abaixo

Questões de assuntos semelhantes

Provas relacionadas