Skip to main content
1 of 4
w128
  • 563
  • 1
  • 4
  • 9

What's the difference between a radix tree and a Patricia trie?

I'm learning about radix trees (aka compressed tries) and Patricia tries, but am finding conflicting information on whether or not these two are actually the same. A radix tree can be obtained from a normal (uncompressed) trie by merging each node that is the only child with its parent. Apparently, the same holds for a Patricia trie. But in what ways are the two structures different?

For example, NIST lists the two as the same:

Patricia tree

(data structure)

Definition: A compact representation of a trie in which any node that is an only child is merged with its parent.

Also known as radix tree.

Many sources on the web claim the same. However, apparently Patricia tries are a special case of a radix tree. Wikipedia entry says:

PATRICIA tries are radix tries with radix equals 2, which means that each bit of the key is compared individually and each node is a two-way (i.e., left versus right) branch.

but I don't really understand this. Is the difference only in the way comparisons are made when doing a lookup? How can each node be a "two-way branch" - shouldn't there still be at most ALPHABET_SIZE possible branches for a given node?

Can someone clarify this? For practical purposes, are radix tries typically implemented as Patricia tries (and hence often considered the same), or can no such generalizations be made?

w128
  • 563
  • 1
  • 4
  • 9