algorithm - What is the difference between trie and radix trie data structures?

Question

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

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

Answer 1

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.