Questão de Algoritmos e Estrutura de Dados — Árvores — FGV 2024

Árvore AVL – Inserção e Pré-ordem

Gabarito: letra B. O quinto elemento visitado na pré-ordem da árvore AVL formada pela inserção sequencial de 3, 13, 17, 23, 7, 9, 21, 25 e 2 é o número 9.

A banca exige que o candidato construa a árvore AVL passo a passo, aplicando as rotações necessárias, e depois execute o percurso pré-ordem (raiz, subárvore esquerda, subárvore direita).

Simulação da construção

Inserções e ajustes:

1. 3: raiz.

2. 13: inserido à direita de 3. Fator de balanceamento de 3 = +1 (ok).

3. 17: inserido à direita de 13. Nó 3 fator +2 → rotação simples à esquerda: raiz vira 13, com filho esquerdo 3 e direito 17.

4. 23: inserido à direita de 17. Árvore balanceada.

5. 7: inserido à direita de 3. Árvore balanceada.

6. 9: inserido à direita de 7. Nó 3 fator +2 → rotação simples à esquerda no 3: 7 vira raiz da subárvore esquerda de 13, com filhos 3 (esq) e 9 (dir).

7. 21: inserido à esquerda de 23. Nó 17 fator +2 → rotação dupla: primeiro rotação direita no 23, depois esquerda no 17. Subárvore direita de 13: raiz 21, com filhos 17 (esq) e 23 (dir).

8. 25: inserido à direita de 23. Árvore balanceada.

9. 2: inserido à esquerda de 3. Árvore balanceada.

Estrutura final da AVL:

Percurso pré-ordem

A visita começa na raiz, desce à esquerda até o fim, depois retorna e vai à direita:

• 13 (1º)

• 7 (2º)

• 3 (3º)

• 2 (4º)

• 9 (5º)

• 21 (6º)

• 17 (7º)

• 23 (8º)

• 25 (9º)

O quinto número visitado é 9, correspondente à alternativa B.

Alternativas incorretas

• A) 2: quarto visitado.

• C) 13: primeiro visitado.

• D) 17: sétimo visitado.

• E) 25: nono visitado.