Arvore Pesquisa 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 (Practical Algorithm To Retrieve Information Coded 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,