Árvore Patricia

A árvore PATRICIA - Practical Algorithm To Retrieve Information Coded In Alphanumeric - É um tipo de árvore de prefixos em que seqüências de nós com apenas um filho são compactados em um único nó.

Concebido por Donald Morrison, PATRICIA é um algoritmo para realização de buscas em árvores com as chaves dos nós representadas em binário, sem armazenar as chaves nos nós. O nome é um acrônimo de “Practical Algorithm To Retrieve Information Coded In Alphanumeric”, e o método é particularmente útil para tratamento de chaves de tamanho variável extremamente longas, tais como títulos e frases. No caso de pesquisas analíticas, os dados podem tirar proveito deste método desde que as informações sejam armazenadas como cadeias de texto.

Uma restrição dessas árvores é a necessidade de não haver um elemento que seja prefixo de outro, o que pode facilmente ser obtido se necessário.