As árvores binárias servem a um propósito específico no armazenamento de dados hierárquicos? Qual é o uso canônico deles?

12

Entendo a estrutura das árvores binárias e como atravessá-las. No entanto, estou lutando para perceber seus usos, propósitos em programas e programação. Quando penso em exemplos da vida real de dados hierárquicos, eles quase certamente têm mais de 2 filhos. Por exemplo, em uma árvore genealógica, uma mãe pode ter mais de dois filhos.

As 'árvores binárias' são realmente úteis apenas para armazenar dados relacionados linearmente devido aos tempos de processamento mais rápidos em matrizes e listas? Como alternativa, eles servem a um propósito específico no armazenamento de dados hierárquicos? Nesse caso, que exemplos existem da aplicação de árvores binárias. Quais dados são tais que um nó tem no máximo 2 filhos?

data-structures binary-tree sw123456
fonte
Eu acho que o principal uso de uma árvore binária é ordenar dados. https://en.wikipedia.org/wiki/Binary_search_tree
Mandrill

Respostas:

25

Não, as árvores binárias não servem para armazenar dados hierárquicos no sentido em que você está pensando. O principal caso de uso para árvores n-árias, onde né um número fixo, é o recurso de pesquisa rápida , não uma hierarquia semântica.

Lembre-se do jogo antigo, em que uma pessoa pensa em um número entre 1 e 100, e a outra tem que adivinhar o mínimo possível de palpites, e se você errar, a pessoa que pensa no número deve lhe dizer se você é demais. alto ou muito baixo? Fica entediante depois de um tempo, porque você rapidamente descobre que sempre deve começar aos 50, depois passa para 25 ou 75 e continua dividindo o intervalo a ser pesquisado ao meio com cada nova palpite depois disso e, eventualmente, pode adivinhar qualquer número em no máximo 7 palpites, garantido.

Pode não ser um jogo divertido, mas essa propriedade é o que torna as árvores binárias (e outras n-árias) úteis: você pode usá-las para pesquisar um conjunto de dados muito grande em um período de tempo muito pequeno.

Mason Wheeler
fonte
Excelente resposta muito obrigado. Então, as árvores binárias são realmente apenas outra estrutura para armazenar dados como você faria em uma matriz ou lista, mas com o benefício adicional de recursos de pesquisa rápida?
sw123456
1
@ sw123456: Está certo. Como em qualquer engenharia, ele vem com vantagens e desvantagens (usa mais - e mais fragmentada - memória que uma matriz com o mesmo número de elementos, O (n) acesso ao elemento #n do conjunto de dados em vez de O (1) acesso etc.), mas a pesquisa rápida é definitivamente o principal benefício das árvores binárias.
Mason Wheeler
@ sw123456 Ainda bem que pude ajudar a explicar isso :)
Mason Wheeler
3
O acesso aos elementos é O (log (n)) quando a árvore está equilibrada. O (n) será o pior caso quando estiver degenerado (a maioria dos nós com apenas um colchete).
Mandrill
@ sw123456 O encaminhamento de rede utiliza uma ligeira modificação de uma árvore binária chamada Trie (criada para aumentar a eficiência do domínio do problema). Na verdade, ele armazena informações de hierarquia à medida que os roteadores percorrem a árvore, bit a bit, ao procurar um endereço IP para descobrir para onde deve encaminhar o pacote. Os endereços IP também são por natureza hierárquicos; portanto, ao percorrer um IP para encontrar a correspondência de prefixo mais longa, o roteador percorre a hierarquia de IP, os IPs de sub-rede, etc. Não é óbvio semanticamente, mas o relacionamento está lá. Os roteadores usam essa estrutura para obter eficiência de pesquisa, como Mason respondeu.
Chris Cirefice
3

Qualquer estrutura de árvore, onde um nó pode ter um número ilimitado de filhos, pode ser implementada usando uma árvore binária.

Para cada nó na sua árvore, substitua-o por um nó com o ponteiro direito e esquerdo. O ponteiro esquerdo vai para o primeiro filho do nó. O nó direito vai para o próximo irmão do nó. Todos os filhos de um determinado nó estão em uma lista vinculada unida pelos ponteiros direitos, com o cabeçalho da lista apontado pelo ponteiro esquerdo do pai.

Sua árvore complicada e nária se tornou uma árvore simples e binária.

Estou certo de que isso está em Knuth, vol. 1 em algum lugar.

Justsalt
fonte
Esta é uma implementação realmente interessante. Estou certo ao pensar que, como cada nó filho era o início de uma lista vinculada, a árvore não seria mais O (log) n) se equilibrada ou O (n) se não, devido ao fato de que visitar cada nó seria iniciado fora de uma pesquisa linear? Essa implementação resultaria em tempos de pesquisa muito mais lentos? Mas, de cabeça para baixo, os tempos de pesquisa seriam mais rápidos que os de uma estrutura linear padrão? Eu entendi isso corretamente?
21125 sw123456
@ sw123456, Se a árvore original estivesse equilibrada, a árvore binária resultante quase certamente não seria. Acredito que tudo o mais dependeria do ventilador da árvore, quantos filhos um nó tem. Uma pesquisa linear ocorreria apenas ao descobrir qual dos filhos de um determinado nó seguir. Mas não tenho certeza de que você possa evitar isso em qualquer outra implementação de uma árvore n-ária.
Justsalt
2

Árvores binárias por que usá-las?

Na programação, você trabalha muito com coleções do mesmo tipo de dados.

As duas maneiras básicas de armazenar esses dados são: listas e matrizes vinculadas.

Ambos vêm com vantagens e desvantagens: em uma lista vinculada, é fácil adicionar elementos em qualquer posição ou remover elementos. Mas o acesso a um elemento específico é mais difícil, porque você precisa percorrer a lista até chegar ao elemento que deseja.

  • Ele não pesquisa com eficiência, mas é fácil inserir e excluir.

Com uma matriz, o acesso a um elemento específico é fácil, mas é mais difícil inserir ou excluir um elemento porque a inserção significa: estender a matriz por um, alternar todos os elementos antes da posição de inserção 1 para a direita e inserir o elemento.

  • Ele pesquisa com eficiência (se classificado), mas é difícil inserir e excluir.

Portanto, a lista vinculada e a matriz têm desvantagens.

Árvores binárias são feitas para resolver os problemas da matriz e da lista vinculada:

  1. Fácil inserção e exclusão
  2. Pesquisa fácil

Então, a árvore binária é criada para quando você tem muitos dados que são alterados regularmente.

Pieter B
fonte