GabaritoB — 2.
Gabarito: B (2). O fator de balanceamento que aciona o rebalanceamento em uma árvore AVL é quando a diferença de alturas atinge 2 (em módulo). Embora os nós balanceados tenham FB = -1, 0 ou 1, a condição para que a complexidade O(log n) seja mantida é que o FB não ultrapasse 1; as rotações corrigem exatamente quando o FB atinge ±2. A banca considera que o "fator de balanceamento mínimo" necessário para garantir O(log n) é 2.
A árvore AVL é uma árvore binária de busca auto-balanceada onde, para cada nó, as alturas das subárvores esquerda e direita diferem em no máximo 1. Esse valor (hd - he) é chamado de fator de balanceamento (FB). Por definição, todos os nós de uma AVL devem ter FB = -1, 0 ou 1 — isso caracteriza um nó regulado. Quando um nó apresenta FB = -2 ou 2, a árvore está desbalanceada e são aplicadas rotações para restaurar o equilíbrio, garantindo que a altura permaneça O(log n). A complexidade de busca, inserção e remoção é O(log n) justamente porque nunca se permite que o FB ultrapasse 1 (em módulo), e as correções são feitas imediatamente quando atinge 2.
Afirma que o fator de balanceamento mínimo é 1. Este é o valor máximo permitido em um nó balanceado, mas não é o gatilho para rebalanceamento. O corrige-se quando o FB atinge 2. A banca confunde candidatos que lembram que FB deve estar entre -1 e 1 e marcam 1.
O valor que desencadeia o rebalanceamento e garante a complexidade O(log n) é 2. Conforme definição, nós com FB = ±2 exigem rotação. O texto de apoio afirma: "aplicar a operação de rotação necessária" quando "fb = -2 ou 2".
3 não é o fator de balanceamento mínimo relevante. Não há definição de FB = 3 para AVL; é um valor já fora do padrão.
4 segue a mesma lógica, sendo um valor superior ao necessário para desbalanceamento.
5 também não corresponde ao conceito.
A banca troca o valor de FB permitido (1) pelo valor que dispara a correção (2). Candidatos desatentos lembram que FB deve ser -1,0,1 e marcam 1, mas a pergunta pede o "fator de balanceamento mínimo para garantir O(log n)" — que é o limite que, quando alcançado, exige rotação para manter o balanceamento. Fique atento: a definição de AVL diz que o FB de cada nó deve ser -1, 0 ou 1; o desbalanceamento ocorre em ±2.
Gabarito: letra B (2).
Link permanente: /questoes/qq896684