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 a sequência de chaves
mostrando o fator de balanço (balance) de cada nó e as rotações que foram feitas.
Informações dadas relevantes:
mostrando o fator de balanço (balance) de cada nó e as rotações que foram feitas.
Informações dadas relevantes:
- A sequência de inserção é exatamente as onze chaves acima (observe que há uma repetição:
aparece duas vezes). - Deve mostrar, para cada passo de inserção, os fatores de balanço resultantes e quaisquer rotações aplicadas.
Passo 2
Rápida revisão do que vou usar (passo didático, para você conseguir fazer na prova):
- Inserção em árvore de busca binária (BST): cada nova chave vai para a folha apropriada comparando-se com os nós (menor à esquerda, maior à direita). Se duas chaves forem iguais, é preciso adotar uma convenção (vou definir isso no próximo passo).
- Definição de altura e fator de balanço:
- Vou usar altura de folha igual a
e altura de subárvore vazia igual a . - O fator de balanço de um nó é
. - Para AVL, todo nó deve ter
. Se algum nó fica com ou , há desbalanceamento e aplicamos rotações.
- Vou usar altura de folha igual a
- Tipos de rotação (com a convenção acima):
- Se
(lado esquerdo pesado) e : rotação simples à direita (Right rotation, caso Left-Left). - Se
e : rotação dupla (Left-Right): primeiro rotaciona à esquerda na subárvore esquerda, depois à direita no nó. - Se
(lado direito pesado) e : rotação simples à esquerda (Left rotation, caso Right-Right). - Se
e : rotação dupla (Right-Left).
- Se
- Em cada passo vou mostrar a posição onde a chave entra, os
dos nós afetados (subindo até a raiz) e a rotação (se ocorrer), com a árvore antes e depois da rotação.
Passo 3
Convenção sobre chaves iguais: como o enunciado não diz o contrário, adoto a convenção comum “insere chaves iguais na subárvore direita”. Ou seja, ao comparar, se a nova chave for igual ao nó atual, vou para a direita. Essa escolha é arbitrária, mas precisa ficar explícita para que a sequência de inserções seja determinística.
Passo 4
Inserção 1ª chave
.
- Árvore vazia -> insere
como raiz. - Árvore atual (cada nó representado como
): Explicação dos : - Nó
é folha: .
- Nó
Nenhuma rotação necessária.
Passo 5
Inserção 2ª chave
(duplicada, caída para a direita pela convenção).
- Caminho: raiz
-> igual -> vai para a direita -> insere como filho direito. - Árvore antes de qualquer rotação:
Cálculo dos : - Nó folha direito
: . - Raiz (primeiro
): .
- Nó folha direito
- Como
está permitido, nada a fazer.
Passo 6
Inserção 3ª chave
.
- Caminho: raiz
-> direita (porque ) -> encontra (o segundo) -> -> insere como filho direito desse nó. - Antes da rotação a cadeia é direita-direita:
. - Cálculos subindo:
- Nó novo
: folha, . - Pai (segundo
): left height , right height , height . - Raiz (primeiro
): left height , right height (desbalanceada).
- Nó novo
- Tipo de desbalanço:
no nó raiz e caso Right-Right (RR) -> aplica rotação simples à esquerda na raiz.
Rotação à esquerda na raiz (esquematicamente):
- Antes:
- Depois (após left rotation no primeiro
): Onde o novo nó central é o segundo (o que era filho direito), e o primeiro passa a ser filho esquerdo dele. - Cálculo dos
finais: - Folhas
e : . - Nova raiz (segundo
): left height , right height .
- Folhas
Registro: rotações feitas até agora: [Left rotation at root (para tratar RR) ao inserir a terceira chave
].
Passo 7
Inserção 4ª chave
.
- Caminho:
(raiz) -> vai para a direita ( ) -> -> insere como filho direito de . - Antes de balanço final:
- Novo nó
: . - Nó
: left height , right height , height . - Raiz (segundo
): left height , right height .
- Novo nó
- Todos os
ficam em -> sem rotações.
Árvore agora (com
depois da inserção):
Passo 8
Inserção 5ª chave
.
- Caminho:
(raiz) -> direita -> direita -> -> insere como filho direito de . - Subida dos
: -
: folha, . -
: left 0, right 1 , height 2. -
: left 0, right height 2 -> desbalanceado em . -
-> caso Right-Right (RR) no nó .
-
- Ação: rotação simples à esquerda em
.
Antes da rotação (subárvore afetada):
Depois da rotação (left rotation em
):
- Atualizando a ligação com a raiz: a raiz
tem agora como filho direito o nó . - Verificação final dos
: -
folhas , tem left height right height . - Raiz
: left height , right height . Tudo ok.
-
Registro de rotações: adiciona [Left rotation at node
ao inserir
].
Árvore resultante (após inserção de
):
(mais claramente: raiz
; left subtree: root
com filhos
e
; right subtree:
.)
Passo 9
Inserção 6ª chave
.
- Caminho:
-> vai para a direita ( ) -> -> insere como filho direito de . - Subida dos
: -
: folha . -
: left 0, right 1 , height 2. -
: left height (subárvore com 1 e 2), right height ( altura 2) . Tudo equilibrado.
-
- Nenhuma rotação necessária.
Árvore (resumida):
- raiz
- left subtree:
com children e - right subtree:
com right child
Passo 10
Inserção 7ª chave
.
- Caminho:
-> direita -> direita -> -> insere como filho direito de . - Subida dos
: -
: folha, . -
: left 0, right 1 , height 2. -
: left 0, right height 2 -> desbalanceado em . -
-> caso Right-Right no nó .
-
- Ação: rotação simples à esquerda em
.
Antes (subárvore 5):
Depois da rotação (left rotation em
):
- Agora ligar esse novo nó
como filho direito de . - Verificação:
-
folhas , tem left 1 right 1 . - Raiz
: left height 2, right height 2 .
-
Registro de rotações: adiciona [Left rotation at node
ao inserir
].
Passo 11
Inserção 8ª chave
.
- Caminho:
-> direita -> direita -> -> insere como filho direito de . - Subida:
-
: folha, . -
: left 0, right 1 , height 2. -
: left 1 (node 5) right 2 (node 13) , height 3. - Raiz
: left height 2, right height 3 .
-
- Todos em
-> sem rotação.
Árvore está equilibrada.
Passo 12
Inserção 9ª chave
.
- Caminho:
-> -> -> -> -> insere como filho direito de . - Subida:
-
: folha . -
: left 0, right 1 , height 2. -
: left 0, right height 2 -> desbalanceado em . -
-> caso Right-Right no nó .
-
- Ação: left rotation em
.
Antes (subárvore 13):
Depois da rotação (left rotation em
):
- Ligar
como filho direito de . - Atualização dos
em direção à raiz: -
folhas , com left 1 right 1 . -
: left height 1, right height 2 . -
: left 2 right 3 .
-
- Tudo equilibrado.
Registro de rotações: adiciona [Left rotation at node
ao inserir
].
Passo 13
Inserção 10ª chave
.
- Caminho:
-> -> -> -> -> insere como filho direito de . - Subida dos
: -
: folha . -
: left 0, right 1 , height 2. -
: left height 1 (13), right height 2 (34) , height 3. -
: left height 1 (5), right height 3 (21) -> desbalanceado em . - Olhando o filho direito
, temos -> caso Right-Right no nó .
-
- Ação: left rotation em
.
Antes (subárvore raiz em
):
Depois da rotação (left rotation em
):
- Novo nó raiz da subárvore passa a ser
. - Estrutura resultante da subárvore:
- Agora ligar
como filho direito de . - Atualização final dos
: -
folhas . -
tem left and right ambos altura -> . -
tem left 0 right 1 -> . -
tem left height 2 right height 2 -> . - Raiz
: left height 2, right height 3 -> .
-
Registro de rotações: adiciona [Left rotation at node
ao inserir
].
Passo 14
Inserção 11ª (última) chave
.
- Caminho:
-> -> -> -> -> insere como filho direito de . - Subida:
-
: folha . -
: left 0, right 1 , height 2. -
: left 0, right height 2 -> desbalanceado em . -
-> caso Right-Right em .
-
- Ação: left rotation em
.
Antes (subárvore em
):
Depois da rotação (left rotation em
):
- Ligar esse
como filho direito de . - Atualização dos
subindo até a raiz: -
folhas . -
tem left 1 right 1 . -
tem left height 2 (8 subtree) e right height 2 (55 subtree) . - Raiz
tem left height 2 e right height 3 .
-
- Árvore final está balanceada.
Registro de rotações: adiciona [Left rotation at node
ao inserir
].
Resposta
Rotations (in insertion order):
Left rotation at node when inserting
.
Left rotation at node when inserting
.
Left rotation at node when inserting
.
Left rotation at node when inserting
.
Left rotation at node when inserting
.
Left rotation at node when inserting
.
Left rotation at node
Left rotation at node
Left rotation at node
Left rotation at node
Left rotation at node
Left rotation at node
Árvore AVL final (cada nó escrito como
, mostrado por níveis e ligações):