- 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 em ordem as chaves
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
e
, 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
e depois
. Em ambas não há desbalanceamento; temos:
Passo 3
Inserimos
. A primeira árvore sem balancear seria
que dá fator de balanço em
:
e o filho esquerdo
tem FB
, caso LR. Aplicamos dupla rotação LR em
e obtemos
Passo 4
Agora inserimos
. Sem rotação, a árvore vira
com todos os fatores de balanço em
ou
.
Em seguida inserimos . Antes de balancear:
Em seguida inserimos
No nó
temos FB
e o filho esquerdo
tem FB
: caso LL. Aplicando rotação simples à direita em
, fica
Passo 5
Inserimos
. Vai para a direita de
, sem gerar desbalanceamento:
Passo 6
Inserimos
. Fica como filho esquerdo de
, e o nó
passa a ter FB
; seu filho direito
tem FB
: caso RL. Aplicando dupla rotação RL (primeiro à direita em
, depois à esquerda em
), obtemos
Passo 7
Inserimos
e depois
. Em ambos não ocorre desbalanceamento. A árvore final deste momento é
Passo 8
Inserimos
. Fica em
direita, e o nó
tem FB
com filho direito
de FB
: caso RR. Aplicamos rotação simples à esquerda em
e obtemos
Passo 9
Removemos
. Substituímos por seu sucessor in-order
e excluímos o nó original
. A árvore fica
sem necessidade de rotações (todos os FB em
).
Passo 10
Removemos agora
(que está na raiz da subárvore esquerda). Ele tem único filho
, que o substitui, resultando em
O nó
fica com FB
e seu filho direito
tem FB
: caso RR. Fazemos rotação simples à esquerda em
, obtendo a árvore final:
Resposta
Resumo das rotações realizadas:
– Inserção de : LR em
.
– Inserção de : LL em
.
– Inserção de : RL em
.
– Inserção de : RR em
.
– Remoção de : RR em
.
– Inserção de
– Inserção de
– Inserção de
– Inserção de
– Remoção de
Árvore AVL final após todas as operações: