tree - 尝试和树之间的区别？

Question

我远程记得尝试不存储每个节点的全部数据，只存储父节点的后缀。

树确实存储了整个数据，但仅根据前缀进行组织。

因此尝试变得更小，例如可以很好地压缩字典。

这真的是唯一的区别吗？

从实际应用程序中，我记得尝试在范围查询中更快。甚至还有特殊的 solr/lucene trie 字段来加速范围查询。但怎么会这样呢？

尝试和树的实际区别是什么以及优缺点是什么？

Answer 1

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

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

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

Answer 2

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

Trie : trie 的每个节点都由多个分支组成。每个分支代表一个可能的键字符。我们需要将每个键的最后一个节点标记为叶子节点。将使用一个 trie 节点字段值来区分该节点是否为叶节点（该值字段还有其他用途）

要了解尝试，请参阅此 topcoder 教程。 https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/

Answer 3

刚刚从这个谈话中得到了一些见解，即使 Linux 内核中使用的 Radix 树与维基百科上的略有不同。

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

Answer 4

尝试的优点：

• 搜索时间仅取决于搜索字符串的长度。

• 搜索未命中只涉及检查几个字符（特别是搜索字符串和存储在树中的语料库之间的最长公共前缀）。

• 在 trie 中没有唯一键的冲突。

• 无需提供散列函数或更改散列函数，因为将更多键添加到树中。

• trie 可以通过键提供条目的字母顺序。

不幸的是，没有完美的数据结构。所以即使尝试也有一些缺点：

• 每当容器太大而无法放入内存时，尝试查找数据的速度可能比哈希表慢。哈希表需要更少的磁盘访问，甚至只需要一次访问，而 trie 需要 O(m) 磁盘读取长度为 m 的字符串。

• 哈希表通常分配在一个大且连续的内存块中，而 trie 节点可以跨越整个堆。所以，前者最好利用局部性原则。

• trie 的理想用例是存储文本字符串。理论上，我们可以将任何值（从数字到对象）字符串化并存储。然而，如果我们要存储浮点数，例如，由于问题，存在一些边缘情况可能会产生长的无意义路径，例如周期数或超越数，或者某些浮点运算的结果，例如 0.1+0.2具有双精度表示。

• 尝试对节点和引用有内存开销。

当您必须经常执行前缀搜索时使用尝试（longestPrefix 或 keysWithPrefix）。当数据存储在慢速支持（如磁盘）或内存位置很重要时，请使用哈希表。