Alternativa C
Para responder a esta questão, é necessário analisar o comportamento de uma Árvore Binária de Busca (BST) e entender os conceitos de balanceamento (provavelmente referindo-se a Árvores AVL), já que as alternativas mencionam explicitamente "se a árvore for balanceada".
Análise Detalhada
1. Estrutura Atual da Árvore
A figura apresenta uma árvore onde:
- Raiz: 8
- Subárvore Esquerda: Raiz 4 (não tem filhos).
- Subárvore Direita: Raiz 12 (filhos 10 e 15).
Esta é uma estrutura válida de BST, pois valores à esquerda são menores e à direita são maiores.
2. Por que a Alternativa C está correta?
A alternativa discute a inserção do nó 5 em uma árvore balanceada. Vamos simular o processo:
- Inserção: Ao inserir 5, comparamos com a raiz (8). Como $5 < 8$, vamos para a esquerda. Comparamos com o nó 4. Como $5 > 4$, o novo nó 5 torna-se o filho direito de 4.
- Verificação de Balanceamento:
- O nó 4 tinha altura 0 (era folha). Agora tem altura 1 (tem um filho).
- O Fator de Equilíbrio (FE) do nó 4 passa a ser: FE = |Alt(Esquerda) - Alt(Direita)| = |-1 - 1| = 2.
- Um FE igual a 2 indica desbalanceamento.
- Rotação: Como a inserção ocorreu na subárvore direita do nó 4, realiza-se uma Rotação Simples à Esquerda nesse nó.
- Na rotação à esquerda, o filho direito (nó 5) sobe para ocupar a posição da raiz da subárvore.
- O nó antigo (4) desce para a esquerda do novo nó (5).
- Resultado: O nó 5 assume o lugar do nó 4 e torna-se a raiz daquela subárvore. Isso confirma exatamente o que diz a alternativa C.
3. Por que as outras estão incorretas?
- (A) Pré-ordem: A ordem correta é Raiz \rightarrow Esquerda \rightarrow Direita ($8 \rightarrow 4 \rightarrow 12 \rightarrow 10 \rightarrow 15$). A alternativa apresenta uma sequência errada.
- (B) Remoção: Ao remover a raiz (8), que possui dois filhos, a regra padrão em BST é substituir o nó removido pelo seu sucessor (menor valor da subárvore direita, que seria o 10) ou pelo predecessor (maior valor da subárvore esquerda, que seria o 4). O nó 12 não assume a raiz diretamente.
- (D) Inserção de 9: O nó 9 entraria na subárvore direita (8 -> 12 -> 10 -> 9). Isso causaria desbalanceamento na raiz 8. O pivô da rotação para reequilibrar seria o nó 10, e não o 12.
- (E) Árvore de Ordem 2: Independentemente da definição exata de "ordem 2" usada no contexto, transformar essa árvore em uma estrutura mais compacta não obrigatoriamente colocaria todas as folhas no nível 2, pois temos 5 nós. Uma árvore binária completa com 5 nós teria folhas no nível 3.
Análise dos Conceitos-Chave
- Pré-ordem: Visita a raiz primeiro, depois a esquerda, depois a direita.
- Fator de Equilíbrio (FE): Diferença entre as alturas das subárvores esquerda e direita.
FE(Nó) = |Alt(Esquerda) - Alt(Direita)| - Rotação: Operação fundamental em árvores balanceadas (como AVL) para restaurar o equilíbrio após inserções ou remoções sem violar a propriedade de busca.
- Sucessor Imediato: O menor valor na subárvore direita de um nó (usado frequentemente na remoção de nós com dois filhos).
Conclusão
A lógica de balanceamento de árvores descritas na alternativa C segue rigorosamente os algoritmos de manutenção de árvores AVL, onde a inserção gera um desbalanceamento local que é corrigido via rotação, fazendo com que o novo nó inscrito (5) assuma a liderança da subárvore desbalanceada.