基数树中术语"Radix"的意义

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

维基百科可以回答这个问题，https://en.wikipedia.org/wiki/Radix:

在数学数制中，基数或底数是数唯一的数字，包括0，用于表示a中的数字位置数字系统。例如，对于十进制(今天使用的最常用的系统)的基数是10，因为它使用从0到9的十位数字

和树https://en.wikipedia.org/wiki/Radix_tree:

是一个数据结构，表示一个空间优化的trie，其中每个作为唯一子节点的节点与其父节点合并。结果是每个内部节点的子节点数至少是基数树的基数r，其中r是正整数，是x的幂2, x≥1

最后查字典:

1.基数(名词)

一个原始词，由它衍生出其他词

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

编辑-细化

每个内部节点的子节点数至少为基数r

让我们考虑"aba,abnormal,acne和abyss"这几个词。在常规的前缀树(或trie)中，每条弧向单词添加一个字母，所以我们有:

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

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

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

现在我们有一个内部节点(在b后面)，有3个子节点!基数是2的正幂，所以这里是2。为什么是2而不是3?首先注意根结点有两个子结点。另外，假设我们想添加一个单词。选择:

相关内容