Significance of the term "Radix" in Radix Tree

Question

While it is hard to find an unanimous definition of "Radix Tree", most accepted definitions of Radix Tree indicate that it is a compacted Prefix Tree. What I'm struggling to understand is the significance of the term "radix" in this case. Why compacted prefix trees are so named (i.e. Radix Tree) and non-compacted ones are not called Radix Tree?

Prouty

There isn't a good answer to that I guess. I mean a trie has just as much "radix" in it as a radix tree. However someone used this term and it stayed this way. What is more important is that radix tree is compressed version of a trie and that is why some people use the term compressed prefix tree or compressed trie. In addition I use the term PATRICIA to call the same data structure. However there are some debates on that and according to wikipedia PATRICIA is a special type of radix tree used to store binary strings. – Iridissa

I've eventually found an answer and posted my understanding as a response to another question thread #14708634 – Prouty

Answer 1

Wikipedia can answer this, https://en.wikipedia.org/wiki/Radix:

In mathematical numeral systems, the radix or base is the number of unique digits, including zero, used to represent numbers in a positional numeral system. For example, for the decimal system (the most common system in use today) the radix is ten, because it uses the ten digits from 0 through 9.

and the tree https://en.wikipedia.org/wiki/Radix_tree:

a data structure that represents a space-optimized trie in which each node that is the only child is merged with its parent. The result is that the number of children of every internal node is at least the radix r of the radix tree, where r is a positive integer and a power x of 2, having x ≥ 1

Finally check a dictionary:

1.radix(Noun)

A primitive word, from which other words spring.

The radix in the radix tree determines the balance between the amount of children (or depth) of the tree and the 'sparseness', or how many suffixes are unique.

EDIT - elaboration

the number of children of every internal node is at least the radix r

Let's consider the words "aba,abnormal,acne, and abysmal". In a regular prefix tree (or trie), every arc adds a single letter to the word, so we have:

-a-b-a-
   n-o-r-m-a-l-
   y-s-m-a-l-
  -c-n-e-

My drawing is a bit misleading - in tries the letters usually sit on arcs, so '-' is a node and the letters are edges. Note many internal nodes have one child! Now the compact (and obvious) form:

-a-b  -a-
       normal-
       ysmal-
   cne-

Well now we have an inner node (behind b) with 3 children! The radix is a positive power of 2, so 2 in this case. Why 2 and not say 3? Well first note the root has 2 children. In addition, suppose we want to add a word. Options:

• shares the b prefix - well, 4 is greater than 2.
• shares an edge of a child of b - say 'abnormally'. Well The way insertion works the shared part will split and we'll have:

Relevant branch:

-normal-ly-
       -

normal is an inner node now, but has 2 children (one a leaf). - another case would be deleting acne for example. But now the compactness property says The node after b must be merged back, since it's the only child, so the tree becomes

tree:

-ab-a
   -normal-ly-
          -
   -ysmal

so, we still maintain children>2.

Hope this clarifies!

Meuse

@ kabanus - I couldn't understand "every internal node is at least the radix r". Would you pls elaborate on what it means; and why it is not applicable for non-compacted Trie! – Prouty

@ kabanus - Thanks a lot for ur patience; even though I started to sound impossible. Btw, are you saying, for a compacted Trie, for all internal nodes n, if min ( # of children of n) >= 2^r then r is the radix of the compacted trie ? May be we can first have a definition of radix r of such a Trie! – Prouty

I just found another good anwer: #21205480 - wish I saw this sooner. As you see the minimal amount of bits required to maintain all possible prefixes in inner nodes is the radix. – Meuse

@ kabanus - I had my doubt cleared and put my understanding in another post #14708634 . Btw, thanks for the link you shared; the reference book is great. – Prouty