Arvore patricia

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 de caracteres 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 como radixsort 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 de tamanho 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 da palavra 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 e Armazenamento.

Á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 i representa 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

•