ED - 08 - Tries

Prévia do material em texto

Tries
Joaquim Quinteiro Uchôa
Juliana Galvani Greghi
Conceitos Básicos
Uma trie, ou árvore de prefixos, é uma árvore ordenada, que 
pode ser usada para armazenar um array associativo em que as 
chaves são normalmente cadeias de caracteres.
Diferente de uma árvore binária de busca, nenhum nó armazena 
a chave associada a ele. Ao invés disso, a posição do nó na árvore 
é que define a chave. 
Todos os descendentes de um nó tem um prefixo comum da 
string associada ao nó e a raiz geralmente é associada com a 
string vazia. 
Exemplo 1
a trie para as chaves "A", 
"to", "tea", "ted", "ten", "i", 
"in" e "inn" poderia ser 
representada da seguinte 
forma (desconsidere os 
números).
Exemplo 2
Trie com as palavras 
“tree”, “trie”, “algo”, 
“assoc”, “all” e “also”. 
Exemplo 3
Formas de Implementação
Tries podem ser implementadas de diferentes maneiras, por 
exemplo como um autômato finito determinístico. Também 
podem ser implementados como uma árvore n-ária.
Dependendo os valores armazenados, como em um hashing 
expansível (forma de armazenamento em arquivos utilizando 
hash para encontrar a posição no disco), em que os dados são 
strings binárias, é possível armazenar utilizando arranjos.
Árvores PATRICIA
A árvore PATRICIA, que é uma árvore de prefixos binária, é uma 
representação compacta de uma trie onde os nós que teriam 
apenas um filho são agrupados nos seus antecessores. 
PATRICIA significa Practical Algorithm to Retrieve Information 
Coded in Alphanumeric.
Exemplo 4
Exemplo 5