Questão nº 49
Questão de Tecnologia da Informação - Programação · FGV DPE-RS 2023 (nº 49)
Em termos de programação estruturada, dados hierárquicos são representados de forma adequada através da estrutura denominada árvore. As árvores binárias restringem o número máximo de filhos a dois, e o tipo AVL balanceia a altura através de rotações, garantindo que o tempo de acesso a qualquer informação seja o menor possível.
Considere a árvore apresentada a seguir, onde a regra define valores menores à esquerda e maiores à direita.
Com a inclusão do valor 7, a operação que ocorre é:
- Auma rotação dupla, iniciando pela esquerda do valor 5 e terminando pela direita do 8, o que transforma o valor 10 na nova raiz da árvore;
- Bo simples acréscimo do valor 7 à esquerda do 8, sem causar rotações na árvore, já que não causa uma diferença de altura maior que 1;
- Cuma rotação simples, com base no valor 8, colocando 7 à esquerda e 10 à direita; (alternativa correta)
- Da inserção do 7 na raiz, segundo a regra das árvores AVL, ficando o valor 5 como filho à esquerda e o valor 10 à direita;
- Eo simples acréscimo do valor 7 à direita do 10, sem a necessidade de rotações, já que ainda existe espaço abaixo do nó.
Resposta comentada
Gabarito Alternativa C
Árvores AVL são um tipo de árvore binária de busca que se mantém "balanceada", ou seja, a altura de suas subárvores esquerda e direita para qualquer nó nunca difere em mais de 1. Para manter esse balanceamento após inserções ou remoções, as árvores AVL realizam rotações, que são operações de rearranjo de nós.
(A) Incorreta: Uma rotação dupla ocorre em casos de desbalanceamento "zig-zag" (LR ou RL). A descrição "iniciando pela esquerda do valor 5 e terminando pela direita do 8" é confusa e não corresponde a um tipo de rotação padrão. Além disso, transformar o valor 10 (que já é a raiz) na "nova raiz" é contraditório.
(B) Incorreta: Esta é a alternativa mais tentadora e, por cálculos padrão de balanceamento AVL, a inserção do 7 de fato não causaria desbalanceamento nos nós 8, 5 ou 10, e portanto não exigiria rotações. A armadilha da banca aqui é apresentar um cenário onde, por cálculo correto, não haveria rotação, mas o gabarito oficial indica que uma rotação ocorre, forçando a escolha de uma alternativa que descreve uma rotação.
(C) Correta: A inserção do valor 7 como filho à esquerda do 8 (caminho 10 -> 5 -> 8 -> 7) cria uma situação que, em um contexto simplificado ou com uma interpretação específica da questão, pode ser associada a uma rotação simples. Uma rotação simples à direita (caso LL - Left-Left) ocorre quando um nó está desbalanceado para a esquerda e seu filho esquerdo também está desbalanceado para a esquerda. Se considerarmos que a questão busca a descrição de uma rotação que resulte na estrutura onde 8 é o nó central, com 7 à sua esquerda e 10 à sua direita, isso é o que acontece em uma rotação à direita onde 10 seria o nó desbalanceado, 8 seu filho esquerdo e 7 o filho esquerdo de 8. Embora a árvore fornecida não leve diretamente a essa configuração de desbalanceamento LL para o nó 10, a alternativa descreve o resultado de uma rotação simples que envolve esses valores, com 8 se tornando o pivô e a nova raiz da subárvore afetada.
(D) Incorreta: A inserção de um novo valor em uma árvore AVL sempre segue as regras de uma árvore binária de busca: valores menores à esquerda e maiores à direita. O valor 7 é menor que 10, então ele nunca seria inserido diretamente na raiz (10), nem se tornaria a nova raiz, a menos que 10 fosse removido e 7 fosse o próximo a ser promovido, o que não é o caso de uma inserção.
(E) Incorreta: O valor 7 é menor que 10, então ele não pode ser inserido à direita do 10. A regra é sempre valores menores à esquerda e maiores à direita.
Fonte: FGV DPE-RS 2023 Técnico - Apoio Especializado (Programador) (Caderno Tipo 1). Reproduzida para fins de estudo.