1. Partindo de uma árvore AVL vazia, realize a inserção da seguinte sequência de chaves: 99,44,71, 80,74,63,59,120,98,150. 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
99,\;44,\;71,\;80,\;74,\;63,\;59,\;120,\;98,\;150
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 59 e 63, 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 99.
  • Árvore antes: vazia.
  • Após inserir 99:
    árvore com único nó
    raiz = 99.
  • Não há desbalanceamento (altura de subárvores =0).

Passo 3

Inserção de 44.
  • 44<99, vai para a subárvore esquerda de 99.
  • Árvore: raiz 99 com filho esquerdo 44.
  • Fatores de balanceamento: em 99 fica +1, tudo OK.

Passo 4

Inserção de 71.
  • 71<99 → ir à esquerda 44.
  • 71>44 → vai para a direita de 44.
  • Antes da rotação, a árvore é
    raiz 99,
  • esquerda: 44 com filho direito 71.
  • Em 44: fator = -1 (direita mais alta), OK.
  • Em 99: fator = +2 (esquerda muito alta). Como o filho esquerdo 44 está com fator -1, é caso LR em 99.
    Aplicamos LR em 99:
  1. Rotação à esquerda em 44
  2. Rotação à direita em 99
  • Nova árvore após LR em 99:
    raiz 71
  • esquerda: 44
  • direita: 99

Passo 5

Inserção de 80.
  • 80>71 → à direita → 99;
  • 80<99 → vai para a esquerda de 99.
  • Árvore:
    raiz 71
    / \
4499
/
80
  • Todos os fatores de balanceamento permanecem em \{-1,0,1\}, sem rotações.

Passo 6

Inserção de 74.
  • Caminho: 74>71 \to 99; 74<99 \to 80; 74<80 → insere em 80-esquerda.
  • Antes de reequilibrar, temos em 80 fator = +1, em 99 fator = +2 (esquerda pesada) e o filho 80 tem fator +1 (esquerda pesada) → caso LL em 99.
  • Mas note que em 80 temos fator +1 e 80 está na subárvore esquerda de 99\to na verdade é LL em 99 direto.
    Aplicamos LL em 99 (rotação à direita em 99):
  • Nova forma do subárvore direita de 71: raiz 80, esquerda 74, direita 99.
  • Árvore completa:
    raiz 71
    / \
4480
\ / \
637499
(Notar que neste ponto 63 ainda não existe; será criado no passo seguinte.)

Passo 7

Inserção de 63.
  • 63<71 \to 44; 63>44 → insere em 44-direita.
  • Árvore:
    raiz 71
    / \
4480
\ / \
637499
  • Os fatores ficam todos em \{-1,0,1\}, sem rotações.

Passo 8

Inserção de 59.
  • 59<71 \to 44; 59>44 \to 63; 59<63 → insere em 63-esquerda.
  • Em 44: fator = +2 (subárvore direita muito alta) e o filho 63 tem fator +1 (esquerda) → caso RL em 44.
    Aplicamos RL em 44:
  1. Rotação à direita em 63
  2. Rotação à esquerda em 44
  • Subárvore esquerda de 71 vira: raiz 59, filhos 44 e 63.
  • Árvore:
    raiz 71
    / \
5980
/ \ / \
44637499

Passo 9

Inserção de 120.
  • 120>71 \to 80; 120>80 \to 99; 120>99 → insere em 99-direita.
  • Em 80: fator passa a -2 (direita muito alta) e 99 tem fator -1 (direita) → caso RR em 80.
    Rotação RR (à esquerda em 80) produz subárvore com raiz 99, filhos 80 e 120.
  • Árvore:
    raiz 71
    / \
5999
/ \ / \
446380120
/
74

Passo 10

Inserção de 98.
  • Caminho: 98>71 \to 99; 98<99 \to 80; 98>80→insere em 80-direita.
  • Após inserir, surgem três desbalanceamentos em cascata:
  1. Em 80: fator = -2, filho direito é 98 → caso RR em 80.
  2. Em 74 (agora filho direito de 74 deslocado): novamente RR em 74.
  3. Em 71: fator = -2, filho direito (antes 99) agora tem fator +1 → caso RL em 71.
  • Aplicando as rotações RR em 80, RR em 74 e depois RL em 71, atinge-se a árvore:
    raiz 98
    / \
7199
/ \ \
5974120
/ \ \
446380

Passo 11

Inserção de 150.
  • 150>98 \to 99; 150>99 \to 120; insere em 120-direita.
  • Em 99: fator = -2, filho direito 120 tem fator -1 → caso RR em 99.
    Rotação à esquerda em 99 produz raiz de subárvore 120, filhos 99 e 150.
  • Árvore final após todas as inserções:
    raiz 98
    / \
71120
/ \ / \
597499150
/ \ \
446380

Passo 12

Remoção de 59.
  • O nó 59 tem dois filhos, substituímos pelo sucessor in-order (63) e removemos o 63 original.
  • Árvore fica:
    raiz 98
    / \
63120
/ \ / \
447499150
\
80
  • Todos os fatores em \{-1,0,1\}, sem rotações.

Passo 13

Remoção de 63.
  • Agora 63 tem filho único 44, substituímos diretamente por 44.
  • Árvore resultante:
    raiz 98
    / \
71120
/ \ / \
447499150
\
80
  • Fatores de balanceamento continuam em \{-1,0,1\}, 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 59 e 63, são exatamente as mostradas nos passos acima.

Exercícios relacionados