Arvore patricia

ÁRVORES PATRICIA

 Vêm de Retrieval (Relacionado à Recuperação de Informações)
 Para distinção com tree pronuncia-se try
 Cada nó contém informações sobre um ou mais símbolos do alfabeto utilizado
 Alfabeto pode abranger: {0,1} , {A,B,C,D...} ou {0,1,2,3,4...} e mais o caracter nulo (ou branco)
 caminho da raiz (root) da trie para qualquer outro nó em representa um prefixo de uma string
 Principais Aplicações Abrangem: Corretores Ortográficos, Auto-Preenchimento de Textos e Armazenamento/Busca de Documentos XML
 Em Tries Compactas todos os descendentes diretos do mesmo pai são agrupados
 No último nodo, o último caracter da palavra sendo procurada deverá ter associado a si (como seu apontador) a posição da palavra no texto
 Trie Compactada Binária
 Caminhos que possuem nós com apenas 1 filho são agrupados em uma única aresta
 Diferente das Tries não armazena informações nos nodos internos, apenas contadores e ponteiros para cada sub-árvore descendente.

Exemplo de Representação

Campo Avançar
 Registro Acumulativo que Integra todos os Nodos Exceto os Folhas
 Identifica qual a Posição do Caracter da Chave Informada que deve ser analisado Campo Comparar Com
 Apresenta o Caracter que deve ser Comparado ao Caracter da Chave Informada
 Como nas Árvores Binárias de Busca, após a análise, se a Chave é Menor ou Igual ao Nodo ela é Alocada/Consultada à Esquerda senão à Direita

Exemplo de Consulta

Etapas:
 Primeiro Nodo Informa pra Comparar 7º Caractere da Palavra com “a”.
 Como “t” é maior que “a” desloca-se pra sub-árvore da direita.
 Compara-se agora o Caractere 8º Caractere da Chave com “a”
 Como “ó” é maior que a ele percorre a sub-árvore da direita e acha a palavra.

Etapas: