Arvore patricia

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 cada aresta, 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 lphanumeric Significado: 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 mais eficientes.




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 chaves distintas 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 o registro 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 de inserçã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 e encontramos 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