问题标签 [radix-tree]

如果每个单词与下一个单词至少有 2 个相同的字母，则字符串被命名为2-consistent 。

例如

“Atom another era” [ atomhas aand tin common withanother和 anotherhas eand ain common with era（答案不是唯一的）。

首先，我需要一个数据结构，它需要 2 个单词并在恒定时间内回答问题 "Do these words have at least 2 letters in common?"

现在，给定一串n单词，我需要找到最长的 2 一致子串。

我不知道要使用什么数据结构。我想radix tree或prefix tree，但我找不到答案。你能帮助我吗？

我已经能够在 JavaScript 中编写一个 Radix 树示例（未优化，所以不要判断）

到目前为止，我已经能够Add,Transverse和Find节点。

我在编写一个可以retrieve所有节点的函数时遇到问题，这是我需要帮助的地方。提前谢谢你

下面是 Python 中的代码片段，它将 IP 前缀存储在基数树中，然后如果 IP 属于前缀，则将 IP 和 ASN 关联到字典中。

我想找出特定前缀的所有不同 ASN。更多详情如下：

例如：val在多次迭代中具有来自 protobuf 的以下值：

当我打印出seen_list：

显然val在seen_list；但是，if val not in seen_list:总是正确的并且val被附加了seen_list很多次。我不明白为什么条件总是返回真。是因为存储的对象的类型seen_list吗？

我正在尝试使用基数树来维护驱动程序的一个内部数据。那么摧毁整棵树的正确方法是什么？

一种想法是使用以下提到的方法遍历树：1

对于每个节点，释放项目并从树中删除其键。

另一个问题是，radix_tree_for_each_slot()在循环中删除项目是否安全？删除会触发内部收缩并导致迭代失败吗？

我必须使用尝试制作字典，字母表中的字母数将从 26 增加到 120，因此叶节点的数量将成倍增加。我可以使用哪些优化来使我的查找、插入和删除时间不会成倍增加？

编辑 使问题更清楚，抱歉缺少细节我正在使用像基数树这样的多路特里树并对其进行一些修改。我的问题是，如果我知道单词大小（肯定）会从 26 增加到 120，它会增加树的深度。是否可以通过将密钥增加到 64 位以上来减少深度的增加（寄存器最多可以达到 64 位）？

据我了解（也来自这里）这些 DS 的内存复杂性可以像 Trie > Radix > Patricia 一样排序。但是时间复杂度呢？我认为它们几乎相同。

如果要提到我的问题，我想从预先构建的字典中做很多前缀搜索查询。记忆对我来说不是一个大问题。我想用最快的DS。

HAT-trie 最适合我，但实现起来太复杂了。我应该使用三元搜索树而不是上面提到的任何 DS 吗？

非常感谢！

我一直在尝试对我为使用 Golang 练习而编写的 Radix Tree 实现进行基准测试。

但是我在“我应该如何对其进行基准测试？”上遇到了一个问题。在下面的代码中显示了两种情况，或者说我想对 LookUp 函数进行基准测试的不同方式。

• 案例1：使用树上存在的一个字节片，这意味着它将通过所有子节点等成功查找......

• 案例 2：使用 func 从树中的现有数据生成随机切片，这意味着它也将成功查找...

我知道时间花费将取决于树的深度......我认为案例 2 是否接近现实世界的实现？

问题：哪种情况对基准测试更有效或更有用？

基准：

结果案例一：

结果案例2：

不匹配时的结果：

虽然很难找到“基数树”的一致定义，但大多数公认的基数树定义表明它是一个压缩的前缀树。我正在努力理解的是在这种情况下“基数”一词的意义。为什么压缩前缀树如此命名（即基数树）而非压缩前缀树不称为基数树？

我知道在 trie 中搜索给定前缀的时间为 O(M)，其中 M 是插入到 trie 中的任何单词的最大长度。

但是检索所有以特定前缀开头的元素的时间复杂度是多少？

我想到了一个可能的答案：

O(M+n) 其中 n 是以前缀开头的单词数。想法：搜索前缀在 O(M) 中。然后我有一个包含所有以给定前缀开头的单词的 subtrie，我只需要遍历它。问题（可能）：前缀树中的节点多于单词。但也许有某种形式的有效存储，这样我就不必看它们了？

我一直在阅读“自适应基数树：主内存数据库的 ARTful 索引”的研究论文，我询问了如何将字符串与节点的键匹配。例如：如果我有一个词：Iota，它是我表中一个元组的主键（标识符）。而且我必须从从 A 开始的值中搜索它，例如 Alpha 到 Zeta。为简单起见，请仅考虑 10 个值：Alpha、Beta、Delta、Gamma、Kappa、Iota、Phi、Psi、Rho、Zeta。你会怎么做呢？

参考研究论文：https ://db.in.tum.de/~leis/papers/ART.pdf