简介

Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。

核心思想

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

优缺点

它的强大之处在于它的时间复杂度，插入和查询的时间复杂度=O(K)，K为字符串的长度，与字符串的数目无关
优点在于最大限度地减少无谓的字符串比较，查询效率比哈希表高。
缺点在于空间消耗很高，但是目前也有技术（双数组的实现方案）解决这样的问题

实现

1. 数组实现
2. 指针动态分配

典型应用

1. 统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计
2. 字符串检索
3. 字符串最长公共前缀
4. 排序， 给你N 个互不相同的仅由一个单词构成的英文名，让你将它们按字典序从小到大排序输出。
5. 作为其他数据结构和算法的辅助结构，例如后缀树和AC自动机

性质和特性

Trie树的基本性质可以归纳为：
1. 根节点不包含字符，除根节点以外每个节点只包含一个字符。
2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符串不相同。

Trie树有一些特性：
1. 如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。
2. 插入查找的复杂度为O(n)，n为字符串长度。
3. 插入+查询可以同时完成，建立的过程就是查询的过程

操作的实现

1. 插入过程
   对于一个单词，从根开始，沿着单词的各个字母所对应的树中的节点分支向下走，直到单词遍历完，将最后的节点标记为红色，表示该单词已插入Trie树。
2. 查询过程
   同样的，从根开始按照单词的字母顺序向下遍历trie树，一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色，则表示该单词不存在，若最后的节点标记为红色，表示该单词存在。

Bug Free Procedure 从记事本直接写代码

2016.12.16 新建单词函数出错
1. 新建Trie树节点的函数中忘记返回节点指针