Desenhe a árvore AVL formada pela inserção dos números de 1 a 12 em ordem crescente.

Passo 1

Beleza, vamos resolver esse exercício juntos! A questão pede para desenhar uma árvore AVL resultante da inserção dos números de 1 a 12 em ordem crescente. Uma árvore AVL é um tipo de árvore binária de busca que mantém-se balanceada automaticamente após cada inserção ou remoção, garantindo que a altura das subárvores esquerda e direita de qualquer nó difira no máximo por 1.
Para resolver isso, vamos precisar entender como funciona a inserção em árvores binárias de busca e como a própria árvore AVL verifica e ajusta o balanceamento usando rotações. Vamos passo a passo inserir cada número de 1 a 12 e fazer os ajustes necessários para manter a árvore balanceada.

Passo 2

Vamos começar inserindo o número 1. Como a árvore está vazia, esse será o nó raiz.
1

Passo 3

Agora, inserimos o número 2. Como 2 é maior que 1, ele vai para a direita do nó 1.
  1
   \
    2
A árvore ainda está balanceada, pois a diferença de altura entre as subárvores esquerda e direita do nó 1 é 1, que está dentro do limite permitido.

Passo 4

Inserimos o número 3. Comparando com 1 e depois com 2, 3 é maior que ambos, então vai para a direita do 2.
  1
   \
    2
     \
      3
Agora, a árvore está desbalanceada. O nó 1 tem uma subárvore direita de altura 2 e nenhuma subárvore à esquerda, o que gera uma diferença de altura de 2. Para corrigir isso, realizamos uma rotação à esquerda no nó 1.
Após a rotação, a árvore fica assim:
    2
   / \
  1   3
Agora, a árvore está balanceada novamente.

Passo 5

Vamos inserir o número 4. Começando no nó 2, 4 é maior, vai para a direita do 2, depois maior que 3, vai para a direita do 3.
    2
   / \
  1   3
         \
          4
A diferença de altura no nó 2 é 2 (subárvore direita com altura 2 e esquerda com altura 1), então precisamos rebalancear. Fazemos uma rotação à esquerda no nó 2.
      3
     / \
    2   4
   /
  1
Agora, a árvore está balanceada.

Passo 6

Inserindo o número 5. Comparando com 3, depois com 4, e depois maior, vai para a direita de 4.
      3
     / \
    2   4
   /     \
  1       5
A árvore ainda está balanceada, já que a diferença de altura entre as subárvores de cada nó é no máximo 1.

Passo 7

Inserimos o número 6. Seguimos para a direita de 3, de 4, de 5, e insere à direita de 5.
      3
     / \
    2   4
   /     \
  1       5
             \
              6
Agora, o nó 4 tem uma subárvore direita com altura 2 e nenhuma à esquerda, diferença de altura 2. Realizamos uma rotação à esquerda no nó 4.
      3
     / \
    2   5
   /   / \
  1   4   6
A árvore está balanceada novamente.

Passo 8

Vamos inserir o número 7. Vai para a direita de 3, de 5, de 6, e insere à direita de 6.
      3
     / \
    2   5
   /   / \
  1   4   6
             \
              7
O nó 5 agora tem uma subárvore direita com altura 2 e a esquerda com altura 1, diferença de altura 1. A árvore continua balanceada.

Passo 9

Inserindo o número 8. Segue para a direita de 3, de 5, de 6, de 7, e insere à direita de 7.
      3
     / \
    2   5
   /   / \
  1   4   6
             \
              7
               \
                8
O nó 6 fica desbalanceado com diferença de altura 2. Realizamos uma rotação à esquerda no nó 6.
      3
     / \
    2   5
   /   / \
  1   4   7
         / \
        6   8
A árvore está balanceada novamente.

Passo 10

Agora, inserimos o número 9. Vai para a direita de 3, de 5, de 7, de 8, e insere à direita de 8.
      3
     / \
    2   5
   /   / \
  1   4   7
         / \
        6   8
               \
                9
O nó 7 tem uma subárvore direita com altura 2 e a esquerda com altura 1, diferença de altura 1. A árvore permanece balanceada.

Passo 11

Inserimos o número 10. Segue para a direita de 3, de 5, de 7, de 8, de 9, e insere à direita de 9.
      3
     / \
    2   5
   /   / \
  1   4   7
         / \
        6   8
               \
                9
                 \
                  10
O nó 8 fica desbalanceado. Fazemos uma rotação à esquerda no nó 8.
      3
     / \
    2   5
   /   / \
  1   4   7
         / \
        6   9
           / \
          8   10
A árvore está balanceada novamente.

Passo 12

Finalmente, inserimos o número 12. Vai para a direita de 3, de 5, de 7, de 9, de 10, e insere à direita de 10.
      3
     / \
    2   5
   /   / \
  1   4   7
         / \
        6   9
           / \
          8   10
               \
                12
O nó 10 está desbalanceado. Realizamos uma rotação à esquerda no nó 10.
      3
     / \
    2   5
   /   / \
  1   4   7
         / \
        6   9
           / \
          8   12
             /
            10
Agora, a árvore está completamente balanceada.

Resposta

A árvore AVL resultante após inserir os números de 1 a 12 em ordem crescente é:
        3
       / \
      2   5
     /   / \
    1   4   7
           / \
          6   9
             / \
            8   12
               /
              10

Exercícios relacionados

Prove ou dê um contraexemplo para as afirmações abaixo:
© Toda árvore estritamente binária é AVL.
Prove ou dê um contraexemplo para as afirmações abaixo:
(a) Toda árvore cheia é completa.
Implemente uma rotação dupla à esquerda sem utilizar uma rotação direita e depois uma esquerda.
Desenhe passo a passo a ávore AVL resultante da inserção dos elementos 5, 7, 11, e 3, nesta ordem, indicando as rotações que foram executadas.