Na ciência da computação , um ou um trie (pronunciado [ˈtriː] ou [ˈtraɪ] ) ou árvore de prefixo , é uma estrutura de dados na forma de uma árvore enraizada . É usado para armazenar uma tabela associativa onde as chaves são geralmente strings . Ao contrário de uma árvore de pesquisa binária , nenhum nó da classificação armazena a string à qual está associado. É a posição do nó na árvore que determina a cadeia correspondente.
Para qualquer nó, seus descendentes têm o mesmo prefixo em comum. A raiz está associada à string vazia . Os valores não são atribuídos a cada nó, mas apenas às folhas e alguns nós internos em uma posição que designa toda a string correspondente a uma chave.
O termo sort vem do inglês retrieval , que significa extração , pesquisa .
Os tipos foram descritos pela primeira vez pelo americano René de la Briandais em 1959. O termo trie foi cunhado dois anos depois por Edward Fredkin, que o pronuncia [ˈtriː] , após a segunda sílaba da palavra inglesa “Retrieval”. No entanto, muitos autores de língua inglesa pronunciam-no [ˈtraɪ] (como “try”), a fim de distingui-lo oralmente de “tree”.
As aplicações de um teste são numerosas. Esta estrutura de dados pode ser usada para implementar uma matriz associativa ou um conjunto , para encontrar redundâncias em alguns algoritmos de compressão (por exemplo, no dicionário de compressão de algoritmos para janela deslizante como LZ77 ), para implementar algoritmos de ortografia de conclusão automática , prefixo, sufixo ou aproximado procurar ...
Existem muitas variações de classificação, incluindo: