TRIE树

TRIE(前缀树/字典树)

TRIE常用于存储和表示字符串的集合，并实现该集合上的增删字符串运算。其核心思想是用公共前缀表示字符串，比如abcd与abc的公共前缀是abc，当字符串间恰好没有公共前缀时，比如abc,edfg,czx构成的集合，那么其会存储3个前缀abc,edfg,czx。

其常用于存储字符串构成的集合。其结构是这样的，Trie的根节点不存储字符，其他节点仅存储单个字符，且同一层节点无重复字符。节点有变量存储“颜色”，若某节点被“染色”说明从根到该节点的路径存储了一个字符串，除此之外Trie的叶节点肯定是“染色”的。下面讨论Trie的运算结构：

1）插入：首先查找根节点全部孩子节点，若找到待插入串首字符则进入该节点并重复该步骤，若没有则在该处新建节点并插入剩余字符，最终为叶节点染色。如果用哈希表/dict来记录每个节点的儿子，可以在\(O(1)\)时间完成当前层的查找，所以可以认为时间复杂度为字符数\(O(n)\)。

2）遍历：首先想到利用节点遍历来实现，如果在节点遍历的同时记录了当前的途径路径，那只要在节点被遍历时判断当前节点是否被“染色”即可解决这个问题。可以发现这个解决方法与节点的深度优先遍历是同步进行的，所以其代价为节点数\(O(n)\)。

3）删除：首先逐个查找每个字符对应节点，直到到达待删除串尾字符的对应节点，若其是叶节点则将其删除，若其不是叶节点则取消“染色”。若未找到待删除串则返回。删除的代价是字符数\(O(n)\)。

4）查找：删除中已经讨论了查找的逻辑。

5）查找前缀：跟查找差不多。

Trie本身虽然不复杂，但其在字符串处理中的应用十分广泛，举些比较基本的例子：

1）字符串排序：这里排序是指把若干字符串，以英语字典那样的方式来排序。这可以通过规定记录子节点的序列中的元素顺序来实现，如果规定序列元素按照abcd的顺序排序，那么对这个Trie树进行上述字符串遍历即可得到排序结果。

2）字符串统计：该问题指“有一篇A个单词的文章与B个单词组成的单词表，统计单词表中各个单词在该文章的出现次数”。方法是把单词表建成Trie树，然后在Trie上查找每个单词。

3）字符串去重：把这些字符串建成Trie然后再遍历该Trie即可去重。

4）字符串前缀：Trie树可用来解决关于前缀的很多问题，例如“求多个字符串的最大公共前缀”，“求单词表中与目标单词公共前缀最长的单词”。解决第一个问题仅需把这些字符串建成Trie树，然后找出一条最长路径，这个路径的每个节点只有一个子节点。解决第二个问题同样也比较容易。

5）字符串匹配：Trie树是著名多模匹配算法“AC自动机”的基础，后面写了篇文章讨论这个。