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:
1,1,2,3,5,8,13,21,34,55,89

Passo 1

O enunciado pede: inserir em uma árvore AVL a sequência de chaves
1,\,1,\,2,\,3,\,5,\,8,\,13,\,21,\,34,\,55,\,89
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: \,1\, 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 1 e altura de subárvore vazia igual a 0.
    • O fator de balanço de um nó é \displaystyle BF = \text{height(left)} - \text{height(right)}.
    • Para AVL, todo nó deve ter \,BF \in \{-1,0,1\}. Se algum nó fica com BF = 2 ou BF = -2, há desbalanceamento e aplicamos rotações.
  • Tipos de rotação (com a convenção acima):
    • Se BF = 2 (lado esquerdo pesado) e BF(\text{left child}) \ge 0: rotação simples à direita (Right rotation, caso Left-Left).
    • Se BF = 2 e BF(\text{left child}) = -1: rotação dupla (Left-Right): primeiro rotaciona à esquerda na subárvore esquerda, depois à direita no nó.
    • Se BF = -2 (lado direito pesado) e BF(\text{right child}) \le 0: rotação simples à esquerda (Left rotation, caso Right-Right).
    • Se BF = -2 e BF(\text{right child}) = +1: rotação dupla (Right-Left).
  • Em cada passo vou mostrar a posição onde a chave entra, os BF 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 \,1.
  • Árvore vazia -> insere \,1 como raiz.
  • Árvore atual (cada nó representado como \text{valor}_{(BF)}): \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; 1_{(0)}Explicação dos BF:
    • \,1 é folha: \text{height(left)}=0,\\ \text{height(right)}=0 \Rightarrow BF=0.
Nenhuma rotação necessária.

Passo 5

Inserção 2ª chave \,1 (duplicada, caída para a direita pela convenção).
  • Caminho: raiz \,1 -> igual -> vai para a direita -> insere como filho direito.
  • Árvore antes de qualquer rotação: 1_{(-1)} \quad \text{com filho direito } 1_{(0)}Cálculo dos BF:
    • Nó folha direito \,1: BF=0.
    • Raiz (primeiro \,1): \text{height(left)}=0,\\ \text{height(right)}=1 \Rightarrow BF=0-1=-1.
  • Como \,BF=-1 está permitido, nada a fazer.

Passo 6

Inserção 3ª chave \,2.
  • Caminho: raiz \,1 -> direita (porque 2>1) -> encontra \,1 (o segundo) -> 2>1 -> insere como filho direito desse nó.
  • Antes da rotação a cadeia é direita-direita: \,1 \to 1 \to 2.
  • Cálculos subindo:
    • Nó novo \,2: folha, BF=0.
    • Pai (segundo \,1): left height 0, right height 1 \Rightarrow BF=-1, height 2.
    • Raiz (primeiro \,1): left height 0, right height 2 \Rightarrow BF= -2 (desbalanceada).
  • Tipo de desbalanço: BF=-2 no nó raiz e BF(\text{right child})=-1 \Rightarrow caso Right-Right (RR) -> aplica rotação simples à esquerda na raiz.
Rotação à esquerda na raiz (esquematicamente):
  • Antes: 1_{(-2)}\;-\text{right}->\;1_{(-1)}\;-\text{right}->\;2_{(0)}
  • Depois (após left rotation no primeiro \,1): \quad 1_{(0)}\\\ \text{esquerda: }1_{(0)}\quad \text{direita: }2_{(0)}Onde o novo nó central 1 é o segundo \,1 (o que era filho direito), e o primeiro \,1 passa a ser filho esquerdo dele.
  • Cálculo dos BF finais:
    • Folhas \,1 e \,2: BF=0.
    • Nova raiz (segundo \,1): left height 1, right height 1 \Rightarrow BF=0.
Registro: rotações feitas até agora: [Left rotation at root (para tratar RR) ao inserir a terceira chave \,2].

Passo 7

Inserção 4ª chave \,3.
  • Caminho: 3>1 (raiz) -> vai para a direita ( 2) -> 3>2 -> insere como filho direito de \,2.
  • Antes de balanço final:
    • Novo nó \,3: BF=0.
    • \,2: left height 0, right height 1 \Rightarrow BF=-1, height 2.
    • Raiz (segundo \,1): left height 1, right height 2 \Rightarrow BF=1-2=-1.
  • Todos os BF ficam em \{-1,0,1\} -> sem rotações.
Árvore agora (com BF depois da inserção):
\begin{array}{c} \; 1_{(-1)}\\\ \text{left: }1_{(0)}\quad \text{right: }2_{(-1)}\\\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\\ \\ \text{right of }2:\\\ 3_{(0)} \end{array}

Passo 8

Inserção 5ª chave \,5.
  • Caminho: 5>1 (raiz) -> direita 2 -> direita 3 -> 5>3 -> insere como filho direito de \,3.
  • Subida dos BF:
    • \,5: folha, BF=0.
    • \,3: left 0, right 1 \Rightarrow BF=-1, height 2.
    • \,2: left 0, right height 2 \Rightarrow BF=0-2=-2 -> desbalanceado em \,2.
    • \,BF(\text{right child of }2)=BF(3)=-1 -> caso Right-Right (RR) no nó \,2.
  • Ação: rotação simples à esquerda em \,2.
Antes da rotação (subárvore afetada):
2_{(-2)} -\text{right}-> 3_{(-1)} -\text{right}-> 5_{(0)}
Depois da rotação (left rotation em \,2):
\quad 3_{(0)}\\\ \text{left: }2_{(0)}\quad \text{right: }5_{(0)}
  • Atualizando a ligação com a raiz: a raiz 1 tem agora como filho direito o nó 3.
  • Verificação final dos BF:
    • 2,5 folhas BF=0, 3 tem left height 1 right height 1 \Rightarrow BF=0.
    • Raiz 1: left height 1, right height 2 \Rightarrow BF=-1. Tudo ok.
Registro de rotações: adiciona [Left rotation at node 2 ao inserir \,5].
Árvore resultante (após inserção de \,5):
\begin{array}{c} 3_{(0)}\\\ \text{left: }1_{(-1)}\\ (\text{com left }1_{(0)})\qquad \text{right: }5_{(0)}\\\ \text{observação: }1\text{ tem right }2_{(0)}\\ \text{(após rotação interna)} \end{array}çãóçã
(mais claramente: raiz \,3; left subtree: root \,1 com filhos \,1 e \,2; right subtree: \,5.)

Passo 9

Inserção 6ª chave \,8.
  • Caminho: 8>3 -> vai para a direita ( 5) -> 8>5 -> insere como filho direito de \,5.
  • Subida dos BF:
    • \,8: folha BF=0.
    • \,5: left 0, right 1 \Rightarrow BF=-1, height 2.
    • \,3: left height 2 (subárvore com 1 e 2), right height 2 ( 5 altura 2) \Rightarrow BF=2-2=0. Tudo equilibrado.
  • Nenhuma rotação necessária.
Árvore (resumida):
  • raiz \,3_{(0)}
  • left subtree: \,1_{(0)} com children \,1_{(0)} e \,2_{(0)}
  • right subtree: \,5_{(-1)} com right child \,8_{(0)}

Passo 10

Inserção 7ª chave \,13.
  • Caminho: 13>3 -> direita 5 -> direita 8 -> 13>8 -> insere como filho direito de \,8.
  • Subida dos BF:
    • \,13: folha, BF=0.
    • \,8: left 0, right 1 \Rightarrow BF=-1, height 2.
    • \,5: left 0, right height 2 \Rightarrow BF=0-2=-2 -> desbalanceado em \,5.
    • BF(\text{right child }8)=-1 -> caso Right-Right no nó \,5.
  • Ação: rotação simples à esquerda em \,5.
Antes (subárvore 5):
5_{(-2)} -\text{right}-> 8_{(-1)} -\text{right}-> 13_{(0)}
Depois da rotação (left rotation em \,5):
\quad 8_{(0)}\\\ \text{left: }5_{(0)}\quad \text{right: }13_{(0)}
  • Agora ligar esse novo nó 8 como filho direito de 3.
  • Verificação:
    • 5,13 folhas BF=0, 8 tem left 1 right 1 \Rightarrow BF=0.
    • Raiz 3: left height 2, right height 2 \Rightarrow BF=0.
Registro de rotações: adiciona [Left rotation at node 5 ao inserir \,13].

Passo 11

Inserção 8ª chave \,21.
  • Caminho: 21>3 -> direita 8 -> direita 13 -> 21>13 -> insere como filho direito de \,13.
  • Subida:
    • \,21: folha, BF=0.
    • \,13: left 0, right 1 \Rightarrow BF=-1, height 2.
    • \,8: left 1 (node 5) right 2 (node 13) \Rightarrow BF=1-2=-1, height 3.
    • Raiz 3: left height 2, right height 3 \Rightarrow BF=2-3=-1.
  • Todos em \{-1,0,1\} -> sem rotação.
Árvore está equilibrada.

Passo 12

Inserção 9ª chave \,34.
  • Caminho: 34>3 -> 8 -> 13 -> 21 -> 34>21 -> insere como filho direito de \,21.
  • Subida:
    • \,34: folha BF=0.
    • \,21: left 0, right 1 \Rightarrow BF=-1, height 2.
    • \,13: left 0, right height 2 \Rightarrow BF=0-2=-2 -> desbalanceado em \,13.
    • BF(\text{right child }21)=-1 -> caso Right-Right no nó \,13.
  • Ação: left rotation em \,13.
Antes (subárvore 13):
13_{(-2)} -\text{right}-> 21_{(-1)} -\text{right}-> 34_{(0)}
Depois da rotação (left rotation em \,13):
\quad 21_{(0)}\\\ \text{left: }13_{(0)}\quad \text{right: }34_{(0)}
  • Ligar 21 como filho direito de 8.
  • Atualização dos BF em direção à raiz:
    • 13,34 folhas BF=0, 21 com left 1 right 1 BF=0.
    • 8: left height 1, right height 2 \Rightarrow BF=-1.
    • 3: left 2 right 3 \Rightarrow BF=-1.
  • Tudo equilibrado.
Registro de rotações: adiciona [Left rotation at node 13 ao inserir \,34].

Passo 13

Inserção 10ª chave \,55.
  • Caminho: 55>3 -> 8 -> 21 -> 34 -> 55>34 -> insere como filho direito de \,34.
  • Subida dos BF:
    • 55: folha BF=0.
    • 34: left 0, right 1 \Rightarrow BF=-1, height 2.
    • 21: left height 1 (13), right height 2 (34) \Rightarrow BF=1-2=-1, height 3.
    • 8: left height 1 (5), right height 3 (21) \Rightarrow BF=1-3=-2 -> desbalanceado em \,8.
    • Olhando o filho direito 21, temos BF(21)=-1 -> caso Right-Right no nó \,8.
  • Ação: left rotation em \,8.
Antes (subárvore raiz em 8):
8_{(-2)}\quad \text{com left }5_{(0)} \\ ;\\ \text{right }21_{(-1)}(13,34_{(-1)}\to 34\to55)
Depois da rotação (left rotation em \,8):
  • Novo nó raiz da subárvore passa a ser 21.
  • Estrutura resultante da subárvore: \quad 21_{(0)}\\\ \text{left: }8_{(0)}\\ (\text{com left }5_{(0)}\\ \text{e right }13_{(0)})\quad \text{right: }34_{(-1)}\\ (\text{com right }55_{(0)})
  • Agora ligar 21 como filho direito de 3.
  • Atualização final dos BF:
    • 5,13,55 folhas BF=0.
    • 8 tem left and right ambos altura 1 -> BF=0.
    • 34 tem left 0 right 1 -> BF=-1.
    • 21 tem left height 2 right height 2 -> BF=0.
    • Raiz 3: left height 2, right height 3 -> BF=-1.
Registro de rotações: adiciona [Left rotation at node 8 ao inserir \,55].

Passo 14

Inserção 11ª (última) chave \,89.
  • Caminho: 89>3 -> 21 -> 34 -> 55 -> 89>55 -> insere como filho direito de \,55.
  • Subida:
    • 89: folha BF=0.
    • 55: left 0, right 1 \Rightarrow BF=-1, height 2.
    • 34: left 0, right height 2 \Rightarrow BF=0-2=-2 -> desbalanceado em \,34.
    • BF(\text{right child }55)=-1 -> caso Right-Right em \,34.
  • Ação: left rotation em \,34.
Antes (subárvore em 34):
34_{(-2)} -\text{right}-> 55_{(-1)} -\text{right}-> 89_{(0)}
Depois da rotação (left rotation em \,34):
\quad 55_{(0)}\\\ \text{left: }34_{(0)}\quad \text{right: }89_{(0)}
  • Ligar esse 55 como filho direito de 21.
  • Atualização dos BF subindo até a raiz:
    • 34,89 folhas BF=0.
    • 55 tem left 1 right 1 \Rightarrow BF=0.
    • 21 tem left height 2 (8 subtree) e right height 2 (55 subtree) \Rightarrow BF=0.
    • Raiz 3 tem left height 2 e right height 3 \Rightarrow BF=-1.
  • Árvore final está balanceada.
Registro de rotações: adiciona [Left rotation at node 34 ao inserir \,89].

Resposta

Rotations (in insertion order):
Left rotation at node 1 when inserting 2.
Left rotation at node 2 when inserting 5.
Left rotation at node 5 when inserting 13.
Left rotation at node 13 when inserting 34.
Left rotation at node 8 when inserting 55.
Left rotation at node 34 when inserting 89.
Árvore AVL final (cada nó escrito como \text{valor}_{(BF)}, mostrado por níveis e ligações):
\begin{array}{c} 3_{(-1)}\\[4pt] \text{left: }1_{(0)}\quad\text{right: }21_{(0)} \\[4pt] \text{onde }1_{(0)}\text{ tem left }1_{(0)}\text{ e right }2_{(0)}\\[4pt] \text{e }21_{(0)}\text{ tem left }8_{(0)}\text{ e right }55_{(0)}\\[4pt] \text{onde }8_{(0)}\text{ tem left }5_{(0)}\text{ e right }13_{(0)}\\[4pt] \text{e }55_{(0)}\text{ tem left }34_{(0)}\text{ e right }89_{(0)} \end{array}]

Exercícios relacionados