Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — CEPS-UFPA 2022

Construção de árvore AVL: simulação passo a passo

Gabarito: letra E. Após inserir os elementos 19, 18, 16, 15, 17, 2, 6 em uma árvore AVL inicialmente vazia, realizando os balanceamentos necessários (rotações simples e duplas), a árvore final tem raiz 16, subárvore esquerda com raiz 6 (filhos 2 e 15) e subárvore direita com raiz 18 (filhos 17 e 19). O percurso pré-ordem (raiz, esquerda, direita) produz a sequência 16, 6, 2, 15, 18, 17, 19, que corresponde exatamente à alternativa E.

A questão exige o entendimento do algoritmo de inserção em árvores AVL, que mantém o balanceamento por meio de rotações. Vamos percorrer cada inserção e verificar quando ocorrem rotações.

Simulação detalhada

1. Inserir 19 – árvore: 19 (fb=0).

2. Inserir 18 – 18 < 19, filho esquerdo de 19. Alturas: 18 (h=1), 19 (h=2, fb=1).

3. Inserir 16 – 16 < 19, < 18, filho esquerdo de 18. Alturas: 16 (h=1), 18 (h=2, fb=1), 19 (h=3, fb=2 → desbalanceado). Rotação simples à direita em 19: 18 torna-se raiz, 19 direita de 18. Árvore: 18 (fb=0) com esquerda=16 (fb=0) e direita=19 (fb=0).

4. Inserir 15 – 15 < 18, < 16, filho esquerdo de 16. Alturas: 15 (h=1), 16 (h=2, fb=1), 18 (h=3, fb=1) – todos balanceados.

5. Inserir 17 – 17 > 16, < 18, filho direito de 16. Alturas: 17 (h=1), 16 (h=2, fb=0), 18 (h=3, fb=1) – balanceados.

6. Inserir 2 – 2 < 15, filho esquerdo de 15. Alturas: 2 (h=1), 15 (h=2, fb=1), 16 (h=3, fb=1), 18 (h=4, fb=2 → desbalanceado). Nó 18 com fb=2 e filho esquerdo 16 com fb=1 (mesmo sinal) → rotação simples à direita em 18. Resultado: 16 torna-se raiz, 18 vai para direita de 16, e o filho direito de 16 (17) torna-se filho esquerdo de 18. Árvore: 16 (fb=0) com esquerda=15 (esquerda=2, fb=1) e direita=18 (esquerda=17, direita=19, fb=0).

7. Inserir 6 – 6 < 16, < 15, > 2, filho direito de 2. Alturas: 6 (h=1), 2 (h=2, fb=-1), 15 (h=3, fb=2 → desbalanceado). Nó 15 com fb=2 e filho esquerdo 2 com fb=-1 (sinais opostos) → rotação dupla à direita (primeiro rotação simples à esquerda em 2, depois rotação simples à direita em 15). Após rotação: 6 torna-se filho esquerdo de 16, com esquerda=2 e direita=15. Todos os fatores de balanço ficam 0.

A árvore final é:

• Raiz: 16

• Esquerda: 6 (esquerda=2, direita=15)

• Direita: 18 (esquerda=17, direita=19)

Percurso pré-ordem

Pré-ordem visita: raiz, subárvore esquerda, subárvore direita.

• 16

• Subárvore esquerda (raiz=6): 6, depois 2, depois 15 → 6, 2, 15

• Subárvore direita (raiz=18): 18, depois 17, depois 19 → 18, 17, 19

Sequência completa: 16, 6, 2, 15, 18, 17, 19.

Análise das alternativas

• Alternativa A (❌ Incorreta): 18, 16, 15, 2, 6, 17, 19 – corresponde a um percurso diferente (possivelmente pré-ordem de uma árvore sem as rotações adequadas).

• Alternativa B (❌ Incorreta): 2, 6, 15, 16, 17, 18, 19 – sequência ordenada crescente (percurso em ordem simétrica).

• Alternativa C (❌ Incorreta): 2, 15, 6, 17, 19, 18, 16 – não corresponde a nenhum percurso padrão da árvore final.

• Alternativa D (❌ Incorreta): 16, 15, 2, 6, 18, 17, 19 – embora comece com 16, a ordem da subárvore esquerda está errada (15 antes de 2 e 6).

• Alternativa E (✅ Correta ⟵ GABARITO): 16, 6, 2, 15, 18, 17, 19 – exatamente o percurso pré-ordem calculado.

Gabarito: letra E