SóProvas

ID
309517
Banca
CESPE / CEBRASPE
Órgão
TJ-ES
Ano
2011
Provas
Disciplina
Algoritmos e Estrutura de Dados

No que se refere às estruturas de dados, julgue os itens
subsequentes.

As árvores binárias possuem vantagens em relação às listas encadeadas somente quando estão balanceadas, justificando-se o uso de um método de balanceamento de uma árvore binária quando elementos estão sendo constantemente acrescidos e removidos da árvore.

Alternativas
Comentários
  • Acredito que o erro da questão estã em dizer em que é justificado o uso de um método de balanceamento quando os elementos estão constantemente sendo acrescido e removidos da árvore.
  • Eu já acredito que o erro está em dizer "balanceamento de uma árvore binária", em vez de árvore de BUSCA binária, mais especificamente AVL.
  • Acredito que erro está em dizer que há vantagens "somente quando estão balanceadas".
    O pior caso de uma arvore é quando ela esta totalmente desbalanceada. Nessa situação ela terá a mesma complexidade de busca de uma lista linear, ou seja, O(n).  Portanto, mesmo uma árvore que não esteja balanceada, mas não esteja no pior caso,  terá um desempenho melhor do que O(n).

    A complexidade de busca de uma arvore balanceada, no caso médio, é O(log(n)) [o que é menor que O(n)].
  • A complexidade de referência é sempre do pior caso (Big-Oh), dessa forma, quando uma árvores está balanceada seu pior caso numa consulta será O(log n), já para uma árvore não balanceada seu pior caso será uma árvore com altura igual a quantidade de chaves, tornando-a equivalente a uma lista O(n).

    Até ai a questão está correta, entretanto a justificativa (o que faz o balanceamento valer a pena) não é o fato de elementos serem constantemente adicionados e removidos, isso caracteriza a desvantagem da utilização de métodos de balanceamento, tendo em vista que são mais custosos do que se não existissem.

    A vantagem em utilizar métodos de balanceamento é observada nos métodos de consulta, pois o balanceamento garante uma consulta em O(log n).
  • Colocando a questão em outras palavras para melhor compreensão:

    As árvores binárias não balanceadas nunca possuem vantagens em relação às listas encadeadas, o que justifica o uso de um método de balanceamento de uma árvore binária no momento em que os elementos estão sendo acrescidos e removidos da árvore.

    - O fato de uma arvore binaria balanceada ser melhor justifica o uso de um método de balanceamento?
    Sim

    - O balanceamento é realizado no momento em que os elementos são acrecidos e removidos da arvore?
    Sim. (é possivel haver outras soluções, mas essa é uma delas e a mais usada)

    - As árvores binárias não balanceadas nunca possuem vantagens em relação às listas encadeadas?
    Quer dizer, uma arvore binária desbalanceada nunca será melhor que uma lista encadeada? Ta certo que isso vai acontecer quando a arvore estiver no pior caso, mas afirmar que ela nunca irá oferecer vantagem está errado. Questão errada.
  • Repare que a questão falou em árvores binárias, NUNCA em árvores binárias de busca.
    Mesmo que a árvore não estivesse ordenada, ainda sim ela é uma esrutura que pode apresentar dados de forma hierárquica.
    Esta já seria uma vantagem em relação a listas

  • O pior caso de uma árvore binária é quando ela não tem ramificação NENHUMA. Nesse caso ela é igual uma lista encadeada. Mas se tiver, ao menos uma ramificação, ainda que não fique balanceada, já é melhora que a lista encadeada.


    A questão falou que só tem vantagem se estiver toda balanceada. Portanto, errada.