KGh*_*tak 6 tree patricia-trie data-structures radix-tree
虽然很难找到"基数树"的一致定义,但大多数公认的基数树定义表明它是一个压缩的前缀树.我正在努力理解的是在这种情况下术语"基数"的重要性.为什么压缩的前缀树如此命名(即Radix Tree),而非压缩的前缀树不称为Radix Tree？
维基百科可以回答这个问题，https://en.wikipedia.org/wiki/Radix：
\n\n\n\n\n在数学数字系统中，基数或基数是唯一数字的数量（包括零），用于表示位置数字系统中的数字。例如，对于十进制系统（当今最常用的系统），基数为 10，因为它使用从 0 到 9 的十位数字。
\n
和树https://en.wikipedia.org/wiki/Radix_tree：
\n\n\n\n\n表示空间优化 trie 的数据结构，其中作为唯一子节点的每个节点都与其父节点合并。结果\n每个内部节点的子节点数量至少为\n基数树的基数r，其中r是正整数，x\n为2的幂，有x\xe2\x89\xa5 1
\n
最后查一下字典：
\n\n\n\n\n1.radix（名词）
\n\n一个原始词，其他词由此产生。
\n
基数树中的基数决定了树的子级（或深度）数量和“稀疏性”之间的平衡，或者有多少后缀是唯一的。
\n\n编辑-阐述
\n\n\n\n\n每个内部节点的子节点数量至少为基数 r
\n
让我们考虑一下“aba、abnormal、acne 和 abysmal”这几个词。在常规前缀树（或特里树）中，每个弧向单词添加一个字母，因此我们有：
\n\n-a-b-a-\n n-o-r-m-a-l-\n y-s-m-a-l-\n -c-n-e-\n我的绘图有点误导 - 在尝试中，字母通常位于弧上，因此“-”是一个节点，字母是边缘。请注意，许多内部节点都有一个子节点！现在是紧凑（且明显）的形式：
\n\n-a-b -a-\n normal-\n ysmal-\n cne-\n现在我们有一个内部节点（在 b 后面），有 3 个子节点！基数是 2 的正幂，因此在本例中是 2。为什么是2而不是3呢？首先请注意根有 2 个子节点。另外，假设我们要添加一个单词。选项：
\n\nb前缀 - 好吧，4 大于 2。b- 比如说“异常”。好吧，插入的工作方式共享部分将分裂，我们将得到：相关分行：
\n\n-normal-ly-\n -\n正常现在是一个内部节点，但有 2 个子节点（一个是叶子）。\n- 例如，另一种情况是删除痤疮。但现在紧凑性属性说后的节点b必须合并回去，因为它是唯一的子节点，所以树变成
树：
\n\n-ab-a\n -normal-ly-\n -\n -ysmal\n所以，我们仍然保持children>2。
\n\n希望这能澄清！
\n| 归档时间： |
|
| 查看次数： |
460 次 |
| 最近记录： |