Insira em uma árvore AVL as seguintes sequências de números, mostrando o balanço de cada nó e as rotações que foram feitas:
Passo 1
O que o enunciado pede e o que ele dá.
- O enunciado fornece a sequência de inserções na árvore:
. - A tarefa é inserir esses valores, um a um, em uma árvore AVL vazia.
- Para cada inserção deve-se:
- Mostrar o fator de balanceamento (balance factor) de cada nó relevante ao final dessa inserção.
- Mostrar as rotações efetuadas (se houver), indicando o tipo e em que nó elas ocorreram.
- Situação inicial: árvore vazia.
Passo 2
Breve explicação das regras que vou usar (para você entender cada passo).
- O fator de balanceamento de um nó é definido como
- Altura de um nó folha é
. Altura de um nó com filhos é . - Uma árvore AVL exige que, para todo nó,
. Se algum nó fica com após uma inserção, é preciso rotacionar para restaurar o balanceamento. - Tipos de desequilíbrio e correção:
- Caso LL (left-left):
e o filho esquerdo tem → rotacao direita no nó desbalanceado. - Caso RR (right-right):
e o filho direito tem → rotacao esquerda no nó desbalanceado. - Caso LR (left-right):
e o filho esquerdo tem → rotação esquerda no filho esquerdo seguida de rotação direita no nó desbalanceado. - Caso RL (right-left):
e o filho direito tem → rotação direita no filho direito seguida de rotação esquerda no nó desbalanceado.
- Caso LL (left-left):
- Nas rotações, as subárvores são rearranjadas preservando a ordem in-order (propriedade BST) e recalcula-se alturas e bfs apenas nas partes afetadas.
Passo 3
Inserção de
.
- Árvore antes: vazia.
- Inserindo
→ vira a raiz. - Alturas e bfs:
-
é folha: , .
-
- Nenhuma rotação necessária.
Estado da árvore:
.
Passo 4
Inserção de
.
- Caminho:
→ vai para a esquerda de . - Atualização de alturas:
-
folha: . -
: esquerda tem altura , direita tem altura (nulo). Então . -
.
-
- Todos os bfs estão em
→ sem rotações.
Estado da árvore:
├─
├─
Passo 5
Inserção de
.
- Caminho:
→ vai para a direita de . - Atualização de alturas:
-
folha: . -
: esquerda , direita → , .
-
- Balanceamento ok, sem rotações.
Estado da árvore:
├─
└─
├─
└─
Passo 6
Inserção de
.
- Caminho:
→ direita; → esquerda de . Então vira filho esquerdo de . - Atualização de alturas:
-
. -
: esquerda , direita → . -
: esquerda , direita → .
-
- Todos os bfs em
→ sem rotações.
Estado da árvore:
├─
└─
└─
├─
└─
└─
Passo 7
Inserção de
.
- Caminho:
→ direita; → esquerda; → direita de . Então vira filho direito de . - Atualização local imediata:
-
. -
: esquerda , direita → . -
: esquerda (subárvore com raiz ), direita → .
-
- Aqui encontramos um nó desbalanceado:
(caso left-heavy). - Para decidir a rotação, olhamos o filho esquerdo
: . Isso indica o caso LR (left-right). - Correção LR: primeiro executar rotação esquerda em
, depois rotação direita em .
Explicando a dupla rotação (passo a passo, visual e intuitivo):
- Antes da correção (subárvore com raiz
):
- Subárvore (somente a parte relevante):
- raiz
com filho esquerdo que tem filho direito .
- raiz
- Rotação à esquerda em
:
-
sobe para a posição de , vira filho esquerdo de . - Resultado intermediário (subárvore):
- raiz temporária
, com esquerda (sem filho direito) e direita nula relativa a essa subárvore.
- raiz temporária
- Rotação à direita em
:
-
sobe para a posição de , vira filho direito de . - Subárvore corrigida tem raiz
, com esquerda e direita .
Recalcular alturas e bfs depois das rotações:
-
: agora folha ou com filhos nulos → . -
: agora folha → . -
: esquerda , direita → . - Substituindo na raiz
: esquerda (nó ), direita (nó ) → .
Resumo das rotações:
- Tipo: LR no nó
. - Equivalente a: rotação esquerda em
seguida de rotação direita em .
Estado da árvore após inserção e rotações:
├─
└─
├─
└─
├─
└─
├─
└─
Passo 8
Inserção de
.
- Caminho:
→ esquerda; → esquerda de . Então vira filho esquerdo de . - Atualização de alturas:
-
. -
: esquerda , direita → . -
não alterou (h=2). -
: esquerda , direita → .
-
- Todos os bfs agora são aceitáveis → sem rotações.
Estado da árvore:
├─
│ └─
└─
├─
└─
├─
│ └─
└─
├─
└─
Passo 9
Inserção de
.
- Caminho:
→ direita; → esquerda; → esquerda de . Então vira filho esquerdo de . - Atualização de alturas:
-
. -
: esquerda , direita → . -
: continua . -
: esquerda , direita → . -
: esquerda , direita → .
-
- Todos os bfs estão ainda em
→ sem rotações.
Estado parcial:
├─
│ └─
└─
├─
│ └─
└─
├─
│ └─
└─
├─
│ └─
└─
Passo 10
Inserção de
.
- Caminho:
→ direita; → direita; → esquerda de . Então vira filho esquerdo de . - Atualização de alturas:
-
. -
: esquerda , direita → . -
: permanece . -
: esquerda , direita → . -
: esquerda , direita → .
-
- Todos os bfs em
→ sem rotações.
Estado final da árvore (após todas as inserções):
- Nó
: - Nó
: (esquerda: ) - Nó
: - Nó
: (esquerda: ) - Nó
: - Nó
: (esquerda: ) - Nó
: (esquerda: , direita: ) - Nó
: (esquerda: , direita: )
Visualização final (cada nó apresentada como
):
├─
│ └─
└─
├─
│ └─
└─
└─
├─
│ └─
└─
├─
│ └─
└─
└─
Resposta
Rotações realizadas: LR em
(primeiro rotação à esquerda em
, depois rotação à direita em
).
Árvore final (cada nó indicado como
):
├─
│ └─
└─
├─
│ └─
└─
└─
├─
│ └─
└─
├─
│ └─
└─
└─