## What is the difference between trie and radix trie data structures?

76

39

Are the trie and radix trie data structures the same thing?

If they are same, then what is the meaning of radix trie (AKA Patricia trie)?

4

Am I the only one who finds it a bit annoying that the tag is `radix-tree` rather than `radix-trie`? There are quite a few questions tagged with it, moreover.

– errantlinguist – 2016-11-13T10:04:08.160

92

A radix tree is a compressed version of a trie. In a trie, on each edge you write a single letter, while in a PATRICIA tree (or radix tree) you store whole words.

Now, assume you have the words `hello`, `hat` and `have`. To store them in a trie, it would look like:

``````    e - l - l - o
/
h - a - t
\
v - e
``````

And you need nine nodes. I have placed the letters in the nodes, but in fact they label the edges.

In a radix tree, you will have:

``````            *
/
(ello)
/
* - h - * -(a) - * - (t) - *
\
(ve)
\
*
``````

and you need only five nodes. In the picture above nodes are the asterisks.

So, overall, a radix tree takes less memory, but it is harder to implement. Otherwise the use case of both is pretty much the same.

Thanks...Can you provide me with a good resource to study trie DS ... That would be of great help ... – Daggerhunt – 2013-02-05T13:58:53.047

I believe only thing I used when I first implemented Trie was the wikipedia article. I am not saying it is perfect but it is good enough.

– Ivaylo Strandjev – 2013-02-05T14:00:12.407

1

can i say that searching in TRIE is faster than Radix tree? Because in TRIE if you wan to search the next char you need to see the ith index in the child array of the current node but in radix tree you need search for all the child nodes sequentially. See the implementation https://code.google.com/p/radixtree/source/browse/trunk/RadixTree/src/ds/tree/RadixTreeImpl.java

– Trying – 2013-12-13T00:18:48.607

3Actually in a radix tree you can't have more than a single edge starting with the same letter so you can use the same constant indexing. – Ivaylo Strandjev – 2013-12-13T06:19:41.107

Suppose we have a forth word, `hatchet`, how would it fit in the upper structures? – mohsenmadi – 2015-06-01T02:14:48.107

@mohsenmadi There would probably be a node for the NUL terminating `'\0'` byte, meaning hat is really `h - a - t - \0` and before the `\0` there would be another branch for `c - h - e - t - \0` – autistic – 2015-06-17T06:19:34.193

@IvayloStrandjev I would recommend taking it with a grain of salt; either the downvoter couldn't be bothered leaving constructive criticism or they just plain didn't like your answer (e.g. it offended their sensitive souls). It's not a requirement that they leave constructive criticism, after all. Though it is a requirement that you know When should I comment? so you can avoid your comments being flagged for deletion, as technically this kind of comment serves no use for future visitors. Nonetheless, if it helps, I can hazard a guess:

– autistic – 2016-02-07T00:34:36.113

I think you were downvoted because you seem to be using wikipedia as a reference, wikipedia is only as credible as it's references, and references are often few and far between. – autistic – 2016-02-07T00:34:47.060

@Seb in fact I am not using wikipedia as a reference in my answer(though I usually do) I use it in my comment only and in a bit different context. – Ivaylo Strandjev – 2016-02-07T07:04:37.357

1@Trying Algorithmically Radix is faster than TRIE, that's why its worth doing the compression. Fewer nodes to load and less space are generally better. That said, implementation quality can vary. – Glenn Teitelbaum – 2016-04-14T14:18:22.143

@GlennTeitelbaum Have you ever implemented a classical (not wikipedian, rather the way it was originally defined) PATRICIA trie? They come as one node per actual insertion, and insert and find are O(k) worst case time complexity... [edit: though admittedly, they are much more like a graph with cycles pointing back up the tree] – autistic – 2016-08-18T03:23:48.243

@ Ivaylo Strandjev - Would really appreciate your feedback on the post stackoverflow.com/questions/40087385/… on Radix Tree. Thnks in adv – KGhatak – 2016-10-20T12:08:17.513

@IvayloStrandjev, Isn't a radix tree slower when modifying the tree ? – Pacerier – 2017-11-12T21:39:35.007

Is the example for the radix tree, in this answer, a Patricia Trie? – firo – 2018-09-10T02:50:30.373

59

My question is whether Trie data structure and Radix Trie are the same thing?

In short, no. The category Radix Trie describes a particular category of Trie, but that doesn't mean that all tries are radix tries.

If they are[n't] same, then what is the meaning of Radix trie (aka Patricia Trie)?

I assume you meant to write aren't in your question, hence my correction.

Similarly, PATRICIA denotes a specific type of radix trie, but not all radix tries are PATRICIA tries.

### What is a trie?

"Trie" describes a tree data structure suitable for use as an associative array, where branches or edges correspond to parts of a key. The definition of parts is rather vague, here, because different implementations of tries use different bit-lengths to correspond to edges. For example, a binary trie has two edges per node that correspond to a 0 or a 1, while a 16-way trie has sixteen edges per node that correspond to four bits (or a hexidecimal digit: 0x0 through to 0xf).

This diagram, retrieved from Wikipedia, seems to depict a trie with (at least) the keys 'A', 'to', 'tea', 'ted', 'ten' and 'inn' inserted:

If this trie were to store items for the keys 't', 'te', 'i' or 'in' there would need to be extra information present at each node to distinguish between nullary nodes and nodes with actual values.

### What is a radix trie?

"Radix trie" seems to describe a form of trie that condenses common prefix parts, as Ivaylo Strandjev described in his answer. Consider that a 256-way trie which indexes the keys "smile", "smiled", "smiles" and "smiling" using the following static assignments:

``````root['s']['m']['i']['l']['e']['\0'] = smile_item;
root['s']['m']['i']['l']['e']['d']['\0'] = smiled_item;
root['s']['m']['i']['l']['e']['s']['\0'] = smiles_item;
root['s']['m']['i']['l']['i']['n']['g']['\0'] = smiling_item;
``````

Each subscript accesses an internal node. That means to retrieve `smile_item`, you must access seven nodes. Eight node accesses correspond to `smiled_item` and `smiles_item`, and nine to `smiling_item`. For these four items, there are fourteen nodes in total. They all have the first four bytes (corresponding to the first four nodes) in common, however. By condensing those four bytes to create a `root` that corresponds to `['s']['m']['i']['l']`, four node accesses have been optimised away. That means less memory and less node accesses, which is a very good indication. The optimisation can be applied recursively to reduce the need to access unnecessary suffix bytes. Eventually, you get to a point where you're only comparing differences between the search key and indexed keys at locations indexed by the trie. This is a radix trie.

``````root = smil_dummy;
root['e'] = smile_item;
root['e']['d'] = smiled_item;
root['e']['s'] = smiles_item;
root['i'] = smiling_item;
``````

To retrieve items, each node needs a position. With a search key of "smiles" and a `root.position` of 4, we access `root["smiles"[4]]`, which happens to be `root['e']`. We store this in a variable called `current`. `current.position` is 5, which is the location of the difference between `"smiled"` and `"smiles"`, so the next access will be `root["smiles"[5]]`. This brings us to `smiles_item`, and the end of our string. Our search has terminated, and the item has been retrieved, with just three node accesses instead of eight.

### What is a PATRICIA trie?

A PATRICIA trie is a variant of radix tries for which there should only ever be `n` nodes used to contain `n` items. In our crudely demonstrated radix trie pseudocode above, there are five nodes in total: `root` (which is a nullary node; it contains no actual value), `root['e']`, `root['e']['d']`, `root['e']['s']` and `root['i']`. In a PATRICIA trie there should only be four. Let's take a look at how these prefixes might differ by looking at them in binary, since PATRICIA is a binary algorithm.

``````smile:   0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0000 0000  0000 0000
smiled:  0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0110 0100  0000 0000
smiles:  0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0111 0011  0000 0000
smiling: 0111 0011  0110 1101  0110 1001  0110 1100  0110 1001  0110 1110  0110 0111 ...
``````

Let us consider that the nodes are added in the order they are presented above. `smile_item` is the root of this tree. The difference, bolded to make it slightly easier to spot, is in the last byte of `"smile"`, at bit 36. Up until this point, all of our nodes have the same prefix. `smiled_node` belongs at `smile_node[0]`. The difference between `"smiled"` and `"smiles"` occurs at bit 43, where `"smiles"` has a '1' bit, so `smiled_node[1]` is `smiles_node`.

Rather than using `NULL` as branches and/or extra internal information to denote when a search terminates, the branches link back up the tree somewhere, so a search terminates when the offset to test decreases rather than increasing. Here's a simple diagram of such a tree (though PATRICIA really is more of a cyclic graph, than a tree, as you'll see), which was included in Sedgewick's book mentioned below:

A more complex PATRICIA algorithm involving keys of variant length is possible, though some of the technical properties of PATRICIA are lost in the process (namely that any node contains a common prefix with the node prior to it):

By branching like this, there are a number of benefits: Every node contains a value. That includes the root. As a result, the length and complexity of the code becomes a lot shorter and probably a bit faster in reality. At least one branch and at most `k` branches (where `k` is the number of bits in the search key) are followed to locate an item. The nodes are tiny, because they store only two branches each, which makes them fairly suitable for cache locality optimisation. These properties make PATRICIA my favourite algorithm so far...

I'm going to cut this description short here, in order to reduce the severity of my impending arthritis, but if you want to know more about PATRICIA you can consult books such as "The Art of Computer Programming, Volume 3" by Donald Knuth, or any of the "Algorithms in {your-favourite-language}, parts 1-4" by Sedgewick.

Would you pls help me understand the significance of the term "Radix"! I understand how, in a natural way, we may try to turn a TRIE into a compact TRIE by allowing multiple symbols/edges coalesce into one edge. However, I'm not able to discern why an un-compacted TRIE (simply a TRIE) cannot be termed as Radix TRIE. – KGhatak – 2016-09-15T14:49:12.120

@ Seb - Would really appreciate your feedback on the post http://stackoverflow.com/questions/40087385/significance-of-the-term-radix-in-radix-tree on Radix Tree. Thnks in adv.

– KGhatak – 2016-10-18T05:56:31.220

@BuckCherry I'd love to be able to, but please realise as my computer was stolen I wouldn't be able to put the effort into an adequate response. – autistic – 2016-10-20T05:12:06.330

good explanation ! – tauseef_CuriousGuy – 2018-05-31T06:40:43.070

15

TRIE:
We can have a search scheme where instead of comparing a whole search key with all existing keys (such as a hash scheme), we could also compare each character of the search key. Following this idea, we can build a structure (as shown below) which has three existing keys – “dad”, “dab”, and ”cab”.

``````         [root]
...// | \\...
|  \
c   d
|    \
[*]    [*]
...//|\.  ./|\\...        Fig-I
a       a
/       /
[*]      [*]
...//|\..  ../|\\...
/        /   \
B        b     d
/        /       \
[]       []       []

``````

This is essentially an M-ary tree with internal node, represented as [ * ] and leaf node, represented as [ ]. This structure is called a trie. The branching decision at each node can be kept equal to the number of unique symbols of the alphabet, say R. For lower case English alphabets a-z, R=26; for extended ASCII alphabets, R=256 and for binary digits/strings R=2.

Compact TRIE:
Typically, a node in a trie uses an array with size=R and thus causes waste of memory when each node has fewer edges. To circumvent the memory concern, various proposals were made. Based on those variations trie are also named as “compact trie” and “compressed trie”. While a consistent nomenclature is rare, a most common version of a compact trie is formed by grouping all edges when nodes have single edge. Using this concept, the above (Fig-I) trie with keys “dad”, “dab”, and ”cab” can take below form.

``````         [root]
...// | \\...
|  \
cab  da
|    \
[ ]   [*]                Fig-II
./|\\...
|  \
b   d
|    \
[]    []
``````

Note that each of ‘c’, ‘a’, and ‘b’ is sole edge for its corresponding parent node and therefore, they are conglomerated into a single edge “cab”. Similarly, ‘d’ and a’ are merged into single edge labelled as “da”.

Prelude to PATRICIA Tree/Trie:
It would be interesting to notice that even strings as keys can be represented using binary-alphabets. If we assume ASCII encoding, then a key “dad” can be written in binary form by writing the binary representation of each character in sequence, say as “011001000110000101100100” by writing binary forms of ‘d’, ‘a’, and ‘d’ sequentially. Using this concept, a trie (with Radix Two) can be formed. Below we depict this concept using a simplified assumption that the letters ‘a’,’b’,’c’, and’d’ are from a smaller alphabet instead of ASCII.

Note for Fig-III: As mentioned, to make the depiction easy, let’s assume an alphabet with only 4 letters {a,b,c,d} and their corresponding binary representations are “00”, “01”, “10” and “11” respectively. With this, our string keys “dad”, “dab”, and ”cab” become “110011”, “110001”, and “100001” respectively. The trie for this will be as shown below in Fig-III (bits are read from left to right just like strings are read from left to right).

``````          [root]
\1
\
[*]
0/ \1
/   \
[*]   [*]
0/     /
/     /0
[*]    [*]
0/      /
/      /0
[*]    [*]
0/     0/ \1                Fig-III
/      /   \
[*]   [*]   [*]
\1     \1    \1
\      \     \
[]     []    []