Arvore patricia

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (336 palavras )
  • Download(s) : 0
  • Publicado : 27 de maio de 2012
Ler documento completo
Amostra do texto
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...
tracking img