exemplos do mundo real de estruturas de árvore

https://stackoverflow.com/questions/577659

05-09-2019
|

Pergunta

Eu estou procurando alguns exemplos de estruturas de árvore que são usados ??em projetos comerciais / Software Livre, modernos ou antigos. Eu posso ver exemplos na wikipedia, mas eu estou procurando exemplos mais concretos e como eles são usados. Por exemplo, as chaves primárias em bancos de dados são (pelo que tenho lido) armazenadas na estrutura BST ou uma variação do BST (sinta-se livre para me corrigir sobre isso)

A minha pergunta não se limita Binary Pesquisa Árvores (BSTs), pode incluir qualquer variação como o vermelho-preto, AVL e assim por diante.

Solução

Está tudo bem se os exemplos são um pouco pouco genérico ou seja, se relacionam com gráficos e não necessariamente para árvores? Se for, continue a ler.

Não é preciso dizer mais XML / analisadores de marcação usar árvores. Veja Apache Xerces por exemplo. Ou, o analisador Xalan XSLT. Graças mathewsdave26 por me lembrar!
PDF é um formato baseado em árvore. Ele tem um nó root seguido por um nó catalog (estas são muitas vezes o mesmo), seguido por um nó pages que tem vários nós page criança. Produtores / consumidores costumam usar uma implementação de árvore balanceada para armazenar um documento na memória.
jogos de xadrez de computador construir uma enorme árvore (formação) que podar em tempo de execução usando a heurística para chegar a um óptimo movimento.
alargamento é uma biblioteca de visualização escrito em AS. Você pode querer verificar a forma como os objetos de dados são mapeados. Em particular, o pacote flare.analytics utiliza uma estrutura fortemente gráfico, abrangendo árvores etc.
A rede social é o chavão atual na pesquisa CS. Escusado será dizer que as conexões / relações são muito naturalmente modeladas utilizando gráficos. Muitas vezes, as árvores são usadas para representar / identificar fenômenos mais interessantes. Como você responder a perguntas como "Será que Harry e Sally tem qualquer amigo comum (s)?"
Alguns muito sucesso árvores física / motores de jogos de construção para o movimento humano com precisão de simulação. Uma árvore neste caso normalmente correspondem a um conjunto de ações; O contexto determinará qual o caminho é levado para renderizar uma resposta particular.
Aprendizagem baseada Árvore de Decisão, na verdade formam uma área formidável de pesquisa de mineração de dados. Existem numerosos métodos famosos como ensacamento, aumentando, e as modificações do mesmo que o trabalho em árvores. Esse trabalho é muitas vezes usado para gerar um modelo preditivo.
Um problema comum em bioinformática é pesquisar bases de dados enormes para encontrar correspondências para uma determinada string de consulta. Tries são uma ocorrência comum lá.
Muito poucos de sucesso (de ações) comerciantes usam árvores de decisão no seu dia a dia de negociação - para escolher uma profissão, para sair um. Muitas vezes estes não são codificados em um programa de computador, mas escrito em algum lugar na parte de trás de seu notebook.

Dupe. Consulte este e este .

Outras dicas

A B no banco de dados do índice B * árvores significa equilibrado, não binário. A árvore é mantido a uma profundidade uniforme para assegurar vezes até mesmo de acesso.

O seu sistema de arquivos é uma estrutura de árvore. Então confira a fonte para qualquer sistema de arquivos livre.
O compilador gera um AST do seu código fonte, como um estágio intermediário. Então confira a fonte para qualquer compilador livre.

índices de banco de dados são normalmente armazenados como variamts de B * árvores que, apesar de seu nome não são árvores binárias.

Binary Trees têm sido utilizados para Space Partitioning e escondido remoção de superfície em 3D jogos de antigamente, eu acredito que um foi usado no jogo da Perdição.

Escrever um analisador descendente recursivo simples, e tê-lo gerar uma árvore de análise.
Bill-Of-Materiais estrutura utilizada na fabricação (como um automóvel consiste em subconjuntos, de forma recursiva, para baixo para o porcas e parafusos).
tabela de símbolo (como usado em um compilador).
plano de contas como usado no gerenciamento de projetos. Um projecto global tem subprojetos, a que taxas podem ser aplicadas.
Empresa estrutura organizacional:. Divisões, departamentos, etc
Índice de um documento.
descendentes de uma pessoa, ancestrais de uma pessoa.
-expressão s Qualquer Lisp, incluindo qualquer programa Lisp.

características de auto-completar em software (eg. Search Engine "sugestões", tipo IDE / símbolo de conclusão, nomes de e-mail e catálogo de endereços, etc) muitas vezes são implementados como Tries, que são estruturas de árvore.

Olhando para qualquer um dos produtos Datawarehousing você verá maneiras inteligentes de armazenamento e perfuração em forma de árvore dimensões. Você começa uma estrutura de árvore para localização (país, região, estado, m condado, cidade, etc) e tempo (ano, mês, dia, hora). Essas duas dimensões são comuns em muitos domínios, mas ainda há muito outros dados do mundo real também se presta para a árvore.

Por exemplo, no varejo de alimentos, na raiz da árvore você poderia ter mantimentos, que pode analisar laticínios, frutas e legumes etc. Após um único segmento que poderia ter. Latas de feijão, no nível mais alto você vai estar falando em cargas de camião, então você vai descer para paletes, caixas, tamanhos estanho. Todos os diferentes SKU (Stock Keeping Unit) são importantes para alguém dentro da loja ou empresa. Então diferentes tipos de feijão, diferentes fornecedores, fabricantes -. Exemplos de árvores para a mesma dimensão

Todos os diferentes produtos formam uma árvore enorme, com diferentes formas de corte e dicinng.

C ++ inclui uma série de coleções (set, multi_set, mapa, multi_map) que são normalmente implementados como árvores vermelhas e pretas, uma espécie de árvore equilibrada.

(O C ++ padrão não requer explicitamente essa implementação, mas este é o projeto mais simples que atenda aos requisitos de complexidade.)

Em um roteador lugar / switch Eu costumava trabalhar usamos um monte de estruturas de árvore, para a tabela de rota software foi utilizado um radix árvore (escolha muito comum para uma tabela de roteamento IP).

Nossa OSPF implementação feito uso de árvores vermelhas e pretas , nossa implementação BGP feita uso de skiplists .

skiplists Tecnicamente não são estruturas de árvore, mas eles são, na prática muito semelhante, e eles estão muito legal.

Nós definitivamente utilizado montes um pouco assim pensar sobre ele, é Já faz um tempo desde que eu trabalhei lá.

consultas DNS .. qualquer coisa usando um mapa usa AVL

System.Collections.Generic.SortedList usos uma árvore de busca binária como a implementação subjacente. O mesmo é verdadeiro para System.Collections.GenericSortedDictionary . Qualquer código usando SortedList ou SortedDictionary está usando uma árvore de pesquisa binária.

No meu projeto, uma edição e imputação sistema para dados de pesquisa / censo, usamos uma árvore de decisão binária para decidir quais variáveis ??de um registro para imputar ou não imputar. A árvore de decisão binária nos permite fazer de forma eficiente decisões sobre caminhos na árvore que deve e não deve tomar.

Penso que esta abordagem (embora talvez não apenas árvores binárias) é usado em aplicações de inteligência artificial assim

Nós usamos uma estrutura de árvore para modelar um sistema de classificação parcial. As peças são classificados em 'classes' que têm classes pai e assim por diante. As classes de nível superior conduzir o texto para guias em nosso UI catálogo. As aulas também são usados ??para aplicar preços regras, identificar 'pontos quentes' em um veículo onde as peças são exibidas em um 'configurador', etc. Nós modelar a árvore em SQL usando conjuntos aninhados de Joe Celko e carregá-los sob demanda na memória para melhor desempenho. Maioria das consultas comuns que fazemos são 'quem são meus descendentes' e 'é esta classe um antepassado meu?'

Muito útil

Classificação de objetos em geral é muitas vezes feito usando árvores. E muitas vezes, um gráfico seria muito mais adequado do que uma árvore, no entanto, uma árvore ofertas duas grandes vantagens sobre um gráfico:

Pode ser representado como uma lista (aninhada). Por exemplo, é muito mais fácil de mostrar uma grande árvore em papel (com títulos, subtítulos, parágrafos e listas aninhadas) ou na tela do computador do que um gráfico.
Você pode apontar para um item na árvore usando uma seqüência de caminho simples (ou uma pilha), por exemplo "HTTP / StackOverflow.com / Users / Dimitri C", algo que é muito mais difícil de fazer em um gráfico.

Há uma Treap implementado em ActionScript. Fontes:

O Treap faz parte do AS3Commons coleções quadro . A Treap modificado é usado para fazer as coleções SortedSet e SortedMap incluídos.

Coloque-se como a raiz da árvore e agora fazer seus pais como filhos da árvore e os pais dos pais como os filhos de árvore e isso pode fazer um caso de uso completo da árvore.

Assim implementar algo onde a hierarquia completa de família exigem que você pode usar a árvore para implementar isso.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow