Arvore 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: