Questão 607171

• Banca: CESGRANRIO
• Órgão: Petrobras
• Ano: 2011
• Provas: CESGRANRIO - 2011 - Petrobras - Analista de Sistemas Júnior - Processos de Negócios - 2011
• Disciplina: Algoritmos e Estrutura de Dados

Após a inserção de um nó, é necessário verificar cada um dos nós ancestrais desse nó inserido, relativamente à consistência com as regras estruturais de uma árvore AVL.

PORQUE

O fator de balanceamento de cada nó, em uma árvore AVL, deve pertencer ao conjunto formado por {-2, -1, 0, +1, +2}.

Analisando-se as afirmações acima, conclui-se que

• A. as duas afirmações são verdadeiras, e a segunda justifica a primeira.
• B. as duas afirmações são verdadeiras, e a segunda não justifica a primeira.
• C. a primeira afirmação é verdadeira, e a segunda é falsa.
• D. a primeira afirmação é falsa, e a segunda é verdadeira.
• E. as duas afirmações são falsas.

Gabarito: C

Comentários

• Iniciamente eu pensei que o item II estivesse correto, eu até errei a questão, mas depois me atentei ao detalhe crucial:

  O fator de balanceamento de cada nó, em uma árvore AVL, deve pertencer ao conjunto formado por { -1, 0, +1}. - AVL balanceada.

   

  {-2, +2} - Caracteriza desbalanceamento.

   

  Go ahead!!!

• Uma árvore binária T é denominada AVL quando, para qualquer nó de T, as alturas de suas duas subárvores, esquerda e direita, diferem em módulo de até uma unidade. Pela definição fica estabelecido que todos os nós de uma árvore AVL devem respeitar a seguinte propriedade:

  |hd(u) - he(u)| ≤ 1, onde hd(u) é a altura da subárvore direita do nó u e he(u) é a altura da subárvore esquerda do nó u. O valor hd(u) - he(u) é denominado fator de balanço do nó. Quando um nó possui fator de balanço com valor -1, 0 ou 1 então o mesmo é um nó regulado. Todos os nós de uma árvore AVL são regulados, caso contrário a árvore não é AVL.

  Fonte: https://pt.wikipedia.org/wiki/%C3%81rvore_AVL

  Logo, a segunda afirmação é falsa!