algoritmos-USP

Árvorie

Pesquisa Digital

Algoritmos e
Estruturas de Dados II

Árvorie (trie) é uma estrutura de índice útil quando as chaves são de tamanho variável
Uma árvorie é uma árvore de busca em mvias, m≥2, na qual a ramificação em qualquer nível é determinada por apenas uma parte do valor de chave e não pela chave inteira

A pesquisa digital está baseada na representação das chaves como uma seqüência de caracteres de um alfabeto
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

José Augusto Baranauskas
Departamento de Física e Matemática – FFCLRP-USP

[e-mail] http://dfm.ffclrp.usp.br/~augusto 2

Árvorie

Árvorie

O termo trie surgiu nos anos 60 e tem origem na palavra retrieval, uma vez que essa estrutura é usada basicamente na recuperação de dados
Na estrutura de dados trie as chaves são representadas caractere por caractere
Tries são usadas para fazer uma rápida busca em um texto grande
Cada chave é formada por uma combinação específica de símbolos do alfabeto
As combinações são de comprimento variável e ilimitado; portanto, as chaves podem ser palavras, seqüências binárias, códigos numéricos, etc

Em uma árvorie, as chaves são armazenadas e manipuladas de uma forma especial, pois são parcialmente compartilhadas entre os elementos
Ao invés de se comparar chaves inteiras entre si, as comparações são feitas componente a componente
Adicionalmente, as chaves são decompostas e as partes comuns entre elas são fundidas
3

Árvorie

4

Árvorie: Estrutura
Árvorie:
Considere a árvore seguinte que contém dois tipos de nós: nó de desvio e nó de informação

As árvories são boas para suportar tarefas de tratamento lexicográfico, tais como:

b

manuseamento de dicionários pesquisas em textos de grande dimensão construção de índices de