江苏龙网

  1. 首页 > 生活 > >

trie树这个数据结构的优点是啥，中文名称是啥 提高点难度：他的缺点是啥，效率用big O表示是多高( 三 )





■网友
前缀树。 当字符串数量多的时候，比二叉树和哈希表更省空间。 可以做前缀比较，重要功能之一是用来做输入提示。我感觉确定之一是只能支持字符串。 不能支持数字，尤其是floating point.复杂度来说， insert/delete/find都是o(m) m是key的长度。
■网友
优点是速度快，Trie树的查询复杂度在最差情况下是 O(length(input))，Hash 只能做到在平均情况下 O(length(input))缺点是内存消耗太大。但是，如果使用自动机，就可以在保持Trie树的功能与性能的同时，大大降低内存用量（十几倍，甚至几十倍，几百倍），但是因为这样的自动机实现太困难，工业上的应用很少。不过，现在已经有成熟的实现了：把自动机用作 Key-Value 存储更进一步，使用自动机还可以做多正则匹配：规则引擎建库工具
■网友
前缀树和字典树两个名字楼上都讲了，我来补点引用吧。Trie在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。从Trie树（字典树）谈到后缀树（10.28修订）Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。它有3个基本性质：
根节点不包含字符，除根节点外每一个节点都只包含一个字符。从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。每个节点的所有子节点包含的字符都不相同。
■网友
优点是适合大量重复前缀，缺点是不重复的情况下意义不大，对团队维护不利，需要所有人掌握设计思路，增删查改都要实现，如果你在网站工作里真用了，搞不好是搬起石头砸自己的脚！因为除了性能以外还有业务逻辑和人员分工，数据来源去向等问题。
对于象棋棋谱这种大量重复的数据结构，追求极致速度，最小空间，看起来可以用Trie树，但是有更牛叉的！搜索一下Zobrist哈希，开局库，你会有惊喜！
【trie树这个数据结构的优点是啥，中文名称是啥 提高点难度：他的缺点是啥，效率用big O表示是多高】 所以，Trie树要懂，但真要追求极致，还有更厉害的，他的应用场景还是比较尴尬，换句话来说：无卵用，但是你要懂了，才有资格说这句话

■网友
还有一个名字是字典树，看名字就知道可以用来像字典一样查找单词了～


推荐阅读


上一篇：怎样看待华米（智器）融资3500万美金，估值3亿美元

下一篇：dx11代码有哪些调试的方法