Faça um esquema gráfico que represente a estrutura final de uma árvore AVL gerada pela inserção dos números
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
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
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)
(ver “Resposta Final” abaixo)
Resposta
13
/ \
7 31
/ \ / \
3 8 17 43
/ \ / \ /
1 5 16 23 36
1 5 16 23 36