术语“基”的意义在基础树 [英] Significance of the term "Radix" in Radix Tree
问题描述
虽然很难找到Radix Tree的一致定义，但大多数接受的基数树的定义表明它是一个压缩的前缀树。我正在努力理解的是这个术语基数的意义。为什么压缩的前缀树是如此命名的（即基数树），未压缩的前缀树不被称为>
While it is hard to find an unanimous definition of "Radix Tree", most accepted definitions of Radix Tree indicate that it is a compacted Prefix Tree. What I'm struggling to understand is the significance of the term "radix" in this case. Why compacted prefix trees are so named (i.e. Radix Tree) and non-compacted ones are not called Radix Tree?
推荐答案
维基百科可以回答这个问题， https://en.wikipedia.org/wiki/Radix ：
Wikipedia can answer this, https://en.wikipedia.org/wiki/Radix:
在数学系统中，基数或基数是
唯一数字的数量，包括零，使用在
位置数字系统中表示数字。例如，对于十进位系统（今天使用的
最常见的系统），基数为十，因为它使用
从0到9的十位数字。
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 ：
一个数据结构，表示每个
节点的空间优化特里这是唯一的孩子与其父母合并。结果是
，每个内部节点的子代数至少为基数树的
基数r，其中r是正整数，幂x
为2，有x ≥1
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（名词）
1.radix(Noun)
一个原始单词，从其他单词春天。
A primitive word, from which other words spring.
基数树中的基数决定了树的子数（或深度）与稀疏度之间的平衡，或者多少后缀是唯一的。
The radix in the radix tree determines the balance between the amount of children (or depth) of the tree and the 'sparseness', or how many suffixes are unique.
编辑
每个内部节点的子代数至少为基数r
the number of children of every internal node is at least the radix r
让我们考虑aba，异常，痤疮和可怜这个词。在一个常规的前缀树（或trie）中，每个弧都会添加单个字母，所以我们有：
Let's consider the words "aba,abnormal,acne, and abysmal". In a regular prefix tree (or trie), every arc adds a single letter to the word, so we have:
-a-b-a-
n-o-r-m-a-l-
y-s-m-a-l-
-c-n-e-
我的绘图有点误导 - 在尝试字母通常坐在弧上，所以' - '是一个节点，字母是边。注意许多内部节点有一个孩子！现在紧凑（和明显）的形式：
My drawing is a bit misleading - in tries the letters usually sit on arcs, so '-' is a node and the letters are edges. Note many internal nodes have one child! Now the compact (and obvious) form:
-a-b -a-
normal-
ysmal-
cne-
现在我们有一个内部节点（b后面），有3个孩子！基数为2的正幂，因此在这种情况下为2。为什么2而不是说3？首先注意根有2个孩子。另外，假设我们要添加一个单词。选项：
Well now we have an inner node (behind b) with 3 children! The radix is a positive power of 2, so 2 in this case. Why 2 and not say 3? Well first note the root has 2 children. In addition, suppose we want to add a word. Options:
- 共享
b前缀 - 好，4大于2。 - 分享
b的孩子的边缘 - 说异常。好的插入工作方式共享的部分将分裂，我们将有：
- shares the
bprefix - well, 4 is greater than 2. - shares an edge of a child of
b- say 'abnormally'. Well The way insertion works the shared part will split and we'll have:
相关分支：
-normal-ly-
-
正常现在是一个内部节点，但有2个孩子（一个叶子）。
- 另一个例子是删除痤疮。但现在紧凑性属性说， b 之后的节点必须被合并，因为它是唯一的孩子，所以树变为
normal is an inner node now, but has 2 children (one a leaf).
- another case would be deleting acne for example. But now the compactness property says The node after b must be merged back, since it's the only child, so the tree becomes
树：
-ab-a
-normal-ly-
-
-ysmal
所以，我们仍然维护孩子2。
so, we still maintain children>2.
希望澄清！
这篇关于术语“基”的意义在基础树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
