基数中“基数”一词的含义

Question

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

Answer 1

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

在数学标记系统中，基数或碱是 独特位，包括零，用于在 定位数系来表示数字的数量。例如，对于十进制系统（目前使用的 最常见的系统）基数为10，因为它是通过9

使用从0 十位数和树https://en.wikipedia.org/wiki/Radix_tree：

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

最后检查字典：

1.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个孩子！基数是2的正幂，所以在这种情况下是2。为什么2而不是3？那么先注意根有2个孩子。另外，假设我们想添加一个词。选项：

• 股b前缀 - 好了，4比2
• 股b子的边缘更大 - 说“不正常”。那么插入的方式工作共用部分会分裂，我们将有：

相关分支：

-normal-ly- 
     - 

正常现在是一个内部节点，但有2个孩子（一个叶）。 - 另一种情况是例如删除痤疮。但是，现在的紧性说b后的节点必须合并回去，因为它是唯一的孩子，所以树变得

树：

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

因此，我们仍然维持孩子> 2。

希望澄清！