1. Insira os números 10,9,8,7,6,5,4,3,2,1 nessa ordem em uma AVL inicialmente vazia e mostre o estado final da árvore.

Passo 1

O enunciado pede para inserir, em ordem decrescente, os valores \,10,9,8,7,6,5,4,3,2,1 em uma árvore AVL inicialmente vazia e, ao fim, mostrar a estrutura final. O conteúdo usado é a inserção em árvore binária de busca com rebalanceamentos (rotações) sempre que o fator de balanço de um nó ultrapassa \,1 em módulo.

Passo 2

Inserimos \,10, depois \,9 e \,8. Após inserir \,8 temos um caso de “esquerda–esquerda” no nó \,10, pois a sequência ficou
10 \to \text{esq}=9 \to \text{esq}=8.
Fazemos uma rotação simples à direita em 10, resultando em
 9
 / \
\[810\]

Passo 3

Em seguida inserimos \,7 e depois \,6.
  • Inserindo \,7 a árvore vira
 9
 / \
\[810\]
 /
7
  • Inserindo \,6 gera novo desbalanceamento em 8 (caso “LL”), então rotacionamos à direita em 8:
 9
 / \
\[710\]
 / \
\[68\]

Passo 4

Agora inserimos \,5 e em seguida \,4.
  • Ao inserir \,5 ocorre desbalanço em 9 (fator =2 no lado esquerdo), rotação à direita em 9:
 7
 / \
\[69\]
 / / \
\[5810\]
  • Ao inserir \,4 desbalanceia 6 (caso “LL”), rotacionamos à direita em 6, ficando:
 7
 / \
\[59\]
 / \ / \
\[46810\]

Passo 5

Finalmente inserimos \,3, \,2 e \,1:
  • Com \,3 e \,2 inseridos, surgem desbalanceamentos em vários nós mas cada um é corrigido por rotações simples “LL” à direita nos nós 4 e depois em 5.
  • Ao inserir \,1 ocorre um último desbalanço em 5 (fator =2), e aplicamos rotação simples à direita em 5.
O resultado final é uma AVL perfeitamente balanceada:

Resposta

 7
 / \
\[39\]
 / \ / \
\[25810\]
 / / \
\[146\]

Exercícios relacionados