基数在基数树中是什么意思？ [英] What does radix mean in a radix tree?

问题描述

我正在尝试了解基数树（或紧凑型前缀树）数据结构。

我了解查找，插入和删除如何与之配合使用。但是我不明白基数在一个基数树中是什么意思。

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.

进一步阅读： Sedgewick，Ch 15.4，Multiway Tries 。第三版 Cormen的算法一般都很好，但对于多路尝试来说并不算太多。

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.

这篇关于基数在基数树中是什么意思？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！