Trabalho Arvore Patricia

ANHANGUERA EDUCACIONAL LTDA.
FACULDADE ANHANGUERA DE CAMPINAS - UNIDADE 3
CIÊNCIA DA COMPUTAÇÃO
CLASSIFICAÇÃO E PESQUISA

AENDERSON ROMALDINO DE OLIVEIRA - 627121530
ALDO MOREIRA FILHO - 6248236345
CLAUDIO RAGNER LEMOS CORREIA - 6814014026
PAULO HENRIQUE TAVANO - 6618352994
JANAINA MESSIAS – 1299109371
JULIO MITICA - 1001761008

ATIVIDADES

PROF. PATRICIA

CAMPINAS - MAIO DE 2015

Arvore Patricia (Pratical Algorithm to Retrieve Information Coded in Alphanumeric)

O que é ?
PATRICIA é um algoritmo para realização de buscas em árvores com as chaves dos nós representadas em binário, sem armazenar as chaves nos nós. O nome é um acrônimo. No caso de pesquisas analíticas, os dados podem tirar proveito deste método desde que as informações sejam armazenadas como cadeias de texto, a árvore patricia é alfanumerico sua construção é baseada em um método digital.
Foi apresentada por Donald R. Morrison com o intuito inicial de a busca de arquivos em bibliotecas.

Vantagem e desvantagem.
Tem como vantagem e característica principal, armazenar um número de posições para qual é movido para a frente antes de fazer a próxima comparação, assim elimina comparações desnecessárias e melhora o desempenho.
Tem a desvantagem de produzir apenas duas subárvores. Se mais do que duas chaves são distintas na mesma posição do caracter, é necessário adicionar nodos extras ao índice para separá-lo.
Conclusão.
Árvores Patrícia buscam tornar mais compactas as Tries com isso ganham em velocidade, por outro lado não possuem escalabilidade adequada quando se têm muitas chaves distintas para um mesmo caracter.

Exemplo de uma arvore Patricia.

No exemplo acima, existe alteração na primeira letra (1), se for seguir a esquerda, a primeira letra é “C”, se for a direita é “D”;
Depois, contando-se 4 letras,tem-se alteração (4), ou seja, 5ª letra (1+4), se for seguir a esquerda, a letra é “A”, se for a direita, tem-se a palavra “casco”;
Na proxima letra (1)(6ª letra), tem alteração