Questão 171220

• Banca: FGV
• Órgão: MEC
• Ano: 2009
• Provas: FGV - 2009 - MEC - Administrador de Banco de Dados; FGV - 2009 - MEC - Analista de Sistemas; FGV - 2009 - MEC - Analista de Teste de Qualidade; FGV - 2009 - MEC - Arquiteto de Sistemas; FGV - 2009 - MEC - Desenvolvedor
• Disciplina: Algoritmos e Estrutura de Dados

Acerca das estruturas de dados Árvores, analise as afirmativas a seguir.

I. A árvore AVL é uma árvore binária com uma condição de balanço, porém não completamente balanceada.

II. Árvores admitem tratamento computacional eficiente quando comparadas às estruturas mais genéricas como os grafos.

III. Em uma Árvore Binária de Busca, todas as chaves da subárvore esquerda são maiores que a chave da raiz.

Assinale:

• A. se somente a afirmativa I estiver correta.
• B. se somente as afirmativas I e II estiverem corretas.
• C. se somente as afirmativas I e III estiverem corretas.
• D. se somente as afirmativas II e III estiverem corretas.
• E. se todas as afirmativas estiverem corretas.

Gabarito: B

Comentários

• Árvore AVL - É árvore binária de altura equilibrada, ou altura balanceada. É construída de tal modo que a altura de sua subárvore direita difere da altura da subárvore esquerda de no máximo 1.

  Fonte:  http://www.icmc.usp.br/~sce182/arvbinrb.html

• III. Em uma Árvore Binária de Busca, todas as chaves da subárvore esquerda são maiores menores que a chave da raiz.
• Uma árvore AVL não é completamente balanceada?
• Paulo Eduardo,
  "É construída de tal modo que a altura de sua subárvore direita difere da altura da subárvore esquerda de no máximo 1"
  
  ela permite uma diferença de no máximo 1, e essa diferença que a faz não precisar ser "completamente balanceada"
• tenho o mesmo questionamento do Paulo Eduardo:
  Qual referência a banca utilizou para afirmar que a árvore é: "não completamente balanceada"?
  
  alguem sabe de algum referência de livro ou autor?
  
  A única definição de balanceamento que conheço é:
  A árvore está balanceada quando seus elementos podem ser encontrados com complexidade de pior caso de O(log N)
  
  Obrigado
• Achei o item 1 mal formulado. Percebe que uma árvore AVL PODE estar ou nao completamente balanceada e no item ele afirma que ela nao deve ser completamente balanceada. Pelas opções se chegava ao gabarito, mas pra mim é inaceitavel o item I. 
  
  Em concurso, é comum encontrar-mos questões que restrigem o domingio mas não invalidam o item (tipico de FCC). Como por exemplo (by Prof. Pedrosa) "Um triangulo possui dois lados?". Resp: Sim possui, possui até 3 (rs). Entenderam a malicia!? Bom, o fato é que no item I desta questão ele nao restringe, ele exclui todas as outras opções, que seria a arvore esta balanceada, portanto o item esta, a meu ver, ERRADO.
  
  Por ultimo para refletir: Uma arvore binaria com condição de balanço e não completamente balanceada pode ser considerada um arvore AVL?
  Bons estudos!!!

• Acredito que a opção I é verdadeira, pois existem outras condições de balanço que uma árvore pode ser balanceada( como por exemplo pelo peso -http://en.wikipedia.org/wiki/AVL_tree).

  Assim é verdade afirmar que a AVL não é completamente balanceada.

• Resposta: B) se somente as afirmativas I e II estiverem corretas.