Radix tree
In trie tree, we have seen that each edge contains a single letter or single part of a key. Radix trees are like a compressed version of trie trees, where the edges can contain more than a single letter, even an entire word (if we are using them for words/letters).
This is very effective, reducing the amount of memory and space the tree needs. Let's see an example:
Trie tree (left) and radix tree (right) for the same input
In the preceding figure, you can view the difference between a trie tree and a radix tree for the same input data, PLAN, PLAY, POLL, and POST. Note the following:
- The radix version of the trie uses fewer nodes; one of the purposes of the radix trees is to reduce the amount of memory used. This is because each key has more information (each edge), so we need fewer edges.
- We can perform this compression of single letters to partial words in edges when a node has a single child. Note the trie tree edges [L ->A], [L -> L], and [S -> T...
