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.

Passo 1

Beleza, vamos resolver esse exercício de árvores AVL! O enunciado pede para inserir os números 5, 7, 11, 17, 4, 6, 2, 1, 22 e 3, nessa ordem, e mostrar passo a passo como a árvore fica, indicando as rotações que acontecem. Vamos precisar entender o que é uma árvore AVL, que é um tipo de árvore binária de busca que se mantém balanceada usando rotações. Isso ajuda a garantir que as operações de busca, inserção e remoção sejam eficientes.

Passo 2

Primeiro, vamos inserir o 5 na árvore. Como a árvore está vazia, o 5 será a raiz.
5

Passo 3

Agora, inserimos o 7. Como 7 é maior que 5, ele vai para a direita de 5.
  5
   \
    7
A árvore ainda está balanceada, então nada mais precisa ser feito.

Passo 4

Em seguida, inserimos o 11. 11 é maior que 5 e também maior que 7, então vai para a direita de 7.
  5
   \
    7
     \
      11
Agora, verificamos o balanceamento. O nó 5 tem um fator de balanceamento de -2 (altura à direita 2, à esquerda 0), então precisamos fazer uma rotação à esquerda no nó 5.
Após a rotação:
    7
   / \
  5   11

Passo 5

Vamos inserir o 17. 17 é maior que 7 e maior que 11, então vai para a direita de 11.
    7
   / \
  5   11
         \
          17
A árvore está balanceada, sem necessidade de rotações.

Passo 6

Inserimos o 4. 4 é menor que 7 e menor que 5, então vai para a esquerda de 5.
    7
   / \
  5   11
 /     \
4       17
Balanceamento está ok, sem rotações necessárias.

Passo 7

Agora, inserimos o 6. 6 é menor que 7, mas maior que 5, então vai para a direita de 5.
    7
   / \
  5   11
 / \    \
4   6    17
A árvore continua balanceada.

Passo 8

Inserindo o 2. 2 é menor que 7, menor que 5 e menor que 4, então vai para a esquerda de 4.
      7
     / \
    5   11
   / \    \
  4   6    17
 /
2
Agora, o nó 5 tem um fator de balanceamento de +2 (esquerda 2, direita 1), que ainda está dentro do limite, então não precisa de rotação.

Passo 9

Vamos inserir o 1. 1 é menor que 7, 5, 4 e 2, então vai para a esquerda de 2.
        7
       / \
      5   11
     / \    \
    4   6    17
   /
  2
 /
1
Agora, o nó 4 tem fator de balanceamento de +2 (esquerda 2, direita 0), o que significa que precisamos fazer uma rotação à direita no nó 4.
Após a rota��ão:
        7
       / \
      5   11
     / \    \
    2   6    17
   / \
  1   4

Passo 10

Por fim, inserimos o 22. 22 é maior que 7, 11 e 17, então vai para a direita de 17.
        7
       / \
      5   11
     / \    \
    2   6    17
   / \        \
  1   4        22
A árvore está balanceada após essa inserção, sem necessidade de rotações.

Passo 11

Vamos inserir o 3. 3 é menor que 7, menor que 5, maior que 2 e menor que 4, então vai para a direita de 2.
        7
       / \
      5   11
     / \    \
    2   6    17
   / \        \
  1   4        22
       /
      3
Agora, o nó 2 tem fator de balanceamento de -1 (esquerda 1, direita 1), e o nó 5 tem fator de balanceamento de -1 também. A árvore continua balanceada, então não precisamos de rotações.

Resposta

A árvore AVL final após todas as inserções fica assim:
        7
       / \
      5   11
     / \    \
    2   6    17
   / \        \
  1   4        22
       /
      3
Foram realizadas rotações:
  1. Rotação à esquerda no nó 5 após inserir o 11.
  2. Rotação à direita no nó 4 após inserir o 1.

Exercícios relacionados

Implemente uma rotação dupla à esquerda sem utilizar uma rotação direita e depois uma esquerda.
Desenhe a árvore AVL formada pela inserção dos números de 1 a 12 em ordem crescente.
Prove que uma rotação dupla à direita pode ser obtida com uma rotação esquerda seguida de uma rotação direita.
Descreva a estrutura de uma árvore AVL formada pela inserção dos números de 1 a n em ordem crescente. Qual é a altura dessa árvore?