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

A alternativa correta é a D - T2 e T3.

Para entender a questão, é necessário compreender alguns conceitos fundamentais sobre Árvores Binárias de Busca (BST) e Árvores AVL. Uma árvore AVL é uma árvore binária de busca que se mantém balanceada, ou seja, para qualquer nó da árvore, a diferença de altura entre sua subárvore esquerda e sua subárvore direita é, no máximo, 1.

Vamos analisar as sequências fornecidas para determinar quais das árvores são balanceadas do tipo AVL:

[3, 1, 2, 7, 5, 4, 6]
Essa sequência é obtida de uma árvore binária de busca T1 em pré-ordem. Montando a árvore, temos:

3
  /   \
1      7
  \   /
   2 5
      /  \
     4   6

Observando a estrutura, podemos ver que a subárvore esquerda da raiz (3) tem uma altura de 2, enquanto a subárvore direita tem altura 3. Isso faz com que a árvore T1 não esteja balanceada de acordo com os critérios AVL.

[3, 1, 2, 6, 4, 5, 7]
Essa é a sequência da árvore binária de busca T2 em pré-ordem. Montando-a, temos:

3
  /   \
1      6
  \   /  \
   2 4    7
       \
       5

Verificamos que as alturas das subárvores diferem em, no máximo, 1 para todos os nós, o que satisfaz os critérios AVL. Portanto, T2 é uma árvore AVL.

[4, 2, 1, 3, 6, 5, 7]
Essa é a sequência da árvore binária de busca T3 em pré-ordem. Montando-a, temos:

4
  /   \
2      6
/  \   /  \
1  3  5  7

Novamente, todas as subárvores têm alturas que diferem, no máximo, por 1 para todos os nós. Portanto, T3 também é uma árvore AVL.

Agora, vamos justificar por que as alternativas estão corretas ou incorretas:

A - T1: Incorreta. Como demonstrado, T1 não é uma árvore AVL.

B - T1 e T2: Incorreta. Embora T2 seja AVL, T1 não é.

C - T1 e T3: Incorreta. T3 é AVL, mas T1 não é.

D - T2 e T3: Correta. Ambas as árvores T2 e T3 são balanceadas do tipo AVL.

E - T1, T2 e T3: Incorreta. Apenas T2 e T3 são AVL; T1 não é.

Espero que esta explicação tenha ajudado a entender a questão e os conceitos envolvidos. Se tiver mais dúvidas, estou à disposição!

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