data-structures - 基数树中的基数是什么意思？

Question

我试图理解 the radix tree (or compact prefix tree) data structure .

我了解查找、插入和删除的工作原理。但是我不明白基数在基数树中是什么意思。

这里radix的作用是什么？

Answer 1

正如@ta 在 Wikipedia etymology link 中提到的那样，'radix'，是你的 trie 的基础。在这种情况下，我们指的是数字基数，我们将考虑存储二进制数据。基数 R = 2 ^ x，其中 x >= 1。

以二进制 (2-ary) 树为例。基数是 2，所以在每个节点你可以比较一位。这两个 child 将处理所有可能的结果:

• 该位为0
• 位为1

下一级别的复杂性将是 4 元树。正如@Garrett 上面提到的，基数必须是 2 的幂，这样它才能始终处理我们使用它的二进制数据的所有可能排序结果。 4 元 trie 可以将两个二进制位与四种可能的结果进行比较:

• 00
• 01
• 10
• 10

这四个选项分别指向不同的子节点。

现在，回答您关于英文字母基数的问题。您想要编码从 a 到 z 的字母(26 个字母)，因此基数至少需要 2^5 = 32。这是最小的基数，可以让您在每个字母之间切换并符合“2 的幂” ' 规则。 2^4 = 16 无法处理所有字母。

作为示例，让我们想象以下编码:

• 00000代表'a'，
• 00001代表'b'，
• ...等等
• 11001代表'z'，
• 11010 到 11111 尚未使用(尚未)

我们现在可以对树中每个节点的五位进行比较，因此每个节点现在都可以在任何罗马字母之间切换。如果你想要一个能够处理大写字母的 trie，那么你将需要一个更大的基数。 2^6 的基数足以让您执行此操作，但代价是 trie 中会浪费更多空间(未使用的分支)。

进一步阅读:Sedgewick, Ch 15.4, on Multiway Tries .第三版Algorithms by Cormen通常非常好，但对多路尝试作用不大。