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 enunciado pede: inserir, em uma árvore AVL vazia, a sequência de chaves
,
mostrando o fator de balanço de cada nó a cada etapa e indicar as rotações realizadas.
mostrando o fator de balanço de cada nó a cada etapa e indicar as rotações realizadas.
Informações dadas:
- Sequência de inserção (na ordem):
, , , , , , , . - A cada inserção devemos atualizar alturas e fatores de balanço e, se necessário, aplicar rotações AVL para restaurar o balanceamento.
O que eu vou apresentar nos passos seguintes:
- Uma breve aula sobre como funciona o AVL (como calcular altura e fator de balanço, como identificar os quatro casos de desequilíbrio).
- Para cada inserção: a árvore antes/ depois (representada textualmente), as alturas relevantes, os fatores de balanço calculados e a rotação (se houver) com explicação do porquê e como é feita.
Passo 2
Mini-aula rápida e prática (prometo ser curto e amigo):
Definições e convenções que vou usar:
- Altura de um nó: a altura de um nó é
mais a maior altura entre seus filhos; uma folha tem altura . Vou denotar altura por . - Fator de balanço (BF) no meu procedimento: vou usar
Exemplos: se um nó tem filho esquerdo de altura
e filho direito ausente (altura
), então
.
- Regras de balanceamento AVL: todo nó deve ter
. Se então o nó está desbalanceado. - Identificação de caso e rotações:
- Se
(esquerda pesada) e (o filho esquerdo está também para esquerda ou neutro) → caso Left-Left (LL): aplicar rotação simples para a direita em . - Se
e → caso Left-Right (LR): rotacionar à esquerda em e depois à direita em . - Se
(direita pesada) e (o filho direito também para direita ou neutro) → caso Right-Right (RR): aplicar rotação simples para a esquerda em . - Se
e → caso Right-Left (RL): rotacionar à direita em e depois à esquerda em .
- Se
Como fazer as rotações (visão prática e simples):
- Rotação à direita em
(LL): o filho esquerdo sobe e vira filho direito de . Se tinha subárvore direita, ela vira subárvore esquerda de . - Rotação à esquerda em
(RR): o filho direito sobe e vira filho esquerdo de . Se tinha subárvore esquerda, ela vira subárvore direita de .
Agora vamos aplicar tudo passo a passo nas inserções.
Passo 3
Inserção de
.
- Árvore antes: vazia.
- Inserimos
como raiz, sem filhos. - Alturas:
-
.
-
- Fatores de balanço:
-
- Desbalanceamento? Não (
). - Rotações: nenhuma.
Árvore atual (representação: nó(esq,dir)):
Passo 4
Inserção de
.
- Inserção:
→ vai para a esquerda de . - Estrutura:
- Raiz:
. - Filho esquerdo de
: (folha).
- Raiz:
- Alturas:
-
- Fatores:
-
(folha). -
-
- Desbalanceamento? Não (
). - Rotações: nenhuma.
Árvore atual:
Passo 5
Inserção de
.
- Caminho de inserção:
→ esquerda → → esquerda de . - Antes de balancear, estrutura:
com esquerda que tem esquerda . - Alturas:
-
- Fatores:
-
-
-
→ desbalanceado (porque ).
-
- Identificação do caso:
- O nó desbalanceado é
com (esquerda pesada). - Filho esquerdo
tem . Então é caso Left-Left (LL).
- O nó desbalanceado é
- Ação: aplicar rotação simples para a direita em
.
Rotação à direita em
:
- Antes:
com esquerda (esquerda ). - Após:
sobe como nova raiz; vira filho direito de ; permanece filho esquerdo de . - Nova estrutura:
- Raiz:
. -
.esq = . -
.dir = .
- Raiz:
- Atualização das alturas e BF:
-
- Rotações efetuadas: Rotação à direita em
(caso LL).
Árvore atual:
Passo 6
Inserção de
.
- Caminho de inserção:
→ ir à direita → → esquerda de . - Colocamos
como filho esquerdo de . - Alturas:
-
- Fatores:
-
- Desbalanceamento? Não (todos em
). - Rotações: nenhuma.
Árvore atual:
Passo 7
Inserção de
.
- Caminho:
→ direita → → esquerda → → esquerda de . - Inserimos
como filho esquerdo de . - Alturas:
-
- Fatores:
-
-
-
→ desbalanceado no nó . -
-
Também detecta desbalanceamento visualmente na raiz , mas primeiro corrigimos o primeiro desbalanceamento mais baixo (subindo).
-
- Identificação do caso para
: -
(esquerda pesada). - Filho esquerdo
tem → caso Left-Left (LL).
-
- Ação: rotacionar à direita em
.
Rotação à direita em
:
- Antes (subárvore de
): com esquerda (esquerda ). - Após:
sobe para o lugar de ; torna-se filho direito de ; fica como filho esquerdo de . - Reanexando ao pai:
era filho direito de ; depois da rotação, .dir passa a ser . - Nova estrutura local:
- Subárvore direita de
agora é .
- Subárvore direita de
- Atualização de alturas e BF locais:
-
- Rotação efetuada: Rotação à direita em
(caso LL).
Árvore atual:
Passo 8
Inserção de
.
- Caminho:
→ direita para ; → direita para ; → direita de . - Inserimos
como filho direito de . - Alturas:
-
- Fatores:
-
-
-
-
-
-
→ nó desbalanceado (BF ).
-
- Identificação do caso para
: -
(direita pesada). - Filho direito
tem → caso Right-Right (RR).
-
- Ação: aplicar rotação simples para a esquerda em
.
Rotação à esquerda em
:
- Antes:
com esquerda e direita . - Após a rotação:
-
sobe para a raiz do trecho. -
vira filho esquerdo de . - A subárvore esquerda de
(que era ) torna-se filho direito de .
-
- Nova estrutura:
- Raiz agora
. -
.esq = com .esq = e .dir = . -
.dir = com .dir = .
- Raiz agora
- Atualização de alturas e BF:
- Folhas
têm altura . -
-
-
- Folhas
- Rotação efetuada: Rotação à esquerda em
(caso RR).
Árvore atual:
Passo 9
Inserção de
.
- Caminho:
→ esquerda → → esquerda → → direita de . - Inserimos
como filho direito de . - Alturas:
-
- Fatores:
-
- Desbalanceamento? Não (tudo em
). - Rotações: nenhuma.
Árvore atual:
Passo 10
Inserção de
.
-
Caminho:
→ esquerda → → esquerda → → direita → → direita de . -
Inserimos
como filho direito de . -
Atualização de alturas (de baixo para cima):
-
-
Fatores:
-
-
-
→ nó desbalanceado. -
-
(isso também indica desbalanceamento na , mas trataremos bottom-up) -
-
-
-
Primeiro nó desbalanceado encontrado ao subir é
com (direita pesada). - Filho direito
tem . Portanto é caso Right-Right (RR) relativo a .
- Filho direito
-
Ação: aplicar rotação à esquerda em
.
Rotação à esquerda em
:
- Antes (subárvore com raiz
): . - Após:
-
sobe, torna-se filho esquerdo de , e permanece como filho direito de .
-
- Depois da rotação, reanexa essa subárvore como filho esquerdo de
(pois era filho esquerdo de ). - Nova subárvore esquerda de
é . - Atualização de alturas e BF locais:
-
- Agora subir e atualizar
: -
- Subir para
: -
- Tudo agora dentro de
, ou seja, balanceado.
Rotações efetuadas nesta etapa: Rotação à esquerda em
(caso RR no nó
).
Árvore final após todas as inserções:
Resposta
A árvore AVL final (com fator de balanço de cada nó entre parênteses) é:
Rotações realizadas (na ordem):
- Rotação direita em
(após inserir ) — caso LL. - Rotação direita em
(após inserir ) — caso LL. - Rotação esquerda em
(após inserir ) — caso RR. - Rotação esquerda em
(após inserir ) — caso RR.