data-structures - Radix Tree中“Radix”一词的意义

Question

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

score 2 · Accepted Answer

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

在数学数字系统中，基数或基数是唯一数字的数量，包括零，用于表示位置数字系统中的数字。例如，对于十进制系统（当今最常用的系统），基数是十，因为它使用从 0 到 9 的十位数字。

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

最后查字典：

1.radix（名词）

一个原始词，其他词从中产生。

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

编辑 - 阐述

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

让我们考虑一下“aba、abnormal、acne 和 abysmal”这几个词。在常规前缀树（或 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？那么首先注意根有2个孩子。另外，假设我们要添加一个词。选项：

1 回答 1