As Árvores AVL são um tipo específico de árvore binária balanceada que garantem que a estrutura da á...

Alternativa C - O fator de balanceamento em uma árvore AVL é a diferença de altura entre as subárvores esquerda e direita de um nó, que deve estar entre -1 e 1.

Introdução

As Árvores AVL (Adelson-Velsky e Landis) representam uma evolução das árvores binárias de busca (BSTs) convencionais, projetadas para mitigar o problema do desempenho degenerado que pode ocorrer quando os dados são inseridos em uma ordem que resulta em uma árvore desbalanceada, assemelhando-se a uma lista encadeada. Para garantir operações eficientes de busca, inserção e remoção, as Árvores AVL introduzem um mecanismo rigoroso de balanceamento, mantido através de um conceito-chave: o fator de balanceamento.

Desenvolvimento

Em uma árvore binária de busca comum, o tempo de execução das operações pode variar de O(log N) no melhor caso (árvore perfeitamente balanceada) para O(N) no pior caso (árvore degenerada). As Árvores AVL resolvem isso garantindo que, a cada nó, a altura de suas duas subárvores (esquerda e direita) não difira em mais de uma unidade. Esse critério de balanceamento é estritamente mantido através da computação do fator de balanceamento para cada nó.

O fator de balanceamento de um nó é um valor numérico que quantifica o grau de desbalanceamento entre as alturas de suas subárvores. Ele é calculado como a diferença entre a altura da subárvore esquerda e a altura da subárvore direita. Após cada operação de inserção ou remoção, os nós afetados na trajetória da raiz até o nó modificado são verificados. Se o fator de balanceamento de qualquer nó violar a regra de balanceamento, ou seja, se seu valor absoluto for maior que 1, rotações (simples ou duplas) são aplicadas para restaurar a propriedade AVL.

Análise

Vamos analisar cada alternativa à luz do conceito de fator de balanceamento em árvores AVL:

| Alternativa | Análise da Afirmação | Correção / Justificativa | | :---------- | :------------------------------------------------------------------------------------------------------------------------------------------------ | :-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | (A) | "Árvores AVL são balanceadas apenas quando a altura da subárvore esquerda é igual à altura da subárvore direita." | Incorreta. Embora uma árvore onde as alturas são iguais (fator de balanceamento 0) seja balanceada, uma Árvore AVL também é considerada balanceada se a diferença de altura for -1 ou 1. A restrição "apenas" torna esta alternativa falsa, pois o critério é mais flexível. | | (B) | "O fator de balanceamento em uma árvore AVL é a soma das alturas das subárvores esquerda e direita de um nó." | Incorreta. O fator de balanceamento é a diferença das alturas (altura(esquerda) - altura(direita)), não a soma. A soma das alturas não indica o balanceamento relativo entre as subárvores, mas sim uma medida da dimensão total sem critério de balanço. | | (C) | "O fator de balanceamento em uma árvore AVL é a diferença de altura entre as subárvores esquerda e direita de um nó, que deve estar entre -1 e 1." | Correta. Esta alternativa define precisamente o fator de balanceamento e seu critério de validade para um nó em uma Árvore AVL. Os valores permitidos para o fator de balanceamento são -1, 0 ou 1. Qualquer valor fora desse intervalo indica um desbalanceamento que requer uma operação de rotação. | | (D) | "O fator de balanceamento em uma árvore AVL pode ser qualquer valor, desde que a árvore permaneça balanceada." | Incorreta. Esta afirmação é contraditória. O fator de balanceamento tem limites muito estritos ([-1, 1]). Se o fator de balanceamento for "qualquer valor" (por exemplo, 2 ou -2), a árvore não permanece balanceada de acordo com as regras AVL, e rotações seriam necessárias para restaurar o balanço. | | (E) | "Árvores AVL não necessitam de rotações para manter o balanceamento após inserções e remoções." | Incorreta. As rotações (simples: LL, RR; ou duplas: LR, RL) são o mecanismo fundamental pelo qual as Árvores AVL restauram o balanceamento sempre que uma inserção ou remoção causa uma violação do fator de balanceamento (ou seja, quando o BF se torna 2 ou -2). Sem rotações, as árvores AVL degenerariam como BSTs comuns. |

Conclusão

O fator de balanceamento é o pilar das Árvores AVL, garantindo que a estrutura da árvore permaneça otimizada para operações de busca, inserção e remoção, mantendo uma complexidade de tempo de O(log N). A definição correta do fator de balanceamento como a diferença de altura entre as subárvores esquerda e direita, com a exigência de que seu valor esteja dentro do intervalo [-1, 1], é fundamental para o entendimento e a implementação eficaz das Árvores AVL. Qualquer desvio desse intervalo aciona os mecanismos de rotação para restaurar o equilíbrio da árvore.

Alternativa C.