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 em ordem as chaves
99,\;44,\;71,\;80,\;74,\;63,\;59,\;120,\;98,\;150
e, a cada inserção, redesenhar a árvore e indicar, se houver, o nó desregulado e o tipo de rotação (LL, RR, LR ou RL). Em seguida, remover as chaves 59 e 63, mostrando a árvore resultante a cada exclusão e indicando a rotação aplicada, se necessária. O conteúdo usado é a definição de fator de balanço e as quatro operações de rotação em árvore AVL.

Passo 2

Inserimos primeiro 99 e depois 44. Em ambas não há desbalanceamento; temos:
T = \bigl(99,\;(44,\varnothing,\varnothing),\;\varnothing\bigr).

Passo 3

Inserimos 71. A primeira árvore sem balancear seria
99 \bigl/ 44 \!\!\bigl\backslash 71
que dá fator de balanço em 99:
\text{FB}(99)=h(\text{esq})-h(\text{dir})=2-0=2,
e o filho esquerdo 44 tem FB = -1, caso LR. Aplicamos dupla rotação LR em 99 e obtemos
T = \bigl(71,\;(44,\varnothing,\varnothing),\;(99,\varnothing,\varnothing)\bigr).

Passo 4

Agora inserimos 80. Sem rotação, a árvore vira
T = \bigl(71,\;(44,\varnothing,\varnothing),\;(99,\;(80,\varnothing,\varnothing),\;\varnothing)\bigr),
com todos os fatores de balanço em -1,0 ou +1.
Em seguida inserimos 74. Antes de balancear:
71 \;/\!\backslash \;44\quad99 \quad / \;80 / 74
No nó 99 temos FB =2 e o filho esquerdo 80 tem FB =+1: caso LL. Aplicando rotação simples à direita em 99, fica
T = \bigl(71,\;(44,\varnothing,\varnothing),\;(80,\;(74,\varnothing,\varnothing),\;(99,\varnothing,\varnothing))\bigr).

Passo 5

Inserimos 63. Vai para a direita de 44, sem gerar desbalanceamento:
T = \bigl(71,\;(44,\;\varnothing,\;(63,\varnothing,\varnothing)),\;(80,\;(74,\varnothing,\varnothing),\;(99,\varnothing,\varnothing))\bigr).

Passo 6

Inserimos 59. Fica como filho esquerdo de 63, e o nó 44 passa a ter FB =0-2=-2; seu filho direito 63 tem FB =+1: caso RL. Aplicando dupla rotação RL (primeiro à direita em 63, depois à esquerda em 44), obtemos
T = \bigl(71,\;(59,\;(44,\varnothing,\varnothing),\;(63,\varnothing,\varnothing)),\;(80,\;(74,\varnothing,\varnothing),\;(99,\varnothing,\varnothing))\bigr).

Passo 7

Inserimos 120 e depois 98. Em ambos não ocorre desbalanceamento. A árvore final deste momento é
T = \bigl(71,\;(59,\;(44,\varnothing,\varnothing),\;(63,\varnothing,\varnothing)),\; (80,\;(74,\varnothing,\varnothing),\;(99,\;(98,\varnothing,\varnothing),\;(120,\varnothing,\varnothing)))\bigr).

Passo 8

Inserimos 150. Fica em 120\to direita, e o nó 80 tem FB =1-3=-2 com filho direito 99 de FB \le0: caso RR. Aplicamos rotação simples à esquerda em 80 e obtemos
T = \bigl(71,\;(59,\;(44,\varnothing,\varnothing),\;(63,\varnothing,\varnothing)),\; (99,\;(80,\;(74,\varnothing,\varnothing),\;(98,\varnothing,\varnothing)),\;(120,\;\varnothing,\;(150,\varnothing,\varnothing))))\bigr).

Passo 9

Removemos 59. Substituímos por seu sucessor in-order 63 e excluímos o nó original 63. A árvore fica
T = \bigl(71,\;(63,\;(44,\varnothing,\varnothing),\;\varnothing),\; (99,\;(80,\;(74,\varnothing,\varnothing),\;(98,\varnothing,\varnothing)),\;(120,\varnothing,\;(150,\varnothing,\varnothing))))\bigr),
sem necessidade de rotações (todos os FB em \{-1,0,+1\}).

Passo 10

Removemos agora 63 (que está na raiz da subárvore esquerda). Ele tem único filho 44, que o substitui, resultando em
\hat T = \bigl(71,\;(44,\varnothing,\varnothing),\; (99,\;(80,\;(74,\varnothing,\varnothing),\;(98,\varnothing,\varnothing)),\;(120,\varnothing,\;(150,\varnothing,\varnothing))))\bigr).
O nó 71 fica com FB =1-3=-2 e seu filho direito 99 tem FB =0: caso RR. Fazemos rotação simples à esquerda em 71, obtendo a árvore final:
T_{\text{final}} = \bigl(99,\;(71,\;(44,\varnothing,\varnothing),\;(80,\;(74,\varnothing,\varnothing),\;(98,\varnothing,\varnothing))),\;(120,\varnothing,\;(150,\varnothing,\varnothing)))\bigr).

Resposta

Resumo das rotações realizadas:
– Inserção de 71: LR em 99.
– Inserção de 74: LL em 99.
– Inserção de 59: RL em 44.
– Inserção de 150: RR em 80.
– Remoção de 63: RR em 71.
Árvore AVL final após todas as operações:
\bigl(99,\; (71,\;(44,\varnothing,\varnothing),\;(80,\;(74,\varnothing,\varnothing),\;(98,\varnothing,\varnothing))), (120,\;\varnothing,\;(150,\varnothing,\varnothing)) \bigr).

Exercícios relacionados