概述

百度官方：字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

字典树又叫前缀树、Trie树、单词查找树，是一种多路树形（N叉树）结构，哈希树的变种。通常来说，一个前缀树是用来存储字符串的。前缀树的每一个节点代表一个字符串（前缀）。每一个节点会有多个子节点，通往不同子节点的路径上有着不同的字符。子节点代表的字符串是由节点本身的原始字符串，以及通往该子节点路径上所有的字符组成的。

比如：
字典树

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

应用场景

1.字符串的快速检索

查询时间复杂度是O(logn)

(1).hash表

通过hash函数把所有的单词分别hash成key值，查询的时候直接通过hash函数即可，都知道hash表的效率是非常高的为O(1)，当然这是对于如果我们hash函数选取的好，计算量少，且冲突少，那单词查询速度肯定是非常快的。那如果hash函数的计算量相对大呢，且冲突律高呢？这些都是要考虑的因素。

更重要的是不支持动态查询，就是说只能完整输入，靠完整的输入来查找答案，不能一步一步的进行，比如输入people，必须输完people才能hash。

(2)字典树Trie

空间允许的话，比hash好，因为可以动态查询。

可以使用的场景：

1. 串排序
   给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出：
   用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。
2. 最长公共前缀
   看结构图就懂了。对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为当时公共祖先问题。
3. 自动匹配前缀显示后缀/串的快速检索
   输入peo，自动显示前缀是peo的各种信息。

实现

3个性质

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
2. 根节点到某一节点，路径上讲过的字符连接起来，为该节点对应的字符串
3. 每个节点的所有子节点包含的字符都不同

基本操作的实现

1. 查找
   首先：从根节点开始，
   其次：循环要插入的字符串，把字符串每一位放进去

1

2. 插入
3. 删除（较为少见）

实现