187810720199

Sumário

1. Introdução 2
2. O que são Árvores Patricia 3
3. Por que Patricia 3 3.1. Objetivo 3
4. Características 4
5. Complexidade 4
6. Como Funciona 4 6.1. Inserção 4 6.2. Remoção 5 6.3. Pesquisa 5 6.4. Algoritmo 5
7. Vantagens e Desvantagens 6 7.1. Vantagens 6 7.2. Desvantagens 6
8. Exemplo 6
9. Conclusão 8
10. Referências 8

Introdução

A Árvore Patrícia foi criada por Donald R. Morrison, ela foi desenvolvida para possuir nós com apenas um filho em cada aresta. Não armazena informações nos nodos internos contendo apenas contadores e ponteiros para cada sub-árvore descendente.

O que são Árvores Patricia

Uma árvore patricia consiste em uma trie compactada, sendo similar a uma trie comum (Trie é uma estrutura de dados que pode ser usada para fazer uma rápida busca em um grande texto.), mas garantindo que cada nó interno tem no mínimo grau 2. Fazendo uma compactação de modo que caminhos em que os nós têm apenas um filho cada, são agrupados em uma única aresta. Chamamos um nó n em uma trie comum de critical, se n tem no mínimo dois filhos, ou se n é a raiz . Fazemos, portanto, a conversão de uma trie comum para uma trie compacta com tentativas de substituição de um caminho com vários nós (n0,n1,n2,...,nk), para k>=0, por uma única aresta (n0,nk) que corresponda ao caminho compactado, desde que: Os nós n0 e nk são critical, mas ni não á critical, para 0 < i < k. Cada nó ni, para 0 < i < k, tem apenas um filho, o nó ni + 1. Assim, os nós em uma Árvore Patricia são associados a strings, as quais são substrings das chaves armazenadas na árvore.

Por que Patricia

Ao contrário do que muitos pensam inicialmente, a denominação "Patricia" trata-se de uma sigla para Pratical Algorithm To Retrieve Information Coded In Alphanumeric.

1 Objetivo

Contornar as desvantagens e tornar os métodos de inserção, remoção e