Trie 树也叫“字典树”，是一种专门处理字符串匹配的树形结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
Trie 树特有的优点，决定它特别适合做搜索引擎的搜索关键词提示功能：在搜索引擎的搜索框中，输入要搜索的文字的某一部分的时候，搜索引擎就会自动弹出下拉框，里面是各种关键词提示。可以直接从下拉框中选择你要搜索的东西，而不用把所有内容都输入进去，一定程度上节省了我们的搜索时间。
Trie 树到底长什么样子：
假设有 6 个字符串分别是：how，hi，her，hello，so，see，组织成 Trie 树的结构，之后每次查找，都是在 Trie 树中进行匹配查找。
Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。最后构造出来的就是下面这个图中的样子：
1570500434769
其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（红色节点并不都是叶子节点）。
Trie 树构造的过程：
1570500456458
在 Trie 树中查找字符串的时候，比如查找字符串“her”，先将要查找的字符串分割成单个的字符 h，e，r，然后从 Trie 树的根节点开始匹配。下图中绿色的路径就是在 Trie 树中匹配的路径。
1570500470544
要查找字符串“he”，先将要查找的字符串分割成单个的字符 h，e。然后从根节点开始沿着某条路径来匹配，下图绿色的路径就是“he”匹配的路径，但路径最后一个节点“e”并不是红色的（“he”是某个字符串的前缀子串），说明未匹配。
1570500495719
Trie 树主要有两个操作：