SóProvas

ID
2839405
Banca
FADESP
Órgão
IF-PA
Ano
2018
Provas
Disciplina
Algoritmos e Estrutura de Dados
Assuntos

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
Comentários

  • 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

  • Dica para chegar na resolução: (1) ele disse que as árvores são binárias; (2) ele disse que a busca em PRÉ-ORDERM produziu os elementos que estão no vetor. Dessa forma, o primeiro elemento do vetor vai ser a raiz da árvore (pois a busca foi pré-ordem); (3) descobrindo-se a raiz, basta apenas montar a árvore toda e verificar quais delas estão balanceadas. Resposta T2 e T3.

  • Força Guerreiro!!!!!!