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,5,14,42,132,429,1430,4862,16796

Passo 1

O enunciado dá a sequência de chaves a inserir numa árvore AVL, na ordem:
\,1,1,2,5,14,42,132,429,1430,4862,16796.\n
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 \,1 (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).
  1. 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).
  1. 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 0; uma folha tem altura 1.
  • Fator de balanceamento (denotado por \mathrm{BF}): vou usar
\mathrm{BF}(\text{nó}) = \text{altura(esquerda)} - \text{altura(direita)}.ó
  • Interpretação: se \mathrm{BF}\in\{-1,0,1\} o nó está balanceado; se \mathrm{BF}\le -2 ou \mathrm{BF}\ge 2 o nó está desbalanceado e precisamos rotacionar.
  1. Tipos de desequilíbrios e correções (explicando passo a passo):
  • Se um nó X fica com \mathrm{BF}=+2, o desbalanceamento pode ser:
    • Left-Left (LL): o filho esquerdo de X tem \mathrm{BF}\ge 0. Correção: rotação simples à direita em X.
    • Left-Right (LR): o filho esquerdo de X tem \mathrm{BF}=-1. Correção: rotação dupla: primeiro rotação à esquerda no filho esquerdo, depois rotação à direita em X.
  • Se um nó X fica com \mathrm{BF}=-2, o desbalanceamento pode ser:
    • Right-Right (RR): o filho direito de X tem \mathrm{BF}\le 0. Correção: rotação simples à esquerda em X.
    • Right-Left (RL): o filho direito de X tem \mathrm{BF}=+1. Correção: rotação dupla: primeiro rotação à direita no filho direito, depois rotação à esquerda em X.
  • Nas rotações, recomputa-se a altura e o \mathrm{BF} apenas nas constantes locais afetadas (os demais nós não mudam de subárvore).
  1. Notação que vou usar para mostrar as árvores:
  • Vou representar cada nó como (\text{valor},\mathrm{BF}=\dots).
  • E a árvore como (\text{raiz},\mathrm{BF})\;[\text{esquerda}]\;[\text{direita}]. Ex.: (5,\mathrm{BF}=0)\;[(2,\mathrm{BF}=0)]\;[(8,\mathrm{BF}=0)].
  • Sempre que fizer uma rotação vou mostrar a configuração antes e depois, e recomputar alturas e \mathrm{BF}.
Agora vamos inserir a sequência, um elemento por passo, mostrando cálculos detalhados.

Passo 3

Inserção de \,1 (primeiro elemento).
  • Árvore antes: vazia.
  • Inserção: \,1 vira a raiz, é folha.
  • Alturas: raiz tem altura 1.
  • Fatores de balanceamento:
    • (1,\mathrm{BF}=0).
Nenhuma rotação necessária.

Passo 4

Inserção de \,1 (segunda ocorrência, duplicata; pela convenção, vai para a direita).
  • Árvore antes:
    • (1,\mathrm{BF}=0).
  • Inserção: comparar com raiz \,1; igual → ir à direita; inserimos como filho direito da raiz.
  • Agora:
    • nó direito é folha (1,\mathrm{BF}=0).
    • raiz tem: altura(esquerda)=0, altura(direita)=1 → altura(raiz)=1+1=2.
    • \mathrm{BF}(\text{raiz}) = 0 - 1 = -1.
  • Árvores e fatores:
    • raiz: (1,\mathrm{BF}=-1) com direita (1,\mathrm{BF}=0).
  • Nenhuma rotação: \mathrm{BF}=-1 é aceitável.
Visualmente:
(1,\mathrm{BF}=-1)\;[\varnothing]\;[(1,\mathrm{BF}=0)].

Passo 5

Inserção de \,2.
  • Árvore antes:
    • raiz = (1,\mathrm{BF}=-1) com right child (1,\mathrm{BF}=0).
  • Inserção: 2>1 → vai à direita; comparar com segundo 1: 2>1 → vai à direita dessa; insere como filho direito do segundo 1.
  • Após inserir, os nós afetados (subindo):
    • nó novo: (2,\mathrm{BF}=0) (folha).
    • seu pai (segundo 1): left altura 0, right 1 \mathrm{BF}=0-1=-1, altura 2.
    • raiz (primeiro 1): left altura 0, right altura 2 \mathrm{BF}=0-2=-2. Aqui dá desbalanceamento.
Identificar caso:
  • O desbalanceamento em raiz é \mathrm{BF}=-2 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):
(1_a,\mathrm{BF}=-2)\;[\varnothing]\;[(1_b,\mathrm{BF}=-1)\;[\varnothing]\;[(2,\mathrm{BF}=0)]].
Rotação à esquerda em 1_a: 1_b sobe para raiz, 1_a vira filho esquerdo de 1_b, 2 permanece filho direito de 1_b.
Depois:
  • Estrutura: raiz (1_b) com esquerda (1_a) e direita (2).
  • Calcular alturas e BF:
    • (1_a): folha → \mathrm{BF}=0, altura 1.
    • (2): folha → \mathrm{BF}=0, altura 1.
    • raiz (1_b): left height 1, right height 1 \mathrm{BF}=1-1=0, altura 2.
Árvore final deste passo:
(1_b,\mathrm{BF}=0)\;[(1_a,\mathrm{BF}=0)]\;[(2,\mathrm{BF}=0)].
Rotações efetuadas neste passo: 1 rotação simples à esquerda (RR) na raiz.

Passo 6

Inserção de \,5.
  • Árvore antes:
    • raiz (1,\mathrm{BF}=0) com esquerda (1,\mathrm{BF}=0) e direita (2,\mathrm{BF}=0).
  • Inserção: 5>1 → à direita; 5>2 → à direita de 2; insere como filho direito de 2.
  • Atualizações subindo:
    • novo nó (5,\mathrm{BF}=0) folha.
    • (2): left height 0, right 1 \mathrm{BF}=-1, altura 2.
    • raiz (1): left height 1, right height 2 \mathrm{BF}=1-2=-1, altura 3.
  • Ambos os \mathrm{BF} estão em \{-1,0,1\} → sem rotação.
Árvore:
(1,\mathrm{BF}=-1)\;[(1,\mathrm{BF}=0)]\;[(2,\mathrm{BF}=-1)\;[\varnothing]\;[(5,\mathrm{BF}=0)]].

Passo 7

Inserção de \,14.
  • Árvore antes:
    • conforme passo anterior.
  • Inserção: 14>1 → direita; 14>2 → direita; 14>5 → direita; insere como filho direito de 5.
  • Atualizações:
    • (14): folha \mathrm{BF}=0, altura 1.
    • (5): left 0, right 1 \mathrm{BF}=-1, altura 2.
    • (2): left 0, right 2 \mathrm{BF}=0-2=-2 → desbalanceado.
    • Subimos para raiz (1): left height 1, right height becomes 3 \mathrm{BF}=1-3=-2. O primeiro nó desbalanceado encontrado subindo é (1) (a raiz neste caso).
Identificar caso no primeiro nó desbalanceado (raiz (1)):
  • 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 (1).
Antes da rotação (esquemático):
(1,\mathrm{BF}=-2)\;[(1,\mathrm{BF}=0)]\;[(2,\mathrm{BF}=-2)\;[\varnothing]\;[(5,\mathrm{BF}=-1)\;[\varnothing]\;[(14,\mathrm{BF}=0)]]].
Rotação à esquerda em (1): (2) sobe para raiz; (1) vira filho esquerdo de (2); a subárvore esquerda de (2) (nula) torna-se subárvore direita de (1).
Depois:
  • Estrutura: raiz (2) com esquerda (1) (que tem à esquerda (1)) e direita (5) com direita (14).
  • Recalcular BF e alturas:
    • folhas (1) (ambas) e (14): \mathrm{BF}=0, altura 1.
    • (1\\ \text{pai}) (o que ficou na esquerda de (2)): left child (1) altura 1, right nil → altura 2, \mathrm{BF}=1-0=1.
    • (5): left 0, right 1 \mathrm{BF}=-1, altura 2.
    • raiz (2): left height 2, right height 2 \mathrm{BF}=0.
  • Tudo balanceado.
Rotações efetuadas neste passo: 1 rotação simples à esquerda na raiz (RR).
Árvore resultante:
(2,\mathrm{BF}=0)\;[(1,\mathrm{BF}=1)\;[(1,\mathrm{BF}=0)]\;[\varnothing]]\;[(5,\mathrm{BF}=-1)\;[\varnothing]\;[(14,\mathrm{BF}=0)]].

Passo 8

Inserção de \,42.
  • Árvore antes: conforme final do Passo 7.
  • Inserção: 42>2 → à direita; 42>5 → à direita; 42>14 → à direita; insere como filho direito de (14).
  • Atualizações subindo:
    • (42): folha, altura 1, \mathrm{BF}=0.
    • (14): left 0, right 1 \mathrm{BF}=-1, altura 2.
    • (5): left 0, right 2 \mathrm{BF}=0-2=-2 → aqui o primeiro desbalanceamento ocorre em (5).
    • Subindo mais, (2) terá left height 2, right height becomes 3 \mathrm{BF}=2-3=-1 (mas a correção é feita no primeiro nó desbalanceado ao subir, que é (5)).
Identificar caso em (5):
  • (5) tem \mathrm{BF}=-2 e seu filho direito (14) tem \mathrm{BF}=-1 (ou direito pesado) → caso Right-Right (RR) em (5).
Correção:
  • Rotação simples à esquerda em (5).
Antes:
(5,\mathrm{BF}=-2)\;[\varnothing]\;[(14,\mathrm{BF}=-1)\;[\varnothing]\;[(42,\mathrm{BF}=0)]].
Rotação à esquerda em (5): (14) sobe no lugar de (5), (5) vira filho esquerdo de (14).
Depois, recomputar:
  • (5): folha → \mathrm{BF}=0, altura 1.
  • (42): folha → \mathrm{BF}=0.
  • (14): left height 1, right height 1 \mathrm{BF}=0.
  • Subir: (2): left height 2 (esquerda não mudou), right height 2 \mathrm{BF}=0.
Árvore final deste passo:
(2,\mathrm{BF}=0)\;[(1,\mathrm{BF}=1)\;[(1,\mathrm{BF}=0)]\;[\varnothing]]\;[(14,\mathrm{BF}=0)\;[(5,\mathrm{BF}=0)]\;[(42,\mathrm{BF}=0)]].
Rotações efetuadas neste passo: 1 rotação simples à esquerda em (5).

Passo 9

Inserção de \,132.
  • Árvore antes: conforme fim do Passo 8.
  • Inserção: 132>2 → direita; 132>14 → direita; 132>42 → direita; insere como filho direito de (42).
  • Atualizações:
    • (132): folha, \mathrm{BF}=0, altura 1.
    • (42): left 0, right 1 \mathrm{BF}=-1, altura 2.
    • (14): left 1 (o (5) tem altura 1), right 2 \mathrm{BF}=1-2=-1, altura 3.
    • (2): left height 2, right height 3 \mathrm{BF}=2-3=-1. Todos dentro de \{-1,0,1\} → sem rotações necessárias.
Árvore após inserção:
(2,\mathrm{BF}=-1)\;[(1,\mathrm{BF}=1)\;[(1,\mathrm{BF}=0)]\;[\varnothing]]\;[(14,\mathrm{BF}=-1)\;[(5,\mathrm{BF}=0)]\;[(42,\mathrm{BF}=-1)\;[\varnothing]\;[(132,\mathrm{BF}=0)]]].

Passo 10

Inserção de \,429.
  • Árvore antes: conforme Passo 9.
  • Inserção: 429>2 → direita; 429>14 → direita; 429>42 → direita; 429>132 → direita; insere como filho direito de (132).
  • Atualizações:
    • (429): folha \mathrm{BF}=0.
    • (132): left 0, right 1 \mathrm{BF}=-1, altura 2.
    • (42): left 0, right 2 \mathrm{BF}=0-2=-2 → desbalanceado em (42).
    • Subindo, (14) terá left 1, right 3 \mathrm{BF}=1-3=-2. O primeiro nó desbalanceado subindo é (42) (mais baixo na cadeia), precisamos corrigir ali primeiro.
Identificar caso em (42):
  • (42) tem \mathrm{BF}=-2 e seu filho direito (132) tem \mathrm{BF}=-1 (direita pesada) → caso Right-Right (RR).
Correção:
  • Rotação simples à esquerda em (42).
Antes:
(42,\mathrm{BF}=-2)\;[\varnothing]\;[(132,\mathrm{BF}=-1)\;[\varnothing]\;[(429,\mathrm{BF}=0)]].
Rotação à esquerda em (42): (132) sobe, (42) vira filho esquerdo de (132); recomputar.
Depois:
  • (42): folha → \mathrm{BF}=0, altura 1.
  • (429): folha → \mathrm{BF}=0, altura 1.
  • (132): left 1, right 1 \mathrm{BF}=0, altura 2.
  • Subir: (14): left 1, right 2 \mathrm{BF}=1-2=-1.
  • (2): left 2, right 3 \mathrm{BF}=2-3=-1. Tudo ok.
Árvore após rotação:
(2,\mathrm{BF}=-1)\;[(1,\mathrm{BF}=1)\;[(1,\mathrm{BF}=0)]\;[\varnothing]]\;[(14,\mathrm{BF}=-1)\;[(5,\mathrm{BF}=0)]\;[(132,\mathrm{BF}=0)\;[(42,\mathrm{BF}=0)]\;[(429,\mathrm{BF}=0)]]].
Rotações efetuadas neste passo: 1 rotação simples à esquerda em (42).

Passo 11

Inserção de \,1430.
  • Árvore antes: conforme Passo 10.
  • Inserção: 1430>2 → direita; 1430>14 → direita; 1430>132 → direita; 1430>429 → direita; insere como filho direito de (429).
  • Atualizações:
    • (1430): folha, \mathrm{BF}=0, altura 1.
    • (429): left 0, right 1 \mathrm{BF}=-1, altura 2.
    • (132): left 1, right 2 \mathrm{BF}=1-2=-1, altura 3.
    • (14): left 1, right 3 \mathrm{BF}=1-3=-2 → desbalanceado em (14).
  • Identificar caso em (14):
    • O filho direito de (14) é (132) que tem \mathrm{BF}=-1 (direita pesada) → caso Right-Right (RR).
Correção:
  • Rotação simples à esquerda em (14).
Antes (parcial):
(14,\mathrm{BF}=-2)\;[(5,\mathrm{BF}=0)]\;[(132,\mathrm{BF}=-1)\;[(42,\mathrm{BF}=0)]\;[(429,\mathrm{BF}=-1)\;[\varnothing]\;[(1430,\mathrm{BF}=0)]]].
Rotação à esquerda em (14): (132) sobe para posição de (14); (14) vira filho esquerdo de (132); recomputar.
Depois:
  • Subárvore esquerda de novo (132) é (14) (que terá (5) como esquerda).
  • Recalcular \mathrm{BF}:
    • (5), (42), (1430) folhas ou altura 1/2 conforme posição; especificamente:
      • (5): ficou como folha (ou possivelmente com \mathrm{BF}=0).
      • (14): left child (5) altura 1, right child was nil → \mathrm{BF}=1-0=1, altura 2.
      • (429): right child (1430) makes it \mathrm{BF}=-1, height 2.
      • (132): left height 2 (14 subtree), right height 2 (429 subtree) → \mathrm{BF}=0.
    • Subir: (2): left height 2, right height 3 \mathrm{BF}=2-3=-1. Tudo balanceado.
Árvore após rotação:
(2,\mathrm{BF}=-1)\;[(1,\mathrm{BF}=1)\;[(1,\mathrm{BF}=0)]\;[\varnothing]]\;[(132,\mathrm{BF}=0)\;[(14,\mathrm{BF}=1)\;[(5,\mathrm{BF}=0)]\;[\varnothing]]\;[(429,\mathrm{BF}=-1)\;[\varnothing]\;[(1430,\mathrm{BF}=0)]]].
Rotações efetuadas neste passo: 1 rotação simples à esquerda em (14).

Passo 12

Inserção de \,4862.
  • Árvore antes: conforme passo anterior.
  • Inserção: 4862 > 2, > 132, > 429, > 1430 → entra como filho direito de (1430).
  • Atualizações:
    • (4862): folha, \mathrm{BF}=0.
    • (1430): left 0, right 1 \mathrm{BF}=-1, altura 2.
    • (429): left 0, right 2 \mathrm{BF}=0-2=-2 → desbalanceado em (429).
    • Subindo, (132) e (2) também podem ter \mathrm{BF} alterados, mas corrige-se no primeiro nó desbalanceado encontrado subindo, que é (429).
Identificar caso em (429):
  • (429) tem \mathrm{BF}=-2 e seu filho direito (1430) tem \mathrm{BF}=-1 → caso Right-Right (RR).
Correção:
  • Rotação simples à esquerda em (429).
Antes:
(429,\mathrm{BF}=-2)\;[\varnothing]\;[(1430,\mathrm{BF}=-1)\;[\varnothing]\;[(4862,\mathrm{BF}=0)]].
Rotação à esquerda em (429): (1430) sobe, (429) torna-se filho esquerdo de (1430).
Depois:
  • (429): folha → \mathrm{BF}=0, altura 1.
  • (4862): folha → \mathrm{BF}=0.
  • (1430): left 1, right 1 \mathrm{BF}=0.
  • Subir: (132): left height 2, right height 2 \mathrm{BF}=0.
  • (2): left height 2, right height 3 (?) vamos recomputar: após rotação o right subtree de 2 tem altura 3 (132 subtree height 3?) Na verdade (132) agora tem altura 3 e 2 left is height 2 => \mathrm{BF}(2)=2-3=-1. Tudo ainda balanceado.
Árvore após rotação:
(2,\mathrm{BF}=-1)\;[(1,\mathrm{BF}=1)\;[(1,\mathrm{BF}=0)]\;[\varnothing]]\;[(132,\mathrm{BF}=0)\;[(14,\mathrm{BF}=1)\;[(5,\mathrm{BF}=0)]\;[\varnothing]]\;[(1430,\mathrm{BF}=0)\;[(429,\mathrm{BF}=0)]\;[(4862,\mathrm{BF}=0)]]].
Rotações efetuadas neste passo: 1 rotação simples à esquerda em (429).

Passo 13

Inserção de \,16796.
  • Árvore antes: conforme Passo 12.
  • Inserção: 16796 segue para a direita sucessivamente: >2, >132, >1430, >4862 → insere como filho direito de (4862).
  • Atualizações:
    • (16796): folha, \mathrm{BF}=0.
    • (4862): left 0, right 1 \mathrm{BF}=-1, altura 2.
    • (1430): left 1 ( 429), right 2 ( 4862 agora altura 2) → \mathrm{BF}=1-2=-1, altura 3.
    • (132): left 2 (subárvore 14 tem altura 2), right 3 (subárvore 1430 altura 3) → \mathrm{BF}=2-3=-1, altura 4.
    • (2): left height 2, right height 4 \mathrm{BF}=2-4=-2 → desbalanceado. O primeiro nó desbalanceado subindo é (2) (a raiz atual).
Identificar caso em (2):
  • A inserção ocorreu no lado direito da árvore da raiz; verificar filho direito de (2) que é (132):
    • \mathrm{BF}(\,132)= -1 (direita pesada). Logo trata-se de um Right-Right (RR) no nó (2) — correção por rotação simples à esquerda.
Correção:
  • Rotação simples à esquerda em (2).
Antes (esquemático):
(2,\mathrm{BF}=-2)\;[(1,\mathrm{BF}=1)]\;[(132,\mathrm{BF}=-1)\;[(14,\mathrm{BF}=1)\;[(5,\mathrm{BF}=0)]\;[\varnothing]]\;[(1430,\mathrm{BF}=-1)\;[(429,\mathrm{BF}=0)]\;[(4862,\mathrm{BF}=-1)\;[\varnothing]\;[(16796,\mathrm{BF}=0)]]]].
Rotação à esquerda em (2): (132) sobe para raiz; (2) vira filho esquerdo de (132); subárvore esquerda de (132) (que é (14)) permanece como sua esquerda depois da rotação, e a antiga right-left passa conforme o algoritmo standard (neste caso (2) ganha a subárvore que era left de (132) se existisse — aqui (14) 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 (132). Vamos recomputar alturas e BF de forma clara:
  • Subárvore esquerda de nova raiz (132) será (2) ajustado: (2) manterá como left child o seu antigo left (1) e como right child a antiga left de (132) (que era (14) antes da rotação?). Atenção: devemos aplicar a rotação padrão à esquerda no nó (2) cuja right child é (132).
    Procedimento padrão para rotação esquerda em X=2 e Y=132:
    • X.\text{right} \leftarrow Y.\text{left}.
    • Y.\text{left} \leftarrow X.
    Antes:
    • X=2, X.\text{left} = 1, X.\text{right}=132.
    • Y=132, Y.\text{left}=14, Y.\text{right}=1430.
    Aplicando:
    • X.\text{right} \leftarrow 14 (ou seja, 2.right = 14).
    • Y.\text{left} \leftarrow 2.
    Resultado:
    • Nova raiz Y=132.
    • 132.left = 2.
    • 2.left = 1 (permanece), 2.right = 14.
    • 132.right = 1430 subárvore com sua cadeia de direita 4862 \to 16796.
Agora recomputar alturas e BF locais:
  • Folhas: 1,5,429,16796 altura 1, BF 0.
  • (14): left 5 (altura 1), right nil → altura 2, \mathrm{BF}=1-0=1.
  • (2): left 1 (altura 1), right 14 (altura 2) → altura 1+2=3, \mathrm{BF}=1-2=-1.
  • (4862): left nil, right 16796 \mathrm{BF}=0-1=-1, altura 2.
  • (1430): left 429 (1), right 4862 (2) → altura 3, \mathrm{BF}=1-2=-1.
  • (132): left 2 (altura 3), right 1430 (altura 3) → altura 4, \mathrm{BF}=3-3=0.
Todos os nós agora com \mathrm{BF}\in\{-1,0,1\}.
Árvore final após última rotação (representação compacta com BF):
(132,\mathrm{BF}=0)\;[(2,\mathrm{BF}=-1)\;[(1,\mathrm{BF}=1)\;[(1,\mathrm{BF}=0)]\;[\varnothing]]\;[(14,\mathrm{BF}=1)\;[(5,\mathrm{BF}=0)]\;[\varnothing]]]\;[(1430,\mathrm{BF}=-1)\;[(429,\mathrm{BF}=0)]\;[(4862,\mathrm{BF}=-1)\;[\varnothing]\;[(16796,\mathrm{BF}=0)]]].
Rotações efetuadas neste passo: 1 rotação simples à esquerda em (2) (RR na raiz).

Resposta

Árvore AVL final (cada nó dado como (\text{valor},\mathrm{BF}), mostrando a estrutura esquerda/direita):
(132,\mathrm{BF}=0)\;[(2,\mathrm{BF}=-1)\;[(1,\mathrm{BF}=1)\;[(1,\mathrm{BF}=0)]\;[\varnothing]]\;[(14,\mathrm{BF}=1)\;[(5,\mathrm{BF}=0)]\;[\varnothing]]]\;[(1430,\mathrm{BF}=-1)\;[(429,\mathrm{BF}=0)]\;[(4862,\mathrm{BF}=-1)\;[\varnothing]\;[(16796,\mathrm{BF}=0)]]]
Sequência de rotações efetuadas (na ordem em que ocorreram):
  1. Inserção de \,2: rotação simples à esquerda (RR) em (1).
  2. Inserção de \,14: rotação simples à esquerda (RR) em (1).
  3. Inserção de \,42: rotação simples à esquerda (RR) em (5).
  4. Inserção de \,132: sem rotação.
  5. Inserção de \,429: rotação simples à esquerda (RR) em (42).
  6. Inserção de \,1430: rotação simples à esquerda (RR) em (14).
  7. Inserção de \,4862: rotação simples à esquerda (RR) em (429).
  8. Inserção de \,16796: rotação simples à esquerda (RR) em (2).

Exercícios relacionados