- Partindo de uma árvore AVL vazia, realize a inserção da seguinte sequência de chaves:
,
. Redesenhe a árvore a cada inserção. Indique para cada rotação feita, o nó desregulado e a rotação aplicada (LL,RR,LR,RL). Em seguida remova os nós 59 e 63 mostrando as árvores resultantes a cada exclusão e a rotação aplicada (quando necessário).
Passo 1
O enunciado pede para construir passo a passo uma árvore AVL inserindo as chaves na ordem
mostrando a árvore a cada inserção e indicando, sempre que ocorrer, o nó desregulado e o tipo de rotação (LL, RR, LR, RL). Em seguida remover os nós
e
, exibindo as árvores resultantes e as rotações aplicadas, se houver. Vamos usar as definições de fator de balanceamento e as regras de rotação de AVL.
Passo 2
Inserção de
.
- Árvore antes: vazia.
- Após inserir
:
árvore com único nó
raiz =. - Não há desbalanceamento (altura de subárvores
).
Passo 3
Inserção de
.
-
, vai para a subárvore esquerda de . - Árvore: raiz
com filho esquerdo . - Fatores de balanceamento: em
fica , tudo OK.
Passo 4
Inserção de
.
-
→ ir à esquerda . -
→ vai para a direita de . - Antes da rotação, a árvore é
raiz, - esquerda:
com filho direito . - Em
: fator = (direita mais alta), OK. - Em
: fator = (esquerda muito alta). Como o filho esquerdo está com fator , é caso LR em .
Aplicamos LR em:
- Rotação à esquerda em
- Rotação à direita em
- Nova árvore após LR em
:
raiz - esquerda:
- direita:
Passo 5
Inserção de
.
-
→ à direita → ; -
→ vai para a esquerda de . - Árvore:
raiz
/ \
/
80
80
- Todos os fatores de balanceamento permanecem em
, sem rotações.
Passo 6
Inserção de
.
- Caminho:
; ; → insere em 80-esquerda. - Antes de reequilibrar, temos em 80 fator =
, em 99 fator = (esquerda pesada) e o filho 80 tem fator (esquerda pesada) → caso LL em . - Mas note que em 80 temos fator
e 80 está na subárvore esquerda de na verdade é LL em 99 direto.
Aplicamos LL em(rotação à direita em 99): - Nova forma do subárvore direita de 71: raiz
, esquerda , direita . - Árvore completa:
raiz
/ \
\ / \
(Notar que neste ponto 63 ainda não existe; será criado no passo seguinte.)
Passo 7
Inserção de
.
-
; → insere em 44-direita. - Árvore:
raiz
/ \
\ / \
- Os fatores ficam todos em
, sem rotações.
Passo 8
Inserção de
.
-
; ; → insere em 63-esquerda. - Em 44: fator =
(subárvore direita muito alta) e o filho 63 tem fator (esquerda) → caso RL em .
Aplicamos RL em:
- Rotação à direita em
- Rotação à esquerda em
- Subárvore esquerda de 71 vira: raiz
, filhos e . - Árvore:
raiz
/ \
/ \ / \
Passo 9
Inserção de
.
-
; ; → insere em 99-direita. - Em 80: fator passa a
(direita muito alta) e 99 tem fator (direita) → caso RR em .
Rotação RR (à esquerda em 80) produz subárvore com raiz, filhos e . - Árvore:
raiz
/ \
/ \ / \
/
74
74
Passo 10
Inserção de
.
- Caminho:
; ; →insere em 80-direita. - Após inserir, surgem três desbalanceamentos em cascata:
- Em
: fator = , filho direito é → caso RR em . - Em
(agora filho direito de 74 deslocado): novamente RR em . - Em
: fator = , filho direito (antes 99) agora tem fator → caso RL em .
- Aplicando as rotações RR em 80, RR em 74 e depois RL em 71, atinge-se a árvore:
raiz
/ \
/ \ \
/ \ \
Passo 11
Inserção de
.
-
; ; insere em 120-direita. - Em
: fator = , filho direito tem fator → caso RR em .
Rotação à esquerda emproduz raiz de subárvore , filhos e . - Árvore final após todas as inserções:
raiz
/ \
/ \ / \
/ \ \
Passo 12
Remoção de
.
- O nó
tem dois filhos, substituímos pelo sucessor in-order e removemos o original. - Árvore fica:
raiz
/ \
/ \ / \
\
80
80
- Todos os fatores em
, sem rotações.
Passo 13
Remoção de
.
- Agora
tem filho único , substituímos diretamente por . - Árvore resultante:
raiz
/ \
/ \ / \
\
80
80
- Fatores de balanceamento continuam em
, sem rotações.
Resposta
As árvores AVL após cada inserção, com os nós desregulados e rotações aplicadas, e as árvores finais depois das exclusões de
e
, são exatamente as mostradas nos passos acima.