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

Passo 1

O que o enunciado pede e o que ele dá.
  • O enunciado fornece a sequência de inserções na árvore: 17,11,141,67,91,1,44,111.
  • A tarefa é inserir esses valores, um a um, em uma árvore AVL vazia.
  • Para cada inserção deve-se:
    • Mostrar o fator de balanceamento (balance factor) de cada nó relevante ao final dessa inserção.
    • Mostrar as rotações efetuadas (se houver), indicando o tipo e em que nó elas ocorreram.
  • Situação inicial: árvore vazia.

Passo 2

Breve explicação das regras que vou usar (para você entender cada passo).
  • O fator de balanceamento de um nó é definido como
\text{bf} = \text{altura( filho esquerdo )} - \text{altura( filho direito )}.
  • Altura de um nó folha é 1. Altura de um nó com filhos é 1+\max(\text{altura(esq)},\text{altura(dir)}).
  • Uma árvore AVL exige que, para todo nó, \text{bf}\in\{-1,0,1\}. Se algum nó fica com |\text{bf}|>1 após uma inserção, é preciso rotacionar para restaurar o balanceamento.
  • Tipos de desequilíbrio e correção:
    • Caso LL (left-left): \text{bf}=2 e o filho esquerdo tem \text{bf}\in\{1,0\} → rotacao direita no nó desbalanceado.
    • Caso RR (right-right): \text{bf}=-2 e o filho direito tem \text{bf}\in\{-1,0\} → rotacao esquerda no nó desbalanceado.
    • Caso LR (left-right): \text{bf}=2 e o filho esquerdo tem \text{bf}=-1 → rotação esquerda no filho esquerdo seguida de rotação direita no nó desbalanceado.
    • Caso RL (right-left): \text{bf}=-2 e o filho direito tem \text{bf}=1 → rotação direita no filho direito seguida de rotação esquerda no nó desbalanceado.
  • Nas rotações, as subárvores são rearranjadas preservando a ordem in-order (propriedade BST) e recalcula-se alturas e bfs apenas nas partes afetadas.

Passo 3

Inserção de 17.
  • Árvore antes: vazia.
  • Inserindo 17 → vira a raiz.
  • Alturas e bfs:
    • \,17 é folha: \text{altura}(17)=1, \text{bf}(17)=0.
  • Nenhuma rotação necessária.
Estado da árvore:
\,17\\ (h=1,\\ bf=0).

Passo 4

Inserção de 11.
  • Caminho: 11<17 → vai para a esquerda de 17.
  • Atualização de alturas:
    • \,11 folha: h(11)=1,\\ bf(11)=0.
    • \,17: esquerda tem altura 1, direita tem altura 0 (nulo). Então h(17)=1+\max(1,0)=2.
    • \text{bf}(17)=1-0=1.
  • Todos os bfs estão em \{-1,0,1\} → sem rotações.
Estado da árvore:
\,17\\ (h=2,\\ bf=1)
├─ \,11\\ (h=1,\\ bf=0)

Passo 5

Inserção de 141.
  • Caminho: 141>17 → vai para a direita de 17.
  • Atualização de alturas:
    • \,141 folha: h(141)=1,\\ bf(141)=0.
    • \,17: esquerda h=1, direita h=1 h(17)=2, \text{bf}(17)=1-1=0.
  • Balanceamento ok, sem rotações.
Estado da árvore:
\,17\\ (h=2,\\ bf=0)
├─ \,11\\ (h=1,\\ bf=0)
└─ \,141\\ (h=1,\\ bf=0)

Passo 6

Inserção de 67.
  • Caminho: 67>17 → direita; 67<141 → esquerda de 141. Então 67 vira filho esquerdo de 141.
  • Atualização de alturas:
    • h(67)=1,\\ bf(67)=0.
    • 141: esquerda h=1, direita h=0 h(141)=2,\\ bf(141)=1.
    • 17: esquerda h=1, direita h=2 h(17)=3,\\ bf(17)=1-2=-1.
  • Todos os bfs em \{-1,0,1\} → sem rotações.
Estado da árvore:
\,17\\ (h=3,\\ bf=-1)
├─ \,11\\ (h=1,\\ bf=0)
└─ \,141\\ (h=2,\\ bf=1)
└─ \,67\\ (h=1,\\ bf=0)

Passo 7

Inserção de 91.
  • Caminho: 91>17 → direita; 91<141 → esquerda; 91>67 → direita de 67. Então 91 vira filho direito de 67.
  • Atualização local imediata:
    • h(91)=1,\\ bf(91)=0.
    • 67: esquerda h=0, direita h=1 h(67)=2,\\ bf(67)=0-1=-1.
    • 141: esquerda h=2 (subárvore com raiz 67), direita h=0 h(141)=3,\\ bf(141)=2-0=2.
  • Aqui encontramos um nó desbalanceado: \text{bf}(141)=2 (caso left-heavy).
  • Para decidir a rotação, olhamos o filho esquerdo 67: \text{bf}(67)=-1. Isso indica o caso LR (left-right).
  • Correção LR: primeiro executar rotação esquerda em 67, depois rotação direita em 141.
Explicando a dupla rotação (passo a passo, visual e intuitivo):
  1. Antes da correção (subárvore com raiz 141):
  • Subárvore (somente a parte relevante):
    • raiz 141 com filho esquerdo 67 que tem filho direito 91.
  1. Rotação à esquerda em 67:
  • 91 sobe para a posição de 67, 67 vira filho esquerdo de 91.
  • Resultado intermediário (subárvore):
    • raiz temporária 91, com esquerda 67 (sem filho direito) e direita nula relativa a essa subárvore.
  1. Rotação à direita em 141:
  • 91 sobe para a posição de 141, 141 vira filho direito de 91.
  • Subárvore corrigida tem raiz 91, com esquerda 67 e direita 141.
Recalcular alturas e bfs depois das rotações:
  • 67: agora folha ou com filhos nulos → h(67)=1,\\ bf(67)=0.
  • 141: agora folha → h(141)=1,\\ bf(141)=0.
  • 91: esquerda h=1, direita h=1 h(91)=2,\\ bf(91)=1-1=0.
  • Substituindo na raiz 17: esquerda h=1 (nó 11), direita h=2 (nó 91) → h(17)=3,\\ bf(17)=1-2=-1.
Resumo das rotações:
  • Tipo: LR no nó 141.
  • Equivalente a: rotação esquerda em 67 seguida de rotação direita em 141.
Estado da árvore após inserção e rotações:
\,17\\ (h=3,\\ bf=-1)
├─ \,11\\ (h=1,\\ bf=0)
└─ \,91\\ (h=2,\\ bf=0)
├─ \,67\\ (h=1,\\ bf=0)
└─ \,141\\ (h=1,\\ bf=0)

Passo 8

Inserção de 1.
  • Caminho: 1<17 → esquerda; 1<11 → esquerda de 11. Então 1 vira filho esquerdo de 11.
  • Atualização de alturas:
    • h(1)=1,\\ bf(1)=0.
    • 11: esquerda h=1, direita h=0 h(11)=2,\\ bf(11)=1-0=1.
    • 91 não alterou (h=2).
    • 17: esquerda h=2, direita h=2 h(17)=3,\\ bf(17)=2-2=0.
  • Todos os bfs agora são aceitáveis → sem rotações.
Estado da árvore:
\,17\\ (h=3,\\ bf=0)
├─ \,11\\ (h=2,\\ bf=1)
│ └─ \,1\\ (h=1,\\ bf=0)
└─ \,91\\ (h=2,\\ bf=0)
├─ \,67\\ (h=1,\\ bf=0)
└─ \,141\\ (h=1,\\ bf=0)

Passo 9

Inserção de 44.
  • Caminho: 44>17 → direita; 44<91 → esquerda; 44<67 → esquerda de 67. Então 44 vira filho esquerdo de 67.
  • Atualização de alturas:
    • h(44)=1,\\ bf(44)=0.
    • 67: esquerda h=1, direita h=0 h(67)=2,\\ bf(67)=1-0=1.
    • 141: continua h=1.
    • 91: esquerda h=2, direita h=1 h(91)=3,\\ bf(91)=2-1=1.
    • 17: esquerda h=2, direita h=3 h(17)=4,\\ bf(17)=2-3=-1.
  • Todos os bfs estão ainda em \{-1,0,1\} → sem rotações.
Estado parcial:
\,17\\ (h=4,\\ bf=-1)
├─ \,11\\ (h=2,\\ bf=1)
│ └─ \,1\\ (h=1,\\ bf=0)
└─ \,91\\ (h=3,\\ bf=1)
├─ \,67\\ (h=2,\\ bf=1)
│ └─ \,44\\ (h=1,\\ bf=0)
└─ \,141\\ (h=1,\\ bf=0)

Passo 10

Inserção de 111.
  • Caminho: 111>17 → direita; 111>91 → direita; 111<141 → esquerda de 141. Então 111 vira filho esquerdo de 141.
  • Atualização de alturas:
    • h(111)=1,\\ bf(111)=0.
    • 141: esquerda h=1, direita h=0 h(141)=2,\\ bf(141)=1-0=1.
    • 67: permanece h=2.
    • 91: esquerda h=2, direita h=2 h(91)=3,\\ bf(91)=2-2=0.
    • 17: esquerda h=2, direita h=3 h(17)=4,\\ bf(17)=2-3=-1.
  • Todos os bfs em \{-1,0,1\} → sem rotações.
Estado final da árvore (após todas as inserções):
  • \,1: h=1,\\ bf=0
  • \,11: h=2,\\ bf=1 (esquerda: 1)
  • \,44: h=1,\\ bf=0
  • \,67: h=2,\\ bf=1 (esquerda: 44)
  • \,111: h=1,\\ bf=0
  • \,141: h=2,\\ bf=1 (esquerda: 111)
  • \,91: h=3,\\ bf=0 (esquerda: 67, direita: 141)
  • \,17: h=4,\\ bf=-1 (esquerda: 11, direita: 91)
Visualização final (cada nó apresentada como \,valor\\ (h=altura,\\ bf=fator)):
\,17\\ (h=4,\\ bf=-1)
├─ \,11\\ (h=2,\\ bf=1)
│ └─ \,1\\ (h=1,\\ bf=0)
└─ \,91\\ (h=3,\\ bf=0)
├─ \,67\\ (h=2,\\ bf=1)
│ └─ \,44\\ (h=1,\\ bf=0)
└─ \,141\\ (h=2,\\ bf=1)
└─ \,111\\ (h=1,\\ bf=0)

Resposta

Rotações realizadas: LR em 141 (primeiro rotação à esquerda em 67, depois rotação à direita em 141).
Árvore final (cada nó indicado como valor (h=\text{altura},\\ bf=\text{fator de balanceamento})):
\,17\\ (h=4,\\ bf=-1)
├─ \,11\\ (h=2,\\ bf=1)
│ └─ \,1\\ (h=1,\\ bf=0)
└─ \,91\\ (h=3,\\ bf=0)
├─ \,67\\ (h=2,\\ bf=1)
│ └─ \,44\\ (h=1,\\ bf=0)
└─ \,141\\ (h=2,\\ bf=1)
└─ \,111\\ (h=1,\\ bf=0)

Exercícios relacionados