Tries和Trees有什么区别？

Question

我模糊地记得tries不会在每个节点上存储整个数据，只会存储到父节点的后缀。

而树是会存储整个数据的，但只基于前缀来组织节点。

所以，tries可以变得更小，这允许例如对字典进行很好的压缩。

这真的是唯一的区别吗？

从实际应用中，我记得tries在范围查询方面更快。甚至有专门针对范围查询加速的solr/lucene trie字段。但是这是为什么呢？

tries和树的实际区别及其优缺点是什么？

- The Surrican

Answer 1

树是一种递归节点的通用结构。有许多类型的树，其中流行的包括二叉树和平衡树。Trie是一种树，有许多名称，包括前缀树、数字搜索树和检索树（因此得名'trie'）。

每种类型的树都有不同的目的、结构和行为。例如，二叉树存储可比较项的集合（例如数字）。因此，它可以用于存储一组数字，或者用于索引可以用数字表示的其他数据（例如可以哈希的对象）。它的结构是排序的，因此可以快速搜索以查找单个项。其他树结构，如平衡树，原理上类似。

Trie在其结构中表示一个序列。它非常不同，因为它存储值序列而不是单个值。每个递归级别都说“输入列表的第I项的值是什么”。这与二叉树将单个搜索值与每个节点进行比较不同。

- Joe

---

Trie 不是有点过时了吗？除了存储空间以外，二叉树在所有方面都比 Trie 更胜一筹，不是吗？ - Pacerier

每种数据结构都有其适用的场景。那么，如何查找所有具有相同前缀的字符串呢？O(n) 访问时间？ - Joe

树难道也能做到吗？让我们有10亿个条目，找出20个前缀。Trie只需要20步就可以完成。而树则需要lg 1B/lg 2 = 30 步才能完成。现在，对于相同的10亿个条目，我们要找出40个前缀。树仍然需要30步才能完成，但是Trie需要40步。当要找100个前缀时，Trie需要100步，而树仍然只需要30步。 - Pacerier

等等，对我来说Trie似乎更好。因为在trie中查找是根据字符串长度为O(m)，而在树中查找是根据节点数和字符串长度为O(m * log n)，因为比较两个字符串最坏情况下需要花费O(m)的时间，而你需要进行最坏情况下O(log n)次比较。而Trie只需进行一次O(1)字符比较。 - semicolon

@Pacerier，Trie在基本上所有操作中都具有更好的渐近性能，因为在Trie中比较是O(1)的，因为您正在比较值的常量大小子部分，而在树中它们是O(m)。 - semicolon

@分号 实际上，单词的长度（至少在英语中）是有限的，不会根据字典的大小而改变，所以在实际情况下 O(m) = O(1)。 - undefined

Answer 2

在树结构中，我们存储整个单词。这样会有很多的开销。如果你搜索 "antic"，你需要遍历每个单词并比较其中所有的字符串。这会消耗太多时间和内存。

然而，在Trie中，压缩是关键。我们只存储常见的前缀，这将减少冗余。

尝试的优点：

搜索时间仅取决于所搜索字符串的长度。 搜索失败只涉及检查几个字符（特别是搜索字符串与存储在树中的语料库之间的最长公共前缀）。 在trie中没有唯一键的冲突。 不需要提供哈希函数或随着更多键被添加到trie而更改哈希函数。 Trie可以按键提供条目的字母顺序。 不幸的是，没有完美的数据结构。因此，即使tries也有一些缺点： 当容器太大无法适应内存时，Tries在查找数据方面可能比哈希表慢。哈希表需要较少的磁盘访问，甚至只需一个访问，而trie对于长度为m的字符串需要O（m）个磁盘读取。 哈希表通常分配在单个大而连续的内存块中，而trie节点可以跨越整个堆。因此，前者将更好地利用局部性原理。 Trie的理想用例是存储文本字符串。我们可以理论上地将任何值，从数字到对象，串行化并存储它。然而，如果我们要存储浮点数，例如，存在一些边缘情况会产生长而无意义的路径，例如周期性或超越数，或某些浮点操作的结果，例如0.1+0.2，由于双精度表示的问题。 Tries具有节点和引用的内存开销。 当您需要频繁执行前缀搜索（longestPrefix或keysWithPrefix）时，请使用tries。在数据存储在慢速支持（如磁盘）上或内存局部性很重要时，请使用哈希表。

参考资料

- Yilmaz

Answer 3

二叉树或bst通常用于存储数字值。在bst中，插入、删除和搜索的时间复杂度为O(log(n))。二叉树中的每个节点最多有两个子节点。

Trie：trie的每个节点都包含多个分支。每个分支表示一个可能的键字符。我们需要将每个键的最后一个节点标记为叶节点。trie节点字段值将用于区分节点作为叶子节点（还有其他用途）。

要了解更多关于tries的内容，请参考这篇topcoder教程。 https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/

- Harsh Gupta

Answer 4

我刚从这个演讲中获得了一些见解，即使在Linux内核中使用的基数树与维基百科上的基数树略有不同。

树只存储键，不存储与键相关联的值。

- firo