Faça um esquema gráfico que represente a estrutura final de uma árvore AVL gerada pela inserção dos números 13,7,31,43,8,17,5,3,1,23,16 e 36 nesta ordem

Passo 1

O enunciado pede para inserir, em uma árvore AVL, os números 13, 7, 31, 43, 8, 17, 5, 3, 1, 23, 16 e 36 na ordem dada e apresentar o esquema gráfico da estrutura final. Vamos usar os conceitos de fator de balanceamento (diferença de alturas das subárvores esquerda e direita) e rotações (LL, RR, LR, RL) para manter a árvore balanceada.

Passo 2

Inserimos 13, 7, 31, 43, 8, 17, 5 e 3 sem criar desbalanceamentos que exijam rotações. Após essas inserções, a árvore fica assim:
    13
   /  \
  7    31
 / \   / \
5   8 17  43
/
3

Passo 3

Ao inserir 1, descemos pela esquerda sucessivamente (13→7→5→3) e colamos 1 como filho esquerdo de 3. Isso deixa o nó 5 com fator de balanceamento +2 (subárvore esquerda de altura 2 e direita vazia) — é um caso LL. Aplicamos rotação simples à direita em 5, resultando em:
    13
   /  \
  7    31
 / \   / \
3   8 17  43
/
1 5

Passo 4

Por fim, inserimos 23, 16 e 36. Cada um cai em um local que não causa desequilíbrio maior que 1 em nenhum nó, então não há novas rotações. A árvore final é:
(ver “Resposta Final” abaixo)

Resposta

    13
   /  \
  7    31
 / \   / \
3   8 17  43
/ \ / \ /
1 5 16 23 36

Exercícios relacionados