Arvore patricia

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (653 palavras )
  • Download(s) : 0
  • Publicado : 24 de fevereiro de 2013
Ler documento completo
Amostra do texto
Agenda

• Pesquisa Digital e Árvore Trie

• Árvore Patricia e Busca.

• Inserção

• Remoção e Aplicação de Árvore Patricia

• Conclusão (Vantagens e Desvantagens)

• Bibliografia Pesquisa Digital

• A pesquisa digital é baseada na representação das chaves como uma sequência de caracteres ou de dígitos.

• Por exemplo, A representação de um string com uma sequência decaracteres e a representação de um número em binário.

B=010010

C=010011

H=011000

J=100001

M=101000

Pesquisa Digital

• A pesquisa digital está para árvores binárias de pesquisa comoradixsort está para os métodos de ordenação.

• Pesquisa não é baseada em comparação de chaves, mas sim em processamento feito sob a chave.

• O método é vantajoso quando as chaves são grandes e detamanho variável.

• Possui a possibilidade de localizar todas as ocorrências de uma determinada cadeia em um texto, com tempo de resposta logarítimico em relação ao tamanho do texto.

Árvore Trie• Definida em 1960 por Edward Fredkin.

• Vêm de Retrieval (Relacionado à Recuperação de Informações);.

• Para distinção com tree pronuncia-se try.

• No último nodo, o último caractere dapalavra sendo procurada deverá ter associado a si (como seu apontador) a posição da palavra no texto. Ortográficos,

Aplicações Abrangem: Corretores • Principais Autopreenchimento de Textos eArmazenamento.

Árvore Trie

• Uma trie é uma árvore M-ária cujos os nós são vetores de M componentes com campos correspondente ao dígitos ou caracteres que formam as chaves.

• Cada nó no nível irepresenta o conjunto de todas as chaves que começam com a mesma sequencia de i (digito ou caractere)

Busca Árvore Trie Binária
D W d 

• 

•  D

B=010010

Busca Árvore Trie Binária

•Percorremos a trie de acordo com os bits da chave.

B=010010

Busca Árvore Trie Binária

• Percorremos a trie de acordo com os bits da chave.

B=010010

Busca Árvore Trie Binária

•...
tracking img