图解：数据结构中的6种「树」，你心中有数吗？( 四 ) 数据结构这门课程是计算机相

Trie树（前缀树或字典树）Trie来源于单词 retrieve（检索）， Trie树也称为前缀树或字典树。利用字符串前缀来查找指定的字符串，缩短查找时间提高查询效率，主要用于字符串的快速查找和匹配。
为什么要称其为字典树呢？因为Trie树的功能就像字典一样，想象一下查英文字典，我们会根据首字母找到对应的页码，接着根据第二、第三...个单词，逐步查找到目标单词， Trie树的组织思想和字典组织很像，字典树由此得名。
文章插图
定义Trie的核心思想是空间换时间，有 3 个基本性质：

根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。

比如对单词序列lru, lua, mem, mcu 建立Trie树如下：

文章插图
Trie树建立和查询是可以同步进行的，可以在还没建立出完成的 Trie 树之前就找到目标数据，而如果用 Hash 表等结构存储是需要先建立完成表才能开始查询，这也是 Trie 树查询速度快的原因。
应用Trie树还用于搜索引擎的关键词提示功能。比如当你在搜索框中输入检索单词的开头几个字，搜索引擎就可以自动联想匹配到可能的词组出来，这正是Trie树的最直接应用。

文章插图
这种结构在海量数据查询上很有优势，因为不必为了找到目标数据遍历整个数据集合，只需按前缀遍历匹配的路径即可找到目标数据。
因此， Trie树还可用于解决类似以下的面试题：
?
给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。
?
?
有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M ，求频数最高的100个词
?
?
1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串，请问怎么设计和实现？
?
?
一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
?
总结一下树形数据结构有许多变种，这篇文章我们从树开始，把几种常见树形数据结构学习了一遍，包括二叉树、二叉查找树（二叉搜索树）、AVL树、红黑树、B树、Trie树。
文章构思的时候想聊聊数据结构中的树，没想到步子跨的有点大，大到不知从何说起，因为数据结构中各种树的变体非常多，一篇文章实难细数，篇幅有限，也只能说是浅尝辄止，作为树形数据结构入门，如果要深入的学习，每个知识点还能写出一篇文章，比如 B+ 树原理及其在数据库索引中的应用、红黑树的详细分析等等，这次柠檬只是粗略带大家走一遍。
在后端开发中，数据结构与算法是后端程序员的基本素养，除了基础架构部的后端开发同学，虽然我们平常不会经常造轮子，但是掌握基本的数据结构与算法仍然是非常有必要，面试也对相关能力有要求。