Tries

Busca Digital
(Trie e Árvore Patrícia)
Estrutura de Dados II
Jairo Francisco de Souza

Introdução
• No problema de busca, é suposto que existe um conjunto de chaves S={s1, …, sn} e um valor x correspondente a uma chave que se deseja localizar em S.
• Nos métodos vistos até agora, tentavam estruturar
S de alguma forma conveniente e, através de comparações de x com si de S, tentar localizar x em S.
• Nesses métodos, cada chave si, bem como a chave desejada x, é tratada como um único elemento indivisível. Introdução
• Porém, nem sempre as chaves serão do mesmo tamanho e podem exceder o espaço definido para elas. • Suponha que se deseje armazenar um texto literário para, em seguida, tentar localizar frases nesse texto.
• Neste caso, o conjunto S de chaves corresponderia às frases armazenadas e cada si à uma frase passível de ser buscada.
• Neste cenário, a busca digital é a mais apropriada.

Busca digital
• A diferença entre a busca digital e a busca estudada até agora é que a chave não é tratada como um elemento indivisível.
• Isto é, assume-se que cada chave é constituída de um conjunto de caracteres ou dígitos definidos em um alfabeto apropriado.
• Em vez de se comparar a chave procurada com as chaves do conjunto armazenado, a comparação é efetuada, individualmente, entre os dígitos que compõem as chaves, dígito a dígito.
• O método de pesquisa digital é análogo à pesquisa manual em dicionários: com a primeira letra da palavra são determinadas todas as páginas que contêm as palavras iniciadas por aquela letra e assim por diante

Introdução
• TRIE vem de RETRIEVAL –
RECUPERAÇÃO
• Pronúncia: TRI ou TRAI

• É um tipo de árvore de busca. • Idéia geral: usar partes das CHAVES como caminho busca
• Origem: anos 60 por
Edward Fredkin

CHAVES: Características
• Cada chave formada por palavras sobre um alfabeto • Palavras com tamanho variável e ilimitado
• Em geral associam-se chaves a elementos ou
registros,