Questão 769219

• Banca: CESPE / CEBRASPE
• Órgão: Banco da Amazônia
• Ano: 2012
• Provas: CESPE - 2012 - Banco da Amazônia - Técnico Científico - Administração de Dados
• Disciplina: Algoritmos e Estrutura de Dados

Uma árvore binária degenerada em lista encadeada não pode ser balanceada.

• C. Certo
• E. Errado

Gabarito: E

Comentários

• Questão errada.
  Claramente é possível balancear uma árvore binária degenerada. Para isso há uma série de algoritmos, a citar: o DSW.
  
  Para mais informações, recomendo a leitura:
  • Estrutura de Dados e Algoritmos em C++ (Adam Drozdek), 2009, Seção. 6.7 (Balanceando uma Àrvore).
• Em árvores degeneradas todos os nós têm apenas 1 filho, com exceção da (única) folha.
  
  Qualquer nó pode ser alcançado a partir da raiz em O(n) passos.

• Força Guerreiro!!!!!!