问题标签 [radix-tree]

我正在尝试用 Java 实现一个非常简单的 Trie，它支持 3 个操作。我希望它有一个 insert 方法、一个 has 方法（即 trie 中的某个单词）和一个 toString 方法以字符串形式返回 trie。我相信我的插入工作正常，但 has 和 toString 被证明是困难的。这是我到目前为止所拥有的。

trie 类。

和节点类

因此，基本上，在创建 Trie 时，会创建一个 TrieNode 作为具有 26 个子节点的根。当尝试插入时，会在该根节点上调用 insert，它会在正确的位置递归地创建一个新节点，并继续直到单词完成。我相信该方法工作正常。

我的 has 函数非常糟糕，因为出于某种原因，我必须在括号外加上 return 语句。我不能将它包含在 else 子句中，否则编译器会抱怨。除此之外，我认为该方法应该进行一些调整，但我无法终生解决。

toString 是我试图解决的野兽，但我扔给它的任何东西都不起作用，所以我会保留它，直到我解决问题。如果我有工作，我可能会想办法将它重新格式化为 toString 函数。

int val = word.charAt(0) - 64; 的目的 是因为输入的每个字符串都必须全部大写（我将创建一个字符串格式化函数来确保这一点）所以第一个字母的 int 值 - 64 将是它在数组中的位置。即数组索引0是A，所以A = 64，A - 64 = 0。B = 65，B - 64 = 1，依此类推。

我正在寻找一个基数树实现，我可以将它用于二进制字符串的键，实际上是 UUID，所以必须支持空字节。

它将用于商业产品，因此具有合适的许可证。

我正在尝试决定以下使用哪种数据结构。

假设我可能有 1000 万个键，其中包含指向包含某些数据的唯一对象的指针。

键是 UUID 将它们视为 16 字节二进制数组。UUID 是使用优质随机数生成器生成的。

我一直在考虑以下内容，但想知道每个人在速度和内存消耗方面的优缺点。一些公平的估计，64 位平台上的最佳/最差/平均情况会很好。

我需要能够插入几乎无限的项目。

二叉树哈希表基数树（基于位或2位多路）

我需要的操作是：插入、删除、搜索

我喜欢基数树的想法，但事实证明它是最难实现的，而且我还没有找到可以整合到商业产品中的合适实现。

我正在用 C++ 编写一个程序，该程序需要快速查找和存储 IP 地址（所有 IPv4）。每个 IP 地址都有一个与之关联的数据。如果它已经存在于 trie 中，我打算将 trie 中的 IP 地址数据与新地址数据合并。如果它不存在，我打算将它作为新条目添加到 trie 中。不需要删除 IP 地址。

为了实现这一点，我需要设计一个 Patricia Trie。但是，我无法想象除此之外的设计。我似乎很天真，但我想到的唯一想法是将 IP 地址更改为二进制形式，然后使用 trie。然而，我对如何实现这一点一无所知。

如果您能帮我解决这个问题，我将非常感谢您。请注意，我确实在这里找到了类似的问题。这个问题或更具体的答案超出了我的理解，因为 CPAN 网站中的代码对我来说不够清楚。

另请注意，我的数据是以下格式

10.10.100.1：“汤姆”、“杰克”、“史密斯”

192.168.12.12：“琼斯”、“莉兹”

12.124.2.1：“吉米”，“乔治”

10.10.100.1：“迈克”、“哈利”、“詹妮弗”

trie和radix trie数据结构是否相同？

如果它们不一样，那么基数特里（AKA Patricia trie）的含义是什么？

Is there a document that will help me understand how ipv4 addresses are inserted into the patricia/radix trees? I am confused around calculating mask length and if the mask length is for the complete address or one octet in the address.

Any explaination would be appreciated.

我一直关心基数树的空间使用情况，但我没有找到任何有用的讨论。

现在假设我们有一个与 linux radix-tree.c 相同的基数树实现，它采用一个整数并使用每 6 位来索引树中的下一个位置。我很容易想到基数树的空间使用量远远超过二叉搜索树的情况。如果我错了，请纠正我：

用例：(0,1,1,1,1), (1,1,1,1,1), (2,1,1,1,1), ... (63,1,1,1 ,1)。

这里为了方便起见，我使用 (a,b,c,d,e) 来表示一个 30 位整数键，每个元素代表一个 6 位值。a 是 MSB，e 是 LSB。

基数树：

对于这个用例，基数树的高度为 5，每个键将占用 4 个单独的节点，因为它们位于根的不同子树上。所以会有 ((5-1) * 64 + 1) = 257 个节点。

每个节点包含 2^6 = 64 个指针，因此它将使用 257 * 64 * 4Byte = 65KB

二叉搜索树

我们只关心有多少键。在这种情况下，它有 64 个键。

假设每个 BST 节点每个节点使用 3 个指针，它将使用 64 * 3 * 4Byte = 768 字节。

比较

看起来基数树的空间效率很低。给定相同数量的节点，它使用的空间是二叉搜索树的 100 倍！我不明白为什么即使在linux内核中也使用它。

我错过了什么吗？谢谢。

我正在浏览一篇关于linux内核基数树实现的文章，文章链接如下：

http://lwn.net/Articles/175432/

在这篇文章中提到 radix_tree_preload 分配了足够的内存，以便后续插入树不会失败。尽管它基于每个 CPU 分配结构，因此该函数在禁用抢占的情况下返回。调用 radix_tree_preload_end 以启用抢占是调用者的责任。

我的问题是：

1) 为什么 radix_tree_preload 在每个 CPU 基础上分配结构？

2) 用户应该何时调用 radix_tree_preload_end？是在 radix_tree_insert 之后吗？

3）它不会影响性能，因为基数树用于页面缓存操作，因此任何插入都会导致抢占被禁用？如果我的理解有误，请纠正我。

当我查找 Tries 和基数树时，例如 http://en.wikipedia.org/wiki/Compact_prefix_tree和 http://en.wikipedia.org/wiki/Trie，我没有看到关于字典排序的具体内容一个节点的子节点。

因此，例如，在这个trie 中（页面上唯一的数字），根的孩子可以更好地从左到右排序为“A”、“i”、“t”。

尝试/基数树用于检索 - 不用于频繁更新。因此，这种排序不会花费太多，尤其是在稀有树更新上，算法上简单/直接，并且在值查找/检索期间增加了一些速度。

我错过了什么？

我正在寻找关于/反对这个的论点。

我目前正试图了解 Trie 的变化，并想知道是否有人能够澄清几点。（我对这个问题的答案感到很困惑Tries vs ternary search trees for autocomplete?，尤其是在第一段中）。

根据我的阅读，以下内容是否正确？假设我们在数据结构中存储了 n 个元素，L 是我们要搜索的字符串的长度：

• Trie 将其键存储在叶节点上，如果我们的搜索结果为正，则意味着它将执行 O(L) 比较。然而，对于未命中的情况，平均性能为 O(log2(n))。

• 类似地，基数树（R = 2^r）将键存储在叶节点，并将执行 O(L) 比较以获得正命中。然而，未命中会更快，并且平均发生在 O(logR(n)) 中。

• 三元搜索 Trie 本质上是一个带有操作 <、>、= 的 BST，并且每个节点中都存储了一个字符。我们不比较节点处的整个密钥（与 BST 一样），而是只比较该节点处密钥的一个字符。总的来说，假设我们的字母大小是 A，那么如果有命中，我们必须（最多）执行 O(L*A) = O(L) 比较。如果没有命中，我们平均有 O(log3(n))。

关于基数树，如果我们的字母表是 {0,1} 并且我们设置 R = 4，对于二进制字符串 0101，我们只需要两次比较，对吧？因此，如果我们的字母表的大小是 A，我们实际上只会执行 L * (A / R) 比较？如果是这样，那么我猜这只是 O(L)，但我很好奇这是否是正确的推理。

感谢大家提供的任何帮助！