- Insira os números
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
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
em módulo.
Passo 2
Inserimos
, depois
e
. Após inserir
temos um caso de “esquerda–esquerda” no nó
, pois a sequência ficou
Fazemos uma rotação simples à direita em
, resultando em
9
/ \
\[810\]
Passo 3
Em seguida inserimos
e depois
.
- Inserindo
a árvore vira
9
/ \
\[810\]
/
7
- Inserindo
gera novo desbalanceamento em (caso “LL”), então rotacionamos à direita em :
9
/ \
\[710\]
/ \
\[68\]
Passo 4
Agora inserimos
e em seguida
.
- Ao inserir
ocorre desbalanço em (fator no lado esquerdo), rotação à direita em :
7
/ \
\[69\]
/ / \
\[5810\]
- Ao inserir
desbalanceia (caso “LL”), rotacionamos à direita em , ficando:
7
/ \
\[59\]
/ \ / \
\[46810\]
Passo 5
Finalmente inserimos
,
e
:
- Com
e inseridos, surgem desbalanceamentos em vários nós mas cada um é corrigido por rotações simples “LL” à direita nos nós e depois em . - Ao inserir
ocorre um último desbalanço em (fator ), e aplicamos rotação simples à direita em .
O resultado final é uma AVL perfeitamente balanceada:
Resposta
7
/ \
\[39\]
/ \ / \
\[25810\]
/ / \
\[146\]