fgbb

Pesquisa em Memória
Primária (cont.)
Livro “Projeto de Algoritmos” – Nívio Ziviani
Capítulo 5 http://www2.dcc.ufmg.br/livros/algoritmos/ Pesquisa Digital
 Pesquisa digital é baseada na representação das chaves como uma seqüência de caracteres ou de dígitos.
 Os métodos de pesquisa digital são particularmente vantajosos quando as chaves são grandes e de tamanho variável.  Um aspecto interessante quanto aos métodos de pesquisa digital é a possibilidade de localizar todas as ocorrências de uma determinada cadeia em um texto, com tempo de resposta logarítmico em relação ao tamanho do texto.
•Trie
•Patrícia
Algoritmos e Estrutura de Dados II

Trie
 Uma trie é uma árvore M -ária cujos nós são vetores de M componentes com campos correspondentes aos dígitos ou caracteres que formam as chaves.
 Cada nó no nível i representa o conjunto de todas as chaves que começam com a mesma seqüência de i dígitos ou caracteres.  Este nó especifica uma ramificação com M caminhos dependendo do (i + 1)-ésimo dígito ou caractere de uma chave. Algoritmos e Estrutura de Dados II

Trie
 Considerando as chaves como seqüência de bits (isto é,
M = 2), o algoritmo de pesquisa digital é semelhante ao de pesquisa em árvore, exceto que, em vez de se caminhar na árvore de acordo com o resultado de comparação entre chaves, caminha-se de acordo com comparação entre os bits de chave.

Algoritmos e Estrutura de Dados II

Exemplo
 Dada as chaves de 6 bits:
•B = 010010
•C = 010011
•H = 011000
•J = 100001
•M = 101000

Algoritmos e Estrutura de Dados II

Inserção das Chaves W e K na Trie Binária
W = 110110
K = 100010
 Faz-se uma pesquisa na árvore com a chave a ser inserida.
Se o nó externo em que a pesquisa terminar for vazio, cria-se um novo nó externo nesse ponto contendo a nova chave, exemplo: a inserção da chave W = 110110.
 Se o nó externo contiver uma chave cria-se um ou mais nós internos cujos descendentes conterão a chave já