LeetCode题目中有关前缀树的描述：Trie前缀树-字典树

前缀树

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。

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

Trie树也有它的缺点，Trie树的内存消耗非常大。

性质：不同字符串的相同前缀只保存一份。

操作：查找，插入，删除。

前缀树的3个基本性质：

字典序排序算法：

是一种基于字典序对随机序列生成全排列的排序方法，通常用于解决这样的问题：给定其中一种排列，求基于字典序的下一种排列（要求下一种排列必须比原排列大，并且二者之间不能存在第三种排列，即下一种排列为大于原排列的最小排列）。

比如给定的排列为 afhdceb，则它的下一种排列为 afhdebc；又比如给定的排列为 5482631，则它的下一种排列为 5483126。

算法的求解步骤

以上述的5482631为例，字典序排序算法的求解步骤如下： （1）在原排列中，从右往左找出数组（序列）中第一个正序（即左边数字小于右边数字），计左边数字的下标为left，计当前左边数字为leftValue，此处left=3，leftValue=2。 （2）在原排列中，再次从右往左找出第一个比leftValue大的数，此时该数的下标记为right，此处right=5，其对应的值为3。 （3）将原排列中第left位与第right位交换（即 2 与 3 交换）后，原排列变为 5483621。 （4）将原排列从left+1到数组（序列）的末尾的数按从小到大排序，得到最小排列126，因此求得原排列的下一个排列为 5483126。

如果你跟我一样不理解，那就和我一起多看几个例子：

​ 如果当前排列是124653,找它的下一个排列的方法是，从这个序列中从右至左找第一个左邻小于右邻的数，

​ 如果找不到，则所有排列求解完成，如果找得到则说明排列未完成。

​ 本例中将找到46,计4所在的位置为i,找到后不能直接将46位置互换，而又要从右到左到第一个比4大的数，

​ 本例找到的数是5，其位置计为j，将i与j所在元素交换125643,

​ 然后将i+1至最后一个元素从小到大排序得到125346，这就是124653的下一个排列。

总结得出字典排序算法四步法：

字典排序： 第一步：从右至左找第一个左邻小于右邻的数，记下位置i，值list[a] 第二部：从右边往左找第一个右边大于list[a]的第一个值，记下位置j，值list[b] 第三步：交换list[a]和list[b]的值 第四步：将i以后的元素重新按从小到大的顺序排列

举例：125643的下一个字典序列 第一步：右边值大于左边的35,j=3;list[b]=6; 第三步：交换list[a]和list[b]的值，序列125643->126543 第四步：将位置2以后的元素重新排序,126543->126345; 结束： 126345即125643的下一个序列

前缀树的应用：

（1）字符串的快速检索

字典树的查询时间复杂度是O(logL)，L是字符串的长度。所以效率还是比较高的。字典树的效率比hash表高。

（2）字符串排序

​ 从下面例子我们很容易看出单词是排序的，先遍历字母序在前面。

​ 减少了没必要的公共子串。

（3）最长公共前缀

​ abc和abd的最长公共前缀是ab，遍历字典树到字母c时，此时这些单词的公共前缀是ab。

（4）自动匹配前缀显示后缀

​ 我们使用辞典或者是搜索引擎的时候，输入appl，后面会自动显示一堆前缀是appl的东东吧。

​ 那么有可能是通过字典树实现的，前面也说了字典树可以找到公共前缀，我们只需要把剩余的后缀遍历显示出来即可。

举例：

题目：给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。

如果我们使用一般的方法，没查询一个单词都去遍历一遍，那么时间复杂度将为O(n^2),这对于100000这么大的数据是不能够接受的。假如我们要查找单词student。那我们通过前缀树只需要查找s开头的即可，然后接下来查询t开头的即可，对于大量的数据可以省去不少的时间。

树结构：

​ 其中count表示以当前单词结尾的单词数量。

​ prefix表示以该处节点之前的字符串为前缀的单词数量。

前缀树的创建

假设有b，abc，abd，bcd，abcd，efg，hii 这6个单词,那我们创建trie树就得到