Questão 41 — Árvores AVL (Algoritmos e Estruturas de Dados) — Fundação VUNESP · Exército Brasileiro — Escola de Saúde e Formação Complementar do Exército (ESFC… 2023

Algoritmos e Estruturas de Dados Árvores AVL

Fundação VUNESP 2023

Exército Brasileiro — Escola de Saúde e Formação Complementar do Exército (ESFCEx) · Oficial do Quadro Complementar do Exército · Caderno 008. Prova Objetiva — Modelo de prova (Versão) A

Gabarito disponível

Uma árvore binária é denominada AVL quando, para qualquer nó dessa árvore, as alturas de suas duas sub-árvores (esquerda e direita)

Selecione uma alternativa A) diferem, em módulo, em mais de uma unidade. B) diferem, em módulo, de até uma unidade. C) são sempre iguais. D) são maiores do que dez unidades. E) são maiores do que cinco unidades.

Resolução comentada

Árvore AVL é a árvore binária de busca balanceada pela altura, com diferença de no máximo 1 entre as subárvores de cada nó.

Na árvore AVL, para todo nó, o módulo da diferença entre as alturas das subárvores esquerda e direita (fator de balanceamento) é de no máximo 1, ou seja, vale -1, 0 ou 1. Quando uma inserção ou remoção viola essa condição, são feitas rotações para restaurar o balanceamento.

Análise das alternativas

A) Errada: diferença maior que 1 viola a definição de AVL. C) Errada: exigir alturas sempre iguais é restritivo demais e só seria possível com árvores perfeitas. D) e E) Erradas: a definição não fixa valores mínimos para as alturas.

Referência: Adelson-Velsky e Landis (1962); Cormen et al., Algoritmos: Teoria e Prática; Szwarcfiter, Estruturas de Dados e Seus Algoritmos.

Resolução comentada do VaiConcursos.