是什么？
Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树 或 键树，是一种多叉树结构。
上图是一棵Trie树，表示了关键字***{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。
从上图可以归纳出Trie树的基本性质：
根节点：根节点不包含字符，除根节点外的每一个子节点都包含一个字符。子节点：每个节点的所有子节点，包含的字符互不相同。路径：从根节点到某一个节点，路径上经过的字符连起来，为该节点对应的字符串。实际场景中，每个中间节点，会设置「一个标记」，用于标识当前节点是否构成一个单词（关键词）。
关键字，都存储在「路径」上，而没有存储再「节点」中。前缀树：公共前缀相等的「关键字」在 Trie Tree 中，前缀部分对应路径相同，因此，Trie 树，又称为前缀树。有什么用？
字典树，作为数据结构，有什么用？本质是：查询效率，或者说「时间复杂度」。
Trie树：
核心思想：空间换时间利用字符串的「公共前缀」，来减少无谓的字符串比较，以达到提高查询效率的目的。优点：
插入和查询的效率很高，都为O(m)，其中 m 是待插入/查询的字符串的长度。关于查询，会有人说 hash 表时间复杂度是O(1)O(1)不是更快？但是，哈希搜索的效率通常取决于 hash 函数的好坏，若一个坏的 hash 函数导致很多的冲突，效率并不一定比Trie树高。Trie树中，不同的关键字不会产生冲突。Trie树只有在允许一个关键字关联多个值的情况下，才有类似hash碰撞发生。Trie树不用求 hash 值，对短字符串有更快的速度。通常，求hash值也是需要遍历字符串的。Trie树可以对关键字，按字典序排序。缺点：
当 hash 函数很好时，Trie树的查找效率会低于哈希搜索。空间消耗比较大。具体的应用场景：
字符串检索词频统计字符串排序：Trie 树，每层节点采用「字典序」存储前缀匹配：例如网址自动提示其他数据结构和算法的辅助结构：后缀树、AC自动机等转自http://ningg.top/data-structure-series-01-trie-tree/
