江苏龙网

  1. 首页 > 生活 > >

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

直接来介绍一下 Trie 树吧。
Trie树Trie这个名字取自“retrieval”，检索，因为Trie可以只用一个前缀便可以在一部字典中找到想要的单词。 虽然发音与「Tree」一致，但为了将这种 字典树 与 普通二叉树 以示区别，程序员小吴一般读「Trie」尾部会重读一声，可以理解为读「TreeE」。Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
此外 Trie 树也称前缀树（因为某节点的后代存在共同的前缀，比如pan是panda的前缀）。
它的key都为字符串，能做到高效查询和插入，时间复杂度为O(k)，k为字符串长度，缺点是如果大量字符串没有共同前缀时很耗内存。
它的核心思想就是通过最大限度地减少无谓的字符串比较，使得查询高效率，即「用空间换时间」，再利用共同前缀来提高查询效率。
Trie树的特点假设有 5 个字符串，它们分别是：code，cook，five，file，fat。现在需要在里面多次查找某个字符串是否存在。如果每次查找，都是拿要查找的字符串跟这 5 个字符串依次进行字符串匹配，那效率就比较低，有没有更高效的方法呢？
如果将这 5 个字符串组织成下图的结构，从肉眼上扫描过去感官上是不是比查找起来会更加迅速。

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


通过上图，可以发现 Trie树 的三个特点：
根节点不包含字符，除根节点外每一个节点都只包含一个字符从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串每个节点的所有子节点包含的字符都不相同通过动画理解 Trie 树构造的过程。在构造过程中的每一步，都相当于往 Trie 树中插入一个字符串。当所有字符串都插入完成之后，Trie 树就构造好了。
trie树这个数据结构的优点是啥，中文名称是啥 提高点难度：他的缺点是啥，效率用big O表示是多高



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


Trie树的插入操作很简单，其实就是将单词的每个字母逐一插入 Trie树。插入前先看字母对应的节点是否存在，存在则共享该节点，不存在则创建对应的节点。比如要插入新单词cook，就有下面几步：
插入第一个字母 c，发现 root 节点下方存在子节点 c，则共享节点 c插入第二个字母 o，发现 c 节点下方存在子节点 o，则共享节点 o插入第三个字母 o，发现 o 节点下方不存在子节点 o，则创建子节点 o插入第三个字母 k，发现 o 节点下方不存在子节点 k，则创建子节点 k至此，单词 cook 中所有字母已被插入 Trie树 中，然后设置节点 k 中的标志位，标记路径 root-\u0026gt;c-\u0026gt;o-\u0026gt;o-\u0026gt;k这条路径上所有节点的字符可以组成一个单词cook Trie树的查询操作 在 Trie 树中查找一个字符串的时候，比如查找字符串 code，可以将要查找的字符串分割成单个的字符 c，o，d，e，然后从 Trie 树的根节点开始匹配。如图所示，绿色的路径就是在 Trie 树中匹配的路径。trie树这个数据结构的优点是啥，中文名称是啥 提高点难度：他的缺点是啥，效率用big O表示是多高

如果要查找的是字符串cod(鳕鱼)呢？还是可以用上面同样的方法，从根节点开始，沿着某条路径来匹配，如图所示，绿色的路径，是字符串cod匹配的路径。但是，路径的最后一个节点「d」并不是橙色的，并不是单词标志位，所以cod字符串不存在。也就是说，cod是某个字符串的前缀子串，但并不能完全匹配任何字符串。
trie树这个数据结构的优点是啥，中文名称是啥 提高点难度：他的缺点是啥，效率用big O表示是多高


推荐阅读


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

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