Questão de Tecnologia da Informação · FGV TJ-MS 2024 (nº 26)

Uma Árvore AVL é uma árvore de busca binária que se auto-balanceia para garantir que a diferença de altura entre as subárvores esquerda e direita de qualquer nó (chamado Fator de Balanceamento) nunca seja maior que 1. Isso mantém a árvore "equilibrada" e as operações eficientes. A busca em pré-ordem (ou pré-fixada) visita os nós na seguinte sequência: Nó atual, depois a subárvore esquerda, e por fim a subárvore direita.

Vamos construir a árvore AVL passo a passo, inserindo os números e realizando as rotações necessárias para manter o balanceamento. O Fator de Balanceamento (FB) é calculado como altura(subárvore_esquerda) - altura(subárvore_direita). Se |FB| > 1, uma rotação é necessária.

1. Inserir 3:

   [3]
   

2. Inserir 13: (13 > 3)

   [3]
     \
     [13]
   

3. Inserir 17: (17 > 13)

   [3] (FB = -2) -> Desbalanceado
     \
     [13] (FB = -1)
       \
       [17] (FB = 0)
   

   • O nó 3 está desbalanceado (FB = -2). O caminho de desbalanceamento é 3 -> 13 -> 17 (Direita-Direita).
   • Rotação Simples à Esquerda no nó 3. O nó 13 se torna a nova raiz.

     [13] (FB = 0)
    /  \
   [3] [17]
   

4. Inserir 23: (23 > 17)

     [13] (FB = -1)
    /  \
   [3] [17] (FB = -1)
         \
         [23] (FB = 0)
   

   • A árvore permanece balanceada.

5. Inserir 7: (7 > 3, 7 < 13)

     [13] (FB = 0)
    /  \
   [3] [17]
     \   \
     [7] [23]
   

   • A árvore permanece balanceada.

6. Inserir 9: (9 > 7)

     [13] (FB = 0)
    /  \
   [3] (FB = -2) -> Desbalanceado
     \
     [7] (FB = -1)
       \
       [9] (FB = 0)
   

   • O nó 3 está desbalanceado (FB = -2). O caminho de desbalanceamento é 3 -> 7 -> 9 (Direita-Direita).
   • Rotação Simples à Esquerda no nó 3. O nó 7 se torna a nova raiz da subárvore.

         [13] (FB = 0)
        /  \
       [7] [17]
      / \    \
     [3] [9] [23]
   

   • A árvore permanece balanceada.

7. Inserir 21: (21 > 17, 21 < 23)

         [13] (FB = 0)
        /  \
       [7] [17] (FB = 0)
      / \  /  \
     [3] [9] [21] [23]
   

   • A árvore permanece balanceada.

8. Inserir 25: (25 > 23)

         [13] (FB = -1)
        /  \
       [7] [17] (FB = -1)
      / \  /  \
     [3] [9] [21] [23] (FB = -1)
                     \
                     [25] (FB = 0)
   

   • A árvore permanece balanceada.

9. Inserir 2: (2 < 3)

         [13] (FB = 0)
        /  \
       [7] [17]
      / \  /  \
     [3] [9] [21] [23]
    /                  \
   [2]                 [25]
   

   • A árvore permanece balanceada. (FB(3)=1, FB(7)=1, FB(13)=0, FB(17)=-1, FB(23)=0).

Árvore AVL final:

      [13]
     /    \
    [7]    [17]
   / \    /  \
  [3] [9] [21] [23]
 /                \
[2]                [25]

Agora, vamos realizar a busca em pré-ordem (Nó, Esquerda, Direita) na árvore final:

1. Visita o nó raiz: 13
2. Vai para a subárvore esquerda de 13 (raiz 7):
   • Visita o nó: 7
   • Vai para a subárvore esquerda de 7 (raiz 3):
     • Visita o nó: 3
     • Vai para a subárvore esquerda de 3 (raiz 2):
       • Visita o nó: 2
       • Não tem subárvore esquerda ou direita. Volta para 3.
     • Não tem subárvore direita de 3. Volta para 7.
   • Vai para a subárvore direita de 7 (raiz 9):
     • Visita o nó: 9
     • Não tem subárvore esquerda ou direita. Volta para 7.
   • Volta para 13.
3. Vai para a subárvore direita de 13 (raiz 17):
   • Visita o nó: 17
   • Vai para a subárvore esquerda de 17 (raiz 21):
     • Visita o nó: 21
     • Não tem subárvore esquerda ou direita. Volta para 17.
   • Vai para a subárvore direita de 17 (raiz 23):
     • Visita o nó: 23
     • Não tem subárvore esquerda ou direita. Volta para 23. (Opa, 23 tem 25 à direita)
     • Visita o nó: 23
     • Não tem subárvore esquerda de 23.
     • Vai para a subárvore direita de 23 (raiz 25):
       • Visita o nó: 25
       • Não tem subárvore esquerda ou direita. Volta para 23.
     • Volta para 17.
   • Volta para 13.

A sequência completa da busca em pré-ordem é: 13, 7, 3, 2, 9, 17, 21, 23, 25.

O quinto elemento da árvore a ser visitado é o número 9.

(A) Incorreta: O número 2 é o quarto elemento visitado na busca em pré-ordem (13, 7, 3, 2).
(B) Correta: O número 9 é o quinto elemento visitado na busca em pré-ordem (13, 7, 3, 2, 9). A armadilha aqui é a complexidade da construção da árvore AVL; um erro nas rotações pode levar a uma estrutura de árvore diferente e, consequentemente, a uma ordem de visitação incorreta. É crucial realizar cada inserção e balanceamento com atenção.
(C) Incorreta: O número 13 é o primeiro elemento visitado, pois é a raiz da árvore AVL final.
(D) Incorreta: O número 17 é o sexto elemento visitado na busca em pré-ordem.
(E) Incorreta: O número 25 é o último elemento visitado na busca em pré-ordem.