Patricia tree

Must read : http://books.google.co.in/books?id=ESM3CWY5xRYC&pg=PA562&lpg=PA562&dq=patricia+tree+routing&source=bl&ots=b4pXXGtACY&sig=TISdjQMrPkEPDjorJMQelA9zx7U&hl=en&sa=X&ei=PZAbT9lw0IisB4Pa4eQN&ved=0CDwQ6AEwBDgK#v=onepage&q=patricia%20tree%20routing&f=false

Patricia stands for "Practical algorithm to retrieve information coded in alphanumeric",

Trie : A tree for storing strings in which there is one node for every common prefix. The strings are stored in extra leaf nodes

Node : (1) A unit of reference in a data structure. Also called a vertex in graphs and trees. (2) A collection of information which must be kept at a single memory location.

Child : An item of a tree referred to by a parent item. See the figure at tree. Every item, except the root, is the child of some parent.


A Patricia tree is related to a Trie. The problem with Tries is that when the set of keys is sparse, i.e. when the actual keys form a small subset of the set of potential keys, as is very often the case, many (most) of the internal nodes in the Trie have only one descendant. This causes the Trie to have a high space-complexity.

Patricia tree : Binary digital tree
Specs :

n external nodes with key values
n-1 internal nodes




---------

Tries were invented by E. Fredkin in 1960

Patricia trees Patricia stands for "Practical algorithm to retrieve information coded in alphanumeric", invented by D. R. Morrison, 1968

The idea is to take a trie and get rid of any nodes that only have one child. Instead, each remaining node is labeled with a character position number which would have given that node's depth in the original uncompressed trie. We now have the problem that keys are no longer uniquely specified by the search path, so we have to store the key itself in the appropriate leaf. The storage requirement is now kn pointers, where n is the number of keys and k is the size of the alphabet. This is often significantly less than s(k + 1), particularly if the keys are very long.

A Patricia tree alone is far from efficient.