javascript-algorithms
Trie
Na ciência da computação, uma trie, também chamada de árvore digital (digital tree) e algumas vezes de radix tree ou prefix tree (tendo em vista que eles podem ser pesquisados por prefixos), é um tipo de árvore de pesquisa, uma uma estrutura de dados de árvore ordenada que é usado para armazenar um conjunto dinâmico ou matriz associativa onde as chaves são geralmente strings. Ao contrário de uma árvore de pesquisa binária (binary search tree), nenhum nó na árvore armazena a chave associada a esse nó; em vez disso, sua posição na árvore define a chave com a qual ela está associada. Todos os descendentes de um nó possuem em comum o prefixo de uma string associada com aquele nó, e a raiz é associada com uma string vazia. Valores não são necessariamente associados a todos nós. Em vez disso, os valores tendem a ser associados apenas a folhas e com alguns nós internos que correspondem a chaves de interesse.
Para a apresentação otimizada do espaço da árvore de prefixo (prefix tree), veja árvore de prefixo compacto.
