Significance of the term “Radix” in Radix Tree

问题:

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?

回答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!