0

Conheço a teoria das árvores binárias, já fiz a implementação de uma AVL em C. Entendo o funcionamento e as aplicações dela quando desenvolvida dinâmicamente. Porém, um professor me pediu pra desenvolver uma árvore binária em vetor, fiz ela perfeitamente só que não consigo identificar uma utilidade ou vantagem para este tipo de específico de estrutura.

2
  • Depende de como será implementado, pode ser que nem esteja fazendo uma árvore binária de fato. Pode ser que só esteja simulando a memória com ele e de fato esteja usando ponteiros criados por você para implementar. Eu queria ver essa implementação para ver se ela ainda é uma árvore de fato e se for, se não é só uma camada extra em algo desnecessário.
    – Maniero
    Commented 17/01/2017 às 18:51
  • Uma das maiores vantagems de um vetor é o acesso direto. Sobre isso, dê uma olhada em Heaps, que são árvores binárias de máximo e mínimo, muito bem implementadas com vetores, devido ao modo como ela se organiza. Se gostar, pesquise por Heapsort, um algoritmo de ordenação utilizando essa estrutura. Commented 17/01/2017 às 18:57

2 Respostas 2

1

São algumas vantagens:

1) A busca em largura vira uma simples interação sobre o Array

2) Você tem acesso O(1) a qualquer nó da sua árvore ao invés de ter que percorrer sua altura pra chegar.

3) Arrays existem em praticamente todas as linguagens de programação, diferentemente de ponteiros.

Fonte: https://www.quora.com/When-is-it-good-to-represent-a-binary-tree-as-an-array-instead

Com certeza existem outras vantagens/aplicações, então comentem que eu edito na resposta, mas acho que fica claro que tem sim aplicação e um porquê de se utilizar a árvore dessa forma.

0

O HeapSort é um caso clássico em que se tem uma árvore binária representada em um vetor.

As vantagens de se usar uma árvore binária representada em um vetor são relativas à performance:

  • os dados não estão totalmente independentes entre si na memória, então você terá menos cache miss
  • o processador não precisará navegar do ponteiro até a região de memória contendo o nó, para só então pegar seu valor, portanto você faz menos acessos a memória, o que acarreta em menos processamentos e diminui as chances de mudar os dados que estão em cache
  • você aloca menos memória e numa região contígua, pois está trabalhando com um vetor de elementos

Existem desvantagens relativas ao uso na representação em vetor também. Remoção/inserção pode se tornar problemático, pois exige manipulação de subárvores.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .