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:
111,44,1,91,67,141,11,17

Passo 1

O enunciado pede: inserir, em uma árvore AVL vazia, a sequência de chaves
\,111,44,1,91,67,141,11,17\,,
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): \,111, \,44, \,1, \,91, \,67, \,141, \,11, \,17.
  • 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ó é 1 mais a maior altura entre seus filhos; uma folha tem altura 1. Vou denotar altura por \operatorname{h}(\cdot).
  • Fator de balanço (BF) no meu procedimento: vou usar
\text{BF}(x)=\operatorname{h}(\text{filho esquerdo de }x)-\operatorname{h}(\text{filho direito de }x).
Exemplos: se um nó tem filho esquerdo de altura \,2 e filho direito ausente (altura 0), então \text{BF}=2-0=2.
  • Regras de balanceamento AVL: todo nó deve ter \text{BF}\in\{-1,0,1\}. Se |\text{BF}|>1 então o nó está desbalanceado.
  • Identificação de caso e rotações:
    • Se \text{BF}(z)>1 (esquerda pesada) e \text{BF}(y)\ge 0 (o filho esquerdo y está também para esquerda ou neutro) → caso Left-Left (LL): aplicar rotação simples para a direita em z.
    • Se \text{BF}(z)>1 e \text{BF}(y)<0 → caso Left-Right (LR): rotacionar à esquerda em y e depois à direita em z.
    • Se \text{BF}(z)<-1 (direita pesada) e \text{BF}(y)\le 0 (o filho direito y também para direita ou neutro) → caso Right-Right (RR): aplicar rotação simples para a esquerda em z.
    • Se \text{BF}(z)<-1 e \text{BF}(y)>0 → caso Right-Left (RL): rotacionar à direita em y e depois à esquerda em z.
Como fazer as rotações (visão prática e simples):
  • Rotação à direita em z (LL): o filho esquerdo y sobe e z vira filho direito de y. Se y tinha subárvore direita, ela vira subárvore esquerda de z.
  • Rotação à esquerda em z (RR): o filho direito y sobe e z vira filho esquerdo de y. Se y tinha subárvore esquerda, ela vira subárvore direita de z.
Agora vamos aplicar tudo passo a passo nas inserções.

Passo 3

Inserção de \,111\,.
  • Árvore antes: vazia.
  • Inserimos \,111 como raiz, sem filhos.
  • Alturas:
    • \operatorname{h}(111)=1.
  • Fatores de balanço:
    • \text{BF}(111)=\operatorname{h}(\text{esq})-\operatorname{h}(\text{dir})=0-0=0.
  • Desbalanceamento? Não ( |0|\le1).
  • Rotações: nenhuma.
Árvore atual (representação: nó(esq,dir)):
(111(\varnothing,\varnothing))

Passo 4

Inserção de \,44\,.
  • Inserção: \,44<111 → vai para a esquerda de \,111.
  • Estrutura:
    • Raiz: \,111.
    • Filho esquerdo de \,111: \,44 (folha).
  • Alturas:
    • \operatorname{h}(44)=1.
    • \operatorname{h}(111)=1+\max(\operatorname{h}(44),0)=1+1=2.
  • Fatores:
    • \text{BF}(44)=0 (folha).
    • \text{BF}(111)=\operatorname{h}(44)-0=1-0=1.
  • Desbalanceamento? Não ( |1|\le1).
  • Rotações: nenhuma.
Árvore atual:
(111(44(\varnothing,\varnothing),\varnothing))

Passo 5

Inserção de \,1\,.
  • Caminho de inserção: \,1<111 → esquerda → \,1<44 → esquerda de 44.
  • Antes de balancear, estrutura: 111 com esquerda 44 que tem esquerda 1.
  • Alturas:
    • \operatorname{h}(1)=1.
    • \operatorname{h}(44)=1+\max(\operatorname{h}(1),0)=1+1=2.
    • \operatorname{h}(111)=1+\max(2,0)=3.
  • Fatores:
    • \text{BF}(1)=0.
    • \text{BF}(44)=\operatorname{h}(1)-0=1-0=1.
    • \text{BF}(111)=\operatorname{h}(44)-0=2-0=2. → desbalanceado (porque |2|>1).
  • Identificação do caso:
    • O nó desbalanceado é z=111 com \text{BF}(111)=2>1 (esquerda pesada).
    • Filho esquerdo y=44 tem \text{BF}(44)=1\ge0. Então é caso Left-Left (LL).
  • Ação: aplicar rotação simples para a direita em 111.
Rotação à direita em 111:
  • Antes: 111 com esquerda 44 (esquerda 1).
  • Após: 44 sobe como nova raiz; 111 vira filho direito de 44; 1 permanece filho esquerdo de 44.
  • Nova estrutura:
    • Raiz: 44.
    • 44.esq = 1.
    • 44.dir = 111.
  • Atualização das alturas e BF:
    • \operatorname{h}(1)=1,\\ \operatorname{h}(111)=1.
    • \operatorname{h}(44)=1+\max(1,1)=2.
    • \text{BF}(1)=0,\\ \text{BF}(111)=0,\\ \text{BF}(44)=1-1=0.
  • Rotações efetuadas: Rotação à direita em 111 (caso LL).
Árvore atual:
(44(1(\varnothing,\varnothing),111(\varnothing,\varnothing)))

Passo 6

Inserção de \,91\,.
  • Caminho de inserção: \,91>44 → ir à direita → \,91<111 → esquerda de 111.
  • Colocamos 91 como filho esquerdo de 111.
  • Alturas:
    • \operatorname{h}(91)=1.
    • \operatorname{h}(111)=1+\max(1,0)=2.
    • \operatorname{h}(1)=1.
    • \operatorname{h}(44)=1+\max(\operatorname{h}(1),\operatorname{h}(111))=1+\max(1,2)=3.
  • Fatores:
    • \text{BF}(91)=0.
    • \text{BF}(111)=\operatorname{h}(91)-0=1-0=1.
    • \text{BF}(1)=0.
    • \text{BF}(44)=\operatorname{h}(1)-\operatorname{h}(111)=1-2=-1.
  • Desbalanceamento? Não (todos em \{-1,0,1\}).
  • Rotações: nenhuma.
Árvore atual:
(44(1(\varnothing,\varnothing),111(91(\varnothing,\varnothing),\varnothing)))

Passo 7

Inserção de \,67\,.
  • Caminho: \,67>44 → direita → \,67<111 → esquerda → \,67<91 → esquerda de 91.
  • Inserimos 67 como filho esquerdo de 91.
  • Alturas:
    • \operatorname{h}(67)=1.
    • \operatorname{h}(91)=1+\max(1,0)=2.
    • \operatorname{h}(111)=1+\max(2,0)=3.
    • \operatorname{h}(1)=1.
    • \operatorname{h}(44)=1+\max(1,3)=4.
  • Fatores:
    • \text{BF}(67)=0.
    • \text{BF}(91)=\operatorname{h}(67)-0=1-0=1.
    • \text{BF}(111)=\operatorname{h}(91)-0=2-0=2. → desbalanceado no nó 111.
    • \text{BF}(1)=0.
    • \text{BF}(44)=\operatorname{h}(1)-\operatorname{h}(111)=1-3=-2. Também detecta desbalanceamento visualmente na raiz 44, mas primeiro corrigimos o primeiro desbalanceamento mais baixo (subindo).
  • Identificação do caso para z=111:
    • \text{BF}(111)=2>1 (esquerda pesada).
    • Filho esquerdo y=91 tem \text{BF}(91)=1\ge0 → caso Left-Left (LL).
  • Ação: rotacionar à direita em 111.
Rotação à direita em 111:
  • Antes (subárvore de 111): 111 com esquerda 91 (esquerda 67).
  • Após: 91 sobe para o lugar de 111; 111 torna-se filho direito de 91; 67 fica como filho esquerdo de 91.
  • Reanexando ao pai: 111 era filho direito de 44; depois da rotação, 44.dir passa a ser 91.
  • Nova estrutura local:
    • Subárvore direita de 44 agora é 91(67,\;111).
  • Atualização de alturas e BF locais:
    • \operatorname{h}(67)=1,\\ \operatorname{h}(111)=1.
    • \operatorname{h}(91)=1+\max(1,1)=2.
    • \operatorname{h}(44)=1+\max(1,2)=3.
    • \text{BF}(67)=0,\\ \text{BF}(111)=0,\\ \text{BF}(91)=1-1=0,\\ \text{BF}(44)=1-2=-1.
  • Rotação efetuada: Rotação à direita em 111 (caso LL).
Árvore atual:
(44(1(\varnothing,\varnothing),91(67(\varnothing,\varnothing),111(\varnothing,\varnothing))))

Passo 8

Inserção de \,141\,.
  • Caminho: \,141>44 → direita para 91; \,141>91 → direita para 111; \,141>111 → direita de 111.
  • Inserimos 141 como filho direito de 111.
  • Alturas:
    • \operatorname{h}(141)=1.
    • \operatorname{h}(111)=1+\max(0,1)=2.
    • \operatorname{h}(67)=1.
    • \operatorname{h}(91)=1+\max(1,2)=3.
    • \operatorname{h}(1)=1.
    • \operatorname{h}(44)=1+\max(1,3)=4.
  • Fatores:
    • \text{BF}(141)=0.
    • \text{BF}(111)=0-1=-1.
    • \text{BF}(67)=0.
    • \text{BF}(91)=\operatorname{h}(67)-\operatorname{h}(111)=1-2=-1.
    • \text{BF}(1)=0.
    • \text{BF}(44)=\operatorname{h}(1)-\operatorname{h}(91)=1-3=-2. → nó 44 desbalanceado (BF -2).
  • Identificação do caso para z=44:
    • \text{BF}(44)=-2< -1 (direita pesada).
    • Filho direito y=91 tem \text{BF}(91)=-1\le 0 → caso Right-Right (RR).
  • Ação: aplicar rotação simples para a esquerda em 44.
Rotação à esquerda em 44:
  • Antes: 44 com esquerda 1 e direita 91(67,111( \varnothing,141 )).
  • Após a rotação:
    • 91 sobe para a raiz do trecho.
    • 44 vira filho esquerdo de 91.
    • A subárvore esquerda de 91 (que era 67) torna-se filho direito de 44.
  • Nova estrutura:
    • Raiz agora 91.
    • 91.esq = 44 com 44.esq = 1 e 44.dir = 67.
    • 91.dir = 111 com 111.dir = 141.
  • Atualização de alturas e BF:
    • Folhas 1,67,141 têm altura 1.
    • \operatorname{h}(111)=1+\max(0,1)=2,\\ \text{BF}(111)=0-1=-1.
    • \operatorname{h}(44)=1+\max(1,1)=2,\\ \text{BF}(44)=1-1=0.
    • \operatorname{h}(91)=1+\max(2,2)=3,\\ \text{BF}(91)=2-2=0.
  • Rotação efetuada: Rotação à esquerda em 44 (caso RR).
Árvore atual:
(91(44(1(\varnothing,\varnothing),67(\varnothing,\varnothing)),111(\varnothing,141(\varnothing,\varnothing))))

Passo 9

Inserção de \,11\,.
  • Caminho: \,11<91 → esquerda → \,11<44 → esquerda → \,11>1 → direita de 1.
  • Inserimos 11 como filho direito de 1.
  • Alturas:
    • \operatorname{h}(11)=1.
    • \operatorname{h}(1)=1+\max(0,1)=2.
    • \operatorname{h}(67)=1,\\ \operatorname{h}(111)=2,\\ \operatorname{h}(44)=1+\max(2,1)=3.
    • \operatorname{h}(91)=1+\max(3,2)=4.
  • Fatores:
    • \text{BF}(11)=0.
    • \text{BF}(1)=0-1=-1.
    • \text{BF}(67)=0.
    • \text{BF}(111)=0-1=-1.
    • \text{BF}(44)=\operatorname{h}(1)-\operatorname{h}(67)=2-1=1.
    • \text{BF}(91)=\operatorname{h}(44)-\operatorname{h}(111)=3-2=1.
  • Desbalanceamento? Não (tudo em \{-1,0,1\}).
  • Rotações: nenhuma.
Árvore atual:
(91(44(1(\varnothing,11(\varnothing,\varnothing)),67(\varnothing,\varnothing)),111(\varnothing,141(\varnothing,\varnothing))))

Passo 10

Inserção de \,17\,.
  • Caminho: \,17<91 → esquerda → \,17<44 → esquerda → \,17>1 → direita → \,17>11 → direita de 11.
  • Inserimos 17 como filho direito de 11.
  • Atualização de alturas (de baixo para cima):
    • \operatorname{h}(17)=1.
    • \operatorname{h}(11)=1+\max(0,1)=2.
    • \operatorname{h}(1)=1+\max(0,\operatorname{h}(11))=1+2=3.
    • \operatorname{h}(67)=1.
    • \operatorname{h}(44)=1+\max(\operatorname{h}(1),\operatorname{h}(67))=1+\max(3,1)=4.
    • \operatorname{h}(111)=2,\\ \operatorname{h}(91)=1+\max(4,2)=5.
  • Fatores:
    • \text{BF}(17)=0.
    • \text{BF}(11)=0-1=-1.
    • \text{BF}(1)=0-\operatorname{h}(11)=0-2=-2. → nó 1 desbalanceado.
    • \text{BF}(67)=0.
    • \text{BF}(44)=\operatorname{h}(1)-\operatorname{h}(67)=3-1=2. (isso também indica desbalanceamento na 44, mas trataremos bottom-up)
    • \text{BF}(111)=0-1=-1.
    • \text{BF}(91)=\operatorname{h}(44)-\operatorname{h}(111)=4-2=2.
  • Primeiro nó desbalanceado encontrado ao subir é z=1 com \text{BF}(1)=-2 (direita pesada).
    • Filho direito y=11 tem \text{BF}(11)=-1\le 0. Portanto é caso Right-Right (RR) relativo a z=1.
  • Ação: aplicar rotação à esquerda em 1.
Rotação à esquerda em 1:
  • Antes (subárvore com raiz 1): 1(\varnothing,11(\varnothing,17)).
  • Após:
    • 11 sobe, 1 torna-se filho esquerdo de 11, e 17 permanece como filho direito de 11.
  • Depois da rotação, reanexa essa subárvore como filho esquerdo de 44 (pois 1 era filho esquerdo de 44).
  • Nova subárvore esquerda de 44 é 11(1,17).
  • Atualização de alturas e BF locais:
    • \operatorname{h}(1)=1,\\ \operatorname{h}(17)=1,\\ \operatorname{h}(11)=1+\max(1,1)=2,
    • \text{BF}(1)=0,\\ \text{BF}(17)=0,\\ \text{BF}(11)=1-1=0.
  • Agora subir e atualizar 44:
    • \operatorname{h}(67)=1.
    • \operatorname{h}(44)=1+\max(\operatorname{h}(11),\operatorname{h}(67))=1+\max(2,1)=3.
    • \text{BF}(44)=\operatorname{h}(11)-\operatorname{h}(67)=2-1=1.
  • Subir para 91:
    • \operatorname{h}(111)=2.
    • \operatorname{h}(91)=1+\max(3,2)=4.
    • \text{BF}(91)=3-2=1.
  • Tudo agora dentro de \{-1,0,1\}, ou seja, balanceado.
Rotações efetuadas nesta etapa: Rotação à esquerda em 1 (caso RR no nó 1).
Árvore final após todas as inserções:
(91(44(11(1(\varnothing,\varnothing),17(\varnothing,\varnothing)),67(\varnothing,\varnothing)),111(\varnothing,141(\varnothing,\varnothing))))

Resposta

A árvore AVL final (com fator de balanço de cada nó entre parênteses) é:
91 (BF 0) raiz
\quadesq: 44 (BF 1)
\quad\quadesq: 11 (BF 0)
\quad\quad\quadesq: 1 (BF 0)
\quad\quad\quaddir: 17 (BF 0)
\quad\quaddir: 67 (BF 0)
\quaddir: 111 (BF -1)
\quad\quaddir: 141 (BF 0)
Rotações realizadas (na ordem):
  1. Rotação direita em 111 (após inserir 1) — caso LL.
  2. Rotação direita em 111 (após inserir 67) — caso LL.
  3. Rotação esquerda em 44 (após inserir 141) — caso RR.
  4. Rotação esquerda em 1 (após inserir 17) — caso RR.

Exercícios relacionados