As árvores AVL apresentam uma característica fundamental, denominada de fator de balanceamento, que ...

Alternativa (B) - I, II e III, apenas.

Introdução

As árvores AVL (Adelson-Velsky e Landis) são uma variação de árvores binárias de busca auto-balanceáveis. Elas garantem que a altura da árvore seja sempre logarítmica em relação ao número de nós, o que otimiza o tempo de busca, inserção e remoção para O(log n). A chave para manter essa propriedade é o conceito de fator de balanceamento, que controla a diferença de altura entre as subárvores de cada nó.

Desenvolvimento

Uma árvore AVL mantém-se balanceada através de uma propriedade estrita em cada um de seus nós: o fator de balanceamento de qualquer nó deve ser -1, 0 ou 1. O fator de balanceamento é uma medida da diferença de altura entre a subárvore esquerda e a subárvore direita de um nó. Se essa propriedade for violada após uma operação (inserção ou remoção), a árvore realiza operações de rotação para restaurar o balanceamento. A altura de um nó é definida como o número de arestas no caminho mais longo de um nó até uma folha. Uma folha tem altura 0. Uma subárvore vazia tem altura -1. O cálculo do fator de balanceamento é crucial para a manutenção da estrutura AVL.

Análise

Vamos analisar cada uma das afirmativas:

1. "O fator de balanceamento em uma árvore AVL é calculado subtraindo a altura da subárvore direita da altura da subárvore esquerda."

   • Esta afirmativa está CORRETA. A definição padrão do fator de balanceamento (FB) para um nó N é: FB(N) = altura(subárvore_esquerda_de_N) - altura(subárvore_direita_de_N). Uma diferença positiva indica que a subárvore esquerda é mais alta, enquanto uma diferença negativa indica que a subárvore direita é mais alta.

2. "Para que uma árvore AVL esteja balanceada, o fator de balanceamento de cada nó deve ser -1, 0 ou 1."

   • Esta afirmativa está CORRETA. Esta é a propriedade fundamental que define uma árvore AVL. Se o fator de balanceamento de qualquer nó for diferente de -1, 0 ou 1 (ou seja, 2 ou -2), a árvore é considerada desbalanceada naquele nó.

3. "Se o fator de balanceamento de um nó em uma árvore AVL estiver fora do intervalo de -1 a 1, uma rotação deve ser realizada para restaurar o balanceamento."

   • Esta afirmativa está CORRETA. Quando o fator de balanceamento de um nó se torna 2 (subárvore esquerda muito alta) ou -2 (subárvore direita muito alta) após uma inserção ou remoção, isso significa que a propriedade AVL foi violada. Para corrigir essa violação e restaurar a propriedade de balanceamento, são aplicadas uma ou mais rotações (simples ou duplas) no nó desbalanceado e seus descendentes.

4. "O fator de balanceamento em uma árvore AVL é a soma das alturas das subárvores esquerda e direita de um nó."

   • Esta afirmativa está INCORRETA. O fator de balanceamento é a diferença entre as alturas das subárvores esquerda e direita, não a soma. A soma das alturas não forneceria a informação necessária para determinar o balanceamento da árvore. Por exemplo, uma subárvore esquerda de altura 3 e uma subárvore direita de altura 2 teriam uma soma de 5 e uma diferença de 1 (balanceado). Uma subárvore esquerda de altura 5 e uma subárvore direita de altura 0 também teriam uma soma de 5, mas uma diferença de 5 (desbalanceado). A soma não distingue.

Comparação das afirmativas:

| Afirmativa | Descrição | Correção | | :--------- | :-------------------------------------------------------------------------------------- | :------- | | 1 | Fator de balanceamento é altura(subárvore esquerda) - altura(subárvore direita). | Correta | | 2 | Fator de balanceamento de cada nó deve ser -1, 0 ou 1. | Correta | | 3 | Fator de balanceamento fora de [-1, 1] exige rotações para rebalancear. | Correta | | 4 | Fator de balanceamento é a soma das alturas das subárvores. | Incorreta|

Conclusão

As afirmativas I, II e III descrevem corretamente os aspectos fundamentais do fator de balanceamento e do processo de rebalanceamento em árvores AVL. O fator de balanceamento é definido como a diferença entre as alturas das subárvores esquerda e direita, deve estar sempre no intervalo [-1, 1] para que a árvore seja considerada balanceada, e desvios desse intervalo exigem rotações para restaurar a propriedade AVL. A afirmativa IV está incorreta, pois o fator de balanceamento é uma diferença, não uma soma.

Alternativa (B).