Meaning of the term “Radix” in the Radix tree

Question

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

Answer 1

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

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

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

a data structure representing a space-optimized trie in which each node, which is the only child, is combined with its parent. As a result, the number of children of each internal node is at least radix r of the base tree, where r is a positive integer and degree x of 2 having x ≥ 1

Finally, check the dictionary:

1.radix (noun)

primitive word, from which other words spring.

The radius in the base tree determines the balance between the number of children (or depth) of the tree and the "sparseness" or number of suffixes unique.

EDIT - development

the number of children of each inner node is at least equal to the radius r

Let's look at the words "aba, abnormal, blackheads and terrible." In a regular prefix tree (or trie), each arc adds one letter to the word, so we have:

-aba- normal- ysmal- -cne- 

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

 -ab -a- normal- ysmal- cne- 

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

• divided by the prefix b - well, 4 is greater than 2.
• separates the edge of child b - say "abnormally." Well, how the insert works, the general part is divided, and we will have:

Corresponding branch:

 -normal-ly- - 

normal is an internal node, but has 2 children (one leaf). - In another case, acne could be removed. But now the compactness property says that the node after b should be merged back, since it is the only child, so the tree becomes

wood:

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

therefore, we still support children> 2.

Hope this clarifies!