Whats a Patricia tree, and does anyone care?

I have done some reading, and I think i understand the concept behind it. However, is there any real world use for these, or is it simply another data structure being used to torture students as they prepare for their final exams?

Practical Algorithm to Retrieve Information Coded in Alphanumeric, but I don’t think anyone really cares! :slight_smile:

Alexnoe might be able to help you in this one :wink:

thats what i gathered from it, but as we didnt have any forum for programming, i had no idea where to put this query

the only applications i could think of, off the top of my head, had to do with ascii. oh well - thanks for reading.

Sure there is a use for it. If i’m not mistaken it’s used for IPv6 databases at the moment. However ,it’s slow and huge. (as is IPv6)


A compact representation of a trie where all nodes with one child are merged with their parents.

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.


For a complete source code , click here

lol, thanks - i think i may have found that page in my googling. but you confirmed my suspicion - their usage is largely academic. thanks :smiley:

There was a study done once where they just threw a bunch of rats in a cage, with nothing in there except a water dish.

After a few weeks, the rats werr so bored, they got into a pattern of forming a circle and rooting each other.

Sometimes I think academia is similar. The academics egg eachother on, but what they come out is strictly academic and of no real use in the real world.

the idea is that by learning to manipulate data into a fully functioning patricia tree with their guidelines, ill somehow have a deeper understanding of computer science, and will feel as one with myself. already i can feel the life force being sucked out of me, like jello through a really really long straw.

Hi there
There is a lot more use to Patricia Tree than of academic usage. For example, if you have a large database of names in your name directory server. If you go by the standard Trie method…you could be at loss. For example, you have names starting with Tom…as follows:

Tomas
Tomson
Tommy
Tomcat
Tom Haas
In case of a Trie, the first different letter starts at level ‘4’. While in Patricia Tree, it starts at level ‘2’. Another such example is, storage of URL-based feature matrix. You can have Patricia Tree in place for a better and faster search of the URL-based feature list using Patricia Tree.
So, unless there is some use…it shall never be included in your course work my dear friend. Consider this as a moral of the story.

/me nominates [B]calvinkiran[/B] as Amo Del Bump of the day!

This thread … was 3.5 years old … and very buried …

Yes, it looks like it might be a new CD Freaks record for resurrecting an old thread. This is like Return of the Mummy part 3.

calvinkiran, welcome to the forum! :slight_smile:

lmao it appears we have had many newbies …bringing life into old threads…

The CdFreaks forum has a huge lot of Google Spiders crawling around. If someone types in something in Google then the CdFreaks forum comes up as first hits quite often. There are new n00bs in town: the google n00bs. :slight_smile:

:disagree: I can beat you all… :bigsmile:


Hahahaha…nice find, ET! :bigsmile:

I found your thread researching something I read in a book about OSPF. According to “OSPF: Anatomy of an Internet Routing Protocol” by John Moy, Patricia trees are commonly used in IP routers to store and do lookups on their routing tables. That would make them actually extremely common, although maybe not something most programmers would need unless they are writing router code. They do seem appropriate for looking up routes (or other things maybe) using an IP address as a key when the number of comparisons must be minimized.

Anyways maybe that explains why you were expected to learn about them, although if such a huge and kind of important real world usage wasn’t pointed out in your class, I wonder if they really are as common as the author of the book I am reading seems to think.

We have a new award Winner for the :clap: :clap: Amo Del Bump of the Year! :clap: :clap:

MY sisters name is PATRICIA she`s blond by choice::eek:
does that mean she was found under a TREE.:wink:
:bigsmile:

Only if you believe the stalk does deliver babies.
I bet that chick is the most sought-after midwife in the world.

I wish someone would look up my routing table!!! :iagree: :bigsmile: :rolleyes: :o :iagree: :bigsmile: