Tries

Seminário de Programação com arquivos

Índice

Tries

Prof.: Dalessandro
Dupla: João Paulo e Kelvin Lucas

Trie

A trie para as chaves "to", "te", "tea", "Ted", "ten", "i", "in" e "inn".
Em ciência da computação , uma trie , também chamada de árvore digitail e às vezes raiz de árvore ou prefixo árvore (como eles podem ser pesquisados por prefixos), é uma árvore ordenada em estrutura de dados que é usado para armazenar um conjunto dinâmico ou array associativo onde as chaves são geralmente strings. Ao contrário de uma árvore de pesquisa binária , nenhum nó da árvore armazena a chave associada a esse nó, em vez disso, a sua posição na árvore define a chave com a qual ele está associado. Todos os descendentes de um nó tem um comum prefixo da seqüência associada a esse nó, e a raiz está associada com a string vazia . Valores não são normalmente associados com cada nó, apenas com as folhas e certos gânglios internas que correspondem às teclas de interesse. Para a apresentação do espaço otimizado de árvore de prefixo, ver árvore de prefixo compacto .
O termo trie foi criad por Edward Fredkin , que pronuncia "tree"(árvore), como na palavra recuperação. No entanto, outros autores pronunciá-lo "tri"(tentar), numa tentativa distingui-lo verbalmente de "tree".
No exemplo mostrado, as teclas são listados nos nós e os valores abaixo delas. Cada palavra Inglês completa tem um valor inteiro arbitrário associado a ele. Um trie pode ser visto como um autómato finito determinista , embora o símbolo em cada aresta é frequentemente implícito na ordem dos ramos.
Não é necessário que as chaves sejam explicitamente armazenados nos nós. (Na figura, as palavras são apresentadas só para ilustrar a forma como funciona o trie.)
Apesar de tentativas são mais comumente introduzido por cadeias de caracteres, eles não precisam ser. Em particular, um bit a bit trie é introduzido nos bits individuais que compõem um tamanho fixo curto de bits como um número inteiro ou endereço de