Arvore patricia

Páginas: 2 (336 palavras) Publicado: 27 de maio de 2012
Trabalho de Classificação e Pesquisa
Árvore Patricia




Introdução:
A Árvore Patricia foi criada por Donald R. Morrison, ela foi desenvolvida para possuir nós com apenas um filho em cadaaresta, não armazena informações nos nodos internos contendo apenas contadores e ponteiros para cada sub-árvore descendente.

P ratical A lgorithm To R etrieve I nformation C oded In A lphanumericSignificado: Algoritmo Prático para Recuperar Informação Codificada em Alfanumérico




Objetivos:
Contornar as desvantagens e tornar os métodos de inserção, remoção e busca ainda maiseficientes.




Justificativa
Árvores Patrícia buscam tornar mais compactas as Tries e com isso ganham em velocidade, por outro lado, não possuem escalabilidade adequada quando se têm muitas chavesdistintas para um mesmo caractere.




Desenvolvimento

O algoritmo percorre as chaves até que encontre um caractere diferente no mesmo índice da string. É alocado um nó pai contendo oregistro com Avançar = n e Compara Com = i. Vale lembrar que o algoritmo de inserção trabalha juntamente com o de consulta.  A implementação do algoritmo de remoção é mais simples se comparado com o deinserção. Ele trabalha juntamente com o de consulta para localizar o nó a ser deletado.  Procuraremos pela palavra DOMANDO. O primeiro nó manda comparar o caractere 1 da chave com “c”. Como “d” é maior,deslocamos para a direita. Agora o segundo com “a”. O caractere “o” de domando é maior que “a”, então vamos para a direita. Agora o quarto com “a” é igual, desta forma, vamos para a esquerda eencontramos a palavra.  Ajustarmos os ponteiros, o nó controlador que passa a ser apontado pelo anterior ao deletado, teve o campo Avançar modificado pelo acúmulo do seu valor anterior com o nó deletado. 


Conclusão:
Árvores Patrícia buscam tornar mais compactas as Tries, com isso ganham em velocidade, mas por outro lado não possuem escalabilidade adequada quando se têm muitas chaves...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Arvore patricia
  • Trabalho Arvore Patricia
  • Arvore Pesquisa Patrícia
  • Patricia
  • Patricia
  • patricia
  • Patricia
  • patricia

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!