Arvore Patrícia

Arvore Patrícia

Practical Algorithm To Retrieve Information Coded in Alphanumeric

As arvores Patrícia são arvores de prefixo, São também formas mais compactas de uma trie com a diferença de armazenar sílabas ao invés de letras.

- Seu nome vem de Patrícia (PracticalAlgorithmToRetrieveInformationCoded in Alphanumeric)

- Uma Chave não corresponde a um nó e sim a uma sílaba espalhada ao longo de um ramo consequentemente: Um conjunto de nós encadeados

- Não Possui ordenação ou balanceamento, o mais próximo de ordenação é que os nós seguem a ordem que forma a chave.

- A Raiz é NULL após a inserção de duas chaves com sílabas iniciais diferentes

- Um nó é folha quando não possui filhos

- Uma chave termina ao chegar numa folha

- não é obrigatório o usos de caracteres, poderiam ser armazenados números.

A ESTRUTUA

A informação de um nó é simples: uma sílaba

Porem a peculiaridade é que ela é uma arvore n-aria, podendo ter de nenhum até n filhos (Afinal não sabemos quantas palavras seriam formadas com aquela letra).

Sendo assim concluímos que seu nó nada mais é do que uma String e uma quantidade não determinada e ordenadas de ponteiros para os filhos (Os ponteiros devem estar em ordem das letras que os compõe).

Podemos usar duas estruturas que representam isso:

- um vetor, caso a quantidade de filhos seja limitada e do tamanho de cada sílaba do nó.

- Uma lista de ponteiros para os filhos (perceba que aqui a quantidade de filhos dependeria somente da quantidade de memória disponível para armazenar) e uma String (C++ e Java).

Aplicações

Como todas as estruturas existem varias aplicações praticas, algumas delas:

- Dicionário: cada chave é uma palavra

- Auto completar: Cada chave é uma palavra, a partir da ultima letra digitada podendo achar todos os ramos seguintes que são possíveis chaves a serem digitadas.

- Base Genética: Como uma base de dados em memória primaria cada chave é uma base nitrogenada (A,G,C,T) ou conjunto delas, cada ramo é uma das duas fitas do DNA, a folha aponta para aquele que gene de uma lista (chave) condiciona.

Pegamos um gene de uma lista (que representa o DNA em estudo) e procuramos o que aquele gene condiciona a partir da informação presente na arvore.

- Base Bibliotecária: Cada chave é uma obra e as folhas apontam para localização da obra a pesquisa provavelmente se tornaria mais rápida do que uma trie.

Inserção

Inicialmente é feita uma busca da chave na arvore

Se a chave já existe nada é feito

Se não existe nem a primeira sílaba a chave é alocada.

Se