尝试和树木之间的区别？

Question

我远程记住,尝试不存储每个节点的整个数据,只存储父节点的后缀.

树存储整个数据,但只根据前缀组织自己.

因此尝试变得更小,这允许例如非常好地压缩字典.

这真的是唯一的区别吗？

从实际应用程序中我记得尝试在范围查询中更快.甚至还有特殊的solr/lucene trie字段来加速范围查询.但那是怎么回事？

尝试和树木的实际差异是什么,优点和缺点是什么？

Answer 1

树是递归节点的一般结构.有很多种树木.流行的是二叉树和平衡树.一个特里是一种树,有许多名称,包括前缀树,数字搜索树,并检索树(故名"线索")闻名.

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

甲特里结构表示在其结构中的序列.它的不同之处在于它存储的是值序列而不是单个单个值.每个递归级别都表示"输入列表的第I项的值是多少".这与将单个搜索值与每个节点进行比较的二叉树不同.

Answer 2

\n

在树结构中，我们存储整个单词。开销很大。\n如果搜索antic，您将遍历每个单词并比较\n中的所有字符串antic。这占用了太多的时间和内存：

\n

\n

\n

\n

然而，在尝试中，压缩是关键。我们仅存储常见的\n前缀。这将减少冗余。

\n

\n

\n

尝试的优点：

\n

\n

\n

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

  \n
\n

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

  \n
\n

• trie 中的唯一键不会发生冲突。

  \n
\n

• 当更多的键添加到 trie 中时，无需提供哈希函数或更改哈希函数。

  \n
\n

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

  \n
\n

\n

不幸的是，不存在完美的数据结构。因此，即使尝试也有一些缺点：

\n

\n

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

  \n
\n

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

  \n
\n

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

  \n
\n

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

  \n
\n

\n

当您必须频繁执行前缀搜索（\nlongestPrefix 或 keysWithPrefix ）时，请使用 attempts。当数据存储\非慢速支持（如磁盘）或内存局部性很重要时，请使用哈希表。

\n

\n

\n

参考

\n

Answer 3

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

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

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

Answer 4

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

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