尝试和树的区别? [英] Difference between Tries and Trees?

问题描述

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

I remotely remember that tries don't store the whole data per node, only the suffix to the parent node.

树存储整个数据的地方，但只根据前缀组织自己.

Where trees do store the whole data, but only organize themselves based on a prefix.

所以尝试变得更小，例如可以很好地压缩字典.

So tries get smaller, which allows for example to compress dictionaries very well.

这真的是唯一的区别吗?

Is that really the only difference?

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

From actual applications I remember that tries are faster in range queries. There are even special solr/lucene trie fields to speed up range queries. But how is that so?

尝试和树的实际区别是什么，优缺点是什么?

What is the actual difference and what are the advantages and disadvantages of tries and trees?

推荐答案

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

A tree is a general structure of recursive nodes. There are many types of trees. Popular ones are binary tree and balanced tree. A Trie is a kind of tree, known by many names including prefix tree, digital search tree, and retrieval tree (hence the name 'trie').

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

Each kind of tree has a different purpose, structure and behaviour. For example, a binary tree stores a collection of comparable items (eg numbers). It can therefore be used to store a set of numbers, or to index other data that can be represented by numbers (eg objects that can be hashed). Its structure is sorted so it can be searched quickly to find a single item. Other tree structures, such as a balanced tree, are similar in principle.

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

A trie represents a sequence in its structure. It is very different in that it stores sequences of values rather than individual single values. Each level of recursion says 'what is the value of item I of the input list'. This is different to a binary tree which compares the single searched value to each node.

这篇关于尝试和树的区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！