trie

Em ciência da computação, uma trie, ou árvore de prefixos, é uma estrutura de dados do tipo árvore ordenada, que pode ser usada para armazenar um array associativo em que as chaves são normalmente cadeias de caracteres. Edward Fredkin, o inventor, usa o termo trie (do inglês "retrieval") (recuperação), porque essa estrutura é basicamente usada na recuperação de dados. De acordo com essa etimologia ele é pronunciado [tri] ("tree"), embora alguns encoragem o uso de [traɪ] ("try") de modo a diferenciá-lo do termo mais geral tree. Ao contrário de uma árvore de busca binária, nenhum nó nessa árvore armazena a chave associada a ele; ao invés disso, ela é determinada pela sua posição na árvore. Todos os descendentes de qualquer nó têm um prefixo comum com a cadeia associada com aquele nó, e a raiz é associada com a cadeia vazia. Normalmente, valores não são associados com todos os nós, apenas com as folhas e alguns nós internos que correspondem a chaves de interesse. No exemplo mostrado na imagem, as chaves estão listadas nos nós e os valores abaixo dos mesmos. Cada palavra completa tem um valor inteiro associado a ela. Uma trie pode ser vista como um autômato finito determinístico, embora o símbolo em cada aresta é freqüentemente implícito na ordem dos galhos. Não é necessário que as chaves sejam explicitamente armazenadas nos nós. (Na imagem, as palavras são mostradas apenas para ilustrar como a trie funciona.) Embora seja o mais comum, tries não precisam utilizar cadeias de caracteres como chaves. Os mesmos algoritmos podem facilmente ser adaptados para funções similares de listas ordenadas de qualquer construção, como permutações em uma lista de dígitos, etc.