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 dá a sequência de chaves a inserir numa árvore AVL, na ordem:
.\n
O que é pedido:
O que é pedido:
- Inserir cada chave, uma a uma, mantendo a propriedade AVL (árvore binária de busca balanceada).
- Em cada passo mostrar o balanço de cada nó (fator de balanceamento) após a inserção e indicar as rotações que foram feitas (quando ocorrerem).
Observações úteis que peguei do enunciado: - A sequência tem duas ocorrências de
(duplicata). - Não há outra informação sobre política de duplicatas; portanto será adotada uma convenção consistente (ver Passo 2).
Passo 2
Regras, convenções e conceitos que vou usar (explicação didática e passo a passo, para você entender e poder reproduzir na prova).
- Convenção para duplicatas:
- Vou inserir chaves iguais sempre no ramo direito. Ou seja, se a chave a inserir é igual à de um nó, continuo a busca para a direita e insiro lá (isso é uma escolha comum e determina a forma da árvore).
- Definição de altura e fator de balanceamento:
- Altura de um nó: número de nós no caminho mais longo daquele nó até uma folha, contando o próprio nó. Para facilitar contas à mão, é prático usar a convenção: nó nulo tem altura
; uma folha tem altura . - Fator de balanceamento (denotado por
): vou usar
- Interpretação: se
o nó está balanceado; se ou o nó está desbalanceado e precisamos rotacionar.
- Tipos de desequilíbrios e correções (explicando passo a passo):
- Se um nó
fica com , o desbalanceamento pode ser: - Left-Left (LL): o filho esquerdo de
tem . Correção: rotação simples à direita em . - Left-Right (LR): o filho esquerdo de
tem . Correção: rotação dupla: primeiro rotação à esquerda no filho esquerdo, depois rotação à direita em .
- Left-Left (LL): o filho esquerdo de
- Se um nó
fica com , o desbalanceamento pode ser: - Right-Right (RR): o filho direito de
tem . Correção: rotação simples à esquerda em . - Right-Left (RL): o filho direito de
tem . Correção: rotação dupla: primeiro rotação à direita no filho direito, depois rotação à esquerda em .
- Right-Right (RR): o filho direito de
- Nas rotações, recomputa-se a altura e o
apenas nas constantes locais afetadas (os demais nós não mudam de subárvore).
- Notação que vou usar para mostrar as árvores:
- Vou representar cada nó como
. - E a árvore como
. Ex.: . - Sempre que fizer uma rotação vou mostrar a configuração antes e depois, e recomputar alturas e
.
Agora vamos inserir a sequência, um elemento por passo, mostrando cálculos detalhados.
Passo 3
Inserção de
(primeiro elemento).
- Árvore antes: vazia.
- Inserção:
vira a raiz, é folha. - Alturas: raiz tem altura
. - Fatores de balanceamento:
-
.
-
Nenhuma rotação necessária.
Passo 4
Inserção de
(segunda ocorrência, duplicata; pela convenção, vai para a direita).
- Árvore antes:
-
.
-
- Inserção: comparar com raiz
; igual → ir à direita; inserimos como filho direito da raiz. - Agora:
- nó direito é folha
. - raiz tem: altura(esquerda)=0, altura(direita)=1 → altura(raiz)=1+1=2.
-
.
- nó direito é folha
- Árvores e fatores:
- raiz:
com direita .
- raiz:
- Nenhuma rotação:
é aceitável.
Visualmente:
.
Passo 5
Inserção de
.
- Árvore antes:
- raiz
com right child .
- raiz
- Inserção:
→ vai à direita; comparar com segundo : → vai à direita dessa; insere como filho direito do segundo . - Após inserir, os nós afetados (subindo):
- nó novo:
(folha). - seu pai (segundo
): left altura , right → , altura . - raiz (primeiro
): left altura , right altura → . Aqui dá desbalanceamento.
- nó novo:
Identificar caso:
- O desbalanceamento em raiz é
e a inserção ocorreu no ramo direito do filho direito → caso Right-Right (RR).
Correção:
- Aplicar rotação simples à esquerda na raiz.
Mostrando antes e depois da rotação:
Antes (breve):
.
Rotação à esquerda em
:
sobe para raiz,
vira filho esquerdo de
,
permanece filho direito de
.
Depois:
- Estrutura: raiz
com esquerda e direita . - Calcular alturas e BF:
-
: folha → , altura . -
: folha → , altura . - raiz
: left height , right height → , altura .
-
Árvore final deste passo:
.
Rotações efetuadas neste passo: 1 rotação simples à esquerda (RR) na raiz.
Passo 6
Inserção de
.
- Árvore antes:
- raiz
com esquerda e direita .
- raiz
- Inserção:
→ à direita; → à direita de ; insere como filho direito de . - Atualizações subindo:
- novo nó
folha. -
: left height , right → , altura . - raiz
: left height , right height → , altura .
- novo nó
- Ambos os
estão em → sem rotação.
Árvore:
.
Passo 7
Inserção de
.
- Árvore antes:
- conforme passo anterior.
- Inserção:
→ direita; → direita; → direita; insere como filho direito de . - Atualizações:
-
: folha , altura . -
: left , right → , altura . -
: left , right → → desbalanceado. - Subimos para raiz
: left height , right height becomes → . O primeiro nó desbalanceado encontrado subindo é (a raiz neste caso).
-
Identificar caso no primeiro nó desbalanceado (raiz
):
- O desbalanceamento veio do lado direito do filho direito (inserção seguiu direita→direita) → caso Right-Right (RR) de novo.
Correção:
- Rotação simples à esquerda na raiz
.
Antes da rotação (esquemático):
.
Rotação à esquerda em
:
sobe para raiz;
vira filho esquerdo de
; a subárvore esquerda de
(nula) torna-se subárvore direita de
.
Depois:
- Estrutura: raiz
com esquerda (que tem à esquerda ) e direita com direita . - Recalcular BF e alturas:
- folhas
(ambas) e : , altura . -
(o que ficou na esquerda de ): left child altura , right nil → altura , . -
: left , right → , altura . - raiz
: left height , right height → .
- folhas
- Tudo balanceado.
Rotações efetuadas neste passo: 1 rotação simples à esquerda na raiz (RR).
Árvore resultante:
.
Passo 8
Inserção de
.
- Árvore antes: conforme final do Passo 7.
- Inserção:
→ à direita; → à direita; → à direita; insere como filho direito de . - Atualizações subindo:
-
: folha, altura , . -
: left , right → , altura . -
: left , right → → aqui o primeiro desbalanceamento ocorre em . - Subindo mais,
terá left height , right height becomes → (mas a correção é feita no primeiro nó desbalanceado ao subir, que é ).
-
Identificar caso em
:
-
tem e seu filho direito tem (ou direito pesado) → caso Right-Right (RR) em .
Correção:
- Rotação simples à esquerda em
.
Antes:
.
Rotação à esquerda em
:
sobe no lugar de
,
vira filho esquerdo de
.
Depois, recomputar:
-
: folha → , altura . -
: folha → . -
: left height , right height → . - Subir:
: left height (esquerda não mudou), right height → .
Árvore final deste passo:
.
Rotações efetuadas neste passo: 1 rotação simples à esquerda em
.
Passo 9
Inserção de
.
- Árvore antes: conforme fim do Passo 8.
- Inserção:
→ direita; → direita; → direita; insere como filho direito de . - Atualizações:
-
: folha, , altura . -
: left , right → , altura . -
: left (o tem altura ), right → , altura . -
: left height , right height → . Todos dentro de → sem rotações necessárias.
-
Árvore após inserção:
.
Passo 10
Inserção de
.
- Árvore antes: conforme Passo 9.
- Inserção:
→ direita; → direita; → direita; → direita; insere como filho direito de . - Atualizações:
-
: folha . -
: left , right → , altura . -
: left , right → → desbalanceado em . - Subindo,
terá left , right → . O primeiro nó desbalanceado subindo é (mais baixo na cadeia), precisamos corrigir ali primeiro.
-
Identificar caso em
:
-
tem e seu filho direito tem (direita pesada) → caso Right-Right (RR).
Correção:
- Rotação simples à esquerda em
.
Antes:
.
Rotação à esquerda em
:
sobe,
vira filho esquerdo de
; recomputar.
Depois:
-
: folha → , altura . -
: folha → , altura . -
: left , right → , altura . - Subir:
: left , right → . -
: left , right → . Tudo ok.
Árvore após rotação:
.
Rotações efetuadas neste passo: 1 rotação simples à esquerda em
.
Passo 11
Inserção de
.
- Árvore antes: conforme Passo 10.
- Inserção:
→ direita; → direita; → direita; → direita; insere como filho direito de . - Atualizações:
-
: folha, , altura . -
: left , right → , altura . -
: left , right → , altura . -
: left , right → → desbalanceado em .
-
- Identificar caso em
: - O filho direito de
é que tem (direita pesada) → caso Right-Right (RR).
- O filho direito de
Correção:
- Rotação simples à esquerda em
.
Antes (parcial):
.
Rotação à esquerda em
:
sobe para posição de
;
vira filho esquerdo de
; recomputar.
Depois:
- Subárvore esquerda de novo
é (que terá como esquerda). - Recalcular
: -
, , folhas ou altura 1/2 conforme posição; especificamente: -
: ficou como folha (ou possivelmente com ). -
: left child altura , right child was nil → , altura . -
: right child makes it , height . -
: left height (14 subtree), right height (429 subtree) → .
-
- Subir:
: left height , right height → . Tudo balanceado.
-
Árvore após rotação:
.
Rotações efetuadas neste passo: 1 rotação simples à esquerda em
.
Passo 12
Inserção de
.
- Árvore antes: conforme passo anterior.
- Inserção:
> , > , > , > → entra como filho direito de . - Atualizações:
-
: folha, . -
: left , right → , altura . -
: left , right → → desbalanceado em . - Subindo,
e também podem ter alterados, mas corrige-se no primeiro nó desbalanceado encontrado subindo, que é .
-
Identificar caso em
:
-
tem e seu filho direito tem → caso Right-Right (RR).
Correção:
- Rotação simples à esquerda em
.
Antes:
.
Rotação à esquerda em
:
sobe,
torna-se filho esquerdo de
.
Depois:
-
: folha → , altura . -
: folha → . -
: left , right → . - Subir:
: left height , right height → . -
: left height , right height (?) vamos recomputar: após rotação o right subtree de tem altura (132 subtree height 3?) Na verdade agora tem altura e left is height 2 => . Tudo ainda balanceado.
Árvore após rotação:
.
Rotações efetuadas neste passo: 1 rotação simples à esquerda em
.
Passo 13
Inserção de
.
- Árvore antes: conforme Passo 12.
- Inserção:
segue para a direita sucessivamente: , , , → insere como filho direito de . - Atualizações:
-
: folha, . -
: left , right → , altura . -
: left ( ), right ( agora altura ) → , altura . -
: left (subárvore 14 tem altura 2), right (subárvore 1430 altura 3) → , altura . -
: left height , right height → → desbalanceado. O primeiro nó desbalanceado subindo é (a raiz atual).
-
Identificar caso em
:
- A inserção ocorreu no lado direito da árvore da raiz; verificar filho direito de
que é : -
(direita pesada). Logo trata-se de um Right-Right (RR) no nó — correção por rotação simples à esquerda.
-
Correção:
- Rotação simples à esquerda em
.
Antes (esquemático):
.
Rotação à esquerda em
:
sobe para raiz;
vira filho esquerdo de
; subárvore esquerda de
(que é
) permanece como sua esquerda depois da rotação, e a antiga right-left passa conforme o algoritmo standard (neste caso
ganha a subárvore que era left de
se existisse — aqui
passa a ficar como left of 132 e 2 becomes left child of 132 with its right turned appropriately).
Depois da rotação, a estrutura mais alta fica centrada em
. Vamos recomputar alturas e BF de forma clara:
-
Subárvore esquerda de nova raiz
será ajustado: manterá como left child o seu antigo left e como right child a antiga left de (que era antes da rotação?). Atenção: devemos aplicar a rotação padrão à esquerda no nó cuja right child é .
Procedimento padrão para rotação esquerda eme : -
. -
.
Antes:-
, , . -
, , .
Aplicando:-
(ou seja, .right = 14). -
.
Resultado:- Nova raiz
. -
.left = . -
.left = (permanece), .right = . -
.right = subárvore com sua cadeia de direita .
-
Agora recomputar alturas e BF locais:
- Folhas:
altura , BF . -
: left (altura 1), right nil → altura , . -
: left (altura 1), right (altura 2) → altura , . -
: left nil, right → , altura . -
: left (1), right (2) → altura , . -
: left (altura 3), right (altura 3) → altura , .
Todos os nós agora com
.
Árvore final após última rotação (representação compacta com BF):
Rotações efetuadas neste passo: 1 rotação simples à esquerda em
(RR na raiz).
Resposta
Árvore AVL final (cada nó dado como
, mostrando a estrutura esquerda/direita):
Sequência de rotações efetuadas (na ordem em que ocorreram):
- Inserção de
: rotação simples à esquerda (RR) em . - Inserção de
: rotação simples à esquerda (RR) em . - Inserção de
: rotação simples à esquerda (RR) em . - Inserção de
: sem rotação. - Inserção de
: rotação simples à esquerda (RR) em . - Inserção de
: rotação simples à esquerda (RR) em . - Inserção de
: rotação simples à esquerda (RR) em . - Inserção de
: rotação simples à esquerda (RR) em .