Laboratório

Árvore Patricia
Partindo da necessidade de localizar palavras-chaves ou strings em arquivos enormes, que contenham uma grande quantidade das mesmas em conjunto, de maneira rápida e eficiente foi desenvolvida a árvore Patricia – “Practical Algorithm To Retrieve Information Coded In Alphanumeric”. Isso se deve ao fato de que os arquivos que guardam os textos estão armazenados em disco e as palavras que os formam possuem tamanhos bastante variáveis e podem ser divididas, o que exclui a utilização de estruturas de dados comuns como arvores binárias, além de um de outro aspecto muito relevante tratado pela Patricia que é a busca por segmentos de palavras se assim o usuário desejar.
Outra motivação para a utilização das árvores Patricias surge ao observarmos que ela aplica métodos que diminuem a altura da árvore, transformando-a em uma compacta estrutura de dados, capaz de ser armazenada na memória principal e usada, como exemplo, em sistemas de recuperação de informação de forma mais eficiente.
Em comparação com as árvores Trie as Patricias podem ser consideradas muito mais eficientes, pois ao invés de armazenar em cada nodo um caractere – como fazem as Trie – armazena strings, o que agiliza muito a busca. É desta maneira que as árvores Patricias conseguem diminuir a sua altura, ou seja, ela agrupa nodos de uma árvore TRIE que possuem apenas um filho; desta forma, diminuindo o numero de comparações e se tornando mais eficiente sendo muito mais utilizada desde busca por palavras em textos até em roteamento de IPs.
A árvore Patricia possui também variantes como exemplo a HAT-trie. A HAT-trie é uma árvore que oferece cadeia de armazenamento e recuperação de dados utilizada para gerenciar strings em memória de maneira mais eficiente.