I am learning about radix trees (aka compressed tries) and Patricia tries, but I am finding conflicting information on whether or not they are actually the same. A radix tree can be obtained from a normal (uncompressed) trie by merging nodes with their parents when the nodes are the only child. This also holds for Patricia tries. In what ways are the two data structures different?
For example, NIST lists the two as the same:
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 radix trees. 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.
I don't really understand this. Is the difference only in the way comparisons are made when doing look-ups? How can each node be a "two-way branch"? Shouldn't there 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?