问题描述
我正在尝试了解。
我了解查找，插入和删除如何与之配合使用。但是我不明白基数在一个基数树中是什么意思。
I understand how lookup, insert and delete works with it. But I could not understand what does radix mean in a radix tree.
这里的基数是什么？
推荐答案
如@ta在，小数是你的特技的基础。在这种情况下，我们的意思是数字库，我们将考虑存储二进制数据。基数R = 2 ^ x，其中x> = 1。
As already mentioned by @ta in the Wikipedia etymology link, the 'radix', is the the base of your trie. In this case we mean the numeric base, and we'll consider storing binary data. Radix R = 2 ^ x, where x >= 1.
以二进制（2-ary）为例。基数为2，因此在每个节点，您可以比较一个位。这两个孩子将处理所有可能的结果：
Take the example of a binary (2-ary) trie. The radix is 2, so at each node you can compare one bit. The two children will handle all of the possible outcomes:
- 该位为0
- 是1
下一个级别的复杂性将是一个4-ary trie。正如@Garrett上面提到的那样，基数必须是2的幂，以便它总能处理我们使用它的二进制数据的所有可能的排序结果。一个4-ary trie可以比较两个二进制位与四个可能的结果：
The next level of complexity would be a 4-ary trie. As @Garrett mentioned above, the radix must be a power of two so that it can always handle all possible sorting outcomes of the binary data we're using it for. A 4-ary trie can compare two binary bits with the four possible outcomes:
- 00
- 01
- 10
- 10
- 00
- 01
- 10
- 10
选项各自导致不同的子节点。
These four options each lead to a different child node.
现在，回答您关于英文字母表基数的问题。你要编码一个字母到一个字母（26个字母），所以需要一个至少为2 ^ 5 = 32的基数。这是最小的基数，它将让你在每个字母之间切换并符合 ' 规则。 2 ^ 4 = 16不会处理所有的字母。
Now, in answer to your question about the radix for the English alphabet. You want to encode letters from a to z (26 letters) so will need to have a radix of at least 2^5 = 32. This is the smallest radix that will let you switch between every letter and conform to the 'powers of two' rule. 2^4 = 16 wouldn't handle all of the letters.
作为一个例子，我们假设以下编码：
As an example, let's imagine the following encoding:
- 00000表示' a'，
- 00001表示'b'，
- ...等
- 11001表示'z '，
- 11010至11111未使用（还）
- 00000 represents 'a',
- 00001 represents 'b',
- ... etc
- 11001 represents 'z',
- 11010 to 11111 are not in use (yet)
我们现在可以做在树中的每个节点上比较五位，所以每个节点现在可以在任何罗马字母表之间切换。如果你想要一个处理大写字母的特技，那么你将需要一个更大的基数。 2 ^ 6的基数会给你足够的这样做，但它是以更多的浪费空间（未使用的分支）为代价的。
we can now do a comparison of five bits at every node in the tree, so every node can now switch between any Roman-alphabet letter. If you want a trie that will handle upper case letters then you will require a larger radix. A radix of 2^6 will give you enough to do this, but it comes at the cost of more wasted space (unused branches) in the trie.
进一步阅读：。第三版一般都很好，但对于多路尝试来说并不算太多。
Further reading: Sedgewick, Ch 15.4, on Multiway Tries. The 3rd edition of Algorithms by Cormen is generally excellent but doesn't do much for multiway tries.
这篇关于基数在基数树中是什么意思？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！