data-structures - 基数树中术语 "Radix"的意义

Question

虽然很难找到“基数树”的一致定义，但大多数接受的基数树定义表明它是一个压缩的前缀树。在这种情况下，我很难理解术语“基数”的重要性。为什么压缩前缀树如此命名(即基数树)而非压缩前缀树不称为基数树？

Answer 1

维基百科可以回答这个问题，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.

和树 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

最后查字典:

1.radix(Noun)

A primitive word, from which other words spring.

基数树中的基数决定了树的子节点数量(或深度)与“稀疏度”之间的平衡，或者有多少后缀是唯一的。

编辑 - 详细说明

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

让我们考虑“aba、异常、痤疮和深渊”这两个词。在常规前缀树(或特里树)中，每个弧向单词添加一个字母，因此我们有:

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

我的画有点误导 - 在尝试中，字母通常位于弧上，所以“-”是一个节点，字母是边。注意很多 内部节点有一个子节点 !现在紧凑(和明显)的形式:

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

那么现在我们有一个带有 3 个 child 的内部节点(在 b 后面)!基数是 2 的正幂，因此在本例中为 2。为什么是 2 而不是说 3？首先要注意根有2个 child 。另外，假设我们要添加一个单词。选项:

分享 b前缀 - 好吧，4 大于 2。

共享 b 的子节点的边- 说'异常'。那么插入工作的方式共享部分将 split ，我们将有:

相关分行:

-normal-ly-
       -

normal 现在是一个内部节点，但有 2 个子节点(一个是叶子节点)。
- 例如，另一种情况是删除痤疮。但是现在紧凑性属性表示 b 之后的节点必须合并回来，因为它是唯一的 child ，所以树变成

树:

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

所以，我们仍然保持children>2。

希望这能澄清!