深入理解Trie树
前言
前面的文章介绍过各种高效的的数据结构，比如二叉搜索树，AVL树，红黑树，B树，跳跃表等，今天我们再来学习一种多路树，叫做Trie树。
什么是Trie树
在计算机科学中，Trie，又称前缀树或字典树，是一种有序树，用于保存关联数组。其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。Trie树的名称来源于搜索引擎中的专有名词的retrieval，发音和单词try一样。
比如下面的这个Trie树包含“Cat”，“Cut”，“Cute”，“To”，“B”五个单词，其存储图示如下：
从上面我们可以发现，前缀一样的单词，在实际存储中只存储了一份，并且如果单词后面有.符号表从root到这个位置是一个单词，前缀相同的单词会复用一样的公共节点。
Trie树的应用场景
Trie最典型的应用场景是用于搜索引擎的suggest功能，比如我们在google中，每输入一个英文字母，搜索引擎都会给过我们返回以这个字母为前缀的相关的结果，如下：
除以之外，还有常见的IDE里面自动补全功能和各种通讯录的自动补全功能等。
Trie树的工作原理
这里以英文单词为例，我们知道英语单词由26个字母组成，每一个字母都是这26个字母中的其中一个，假如现在我们想为英语单词的suggest功能，那么使用Trie树就非常适合。因为总共的可能性只有26，所以我们可以定义一个长度为26的数组来存储所有的可能性，然后附带一个boolean类型的变量，来标记当前层是否是一个单词。
如下定义：
static class TrieNode{ TrieNode[] children; boolean isWord;
public TrieNode(){ children=new TrieNode[26]; } }如何插入
Trie树的结构，通常需要一个虚拟的head节点来辅助，head节点并不存储数据，仅仅用于操作方便，在插入的时候，会分解单词为一个字符数组，然后依次插入其中的每一个字母到Trie树里面，如果插入的位置不存在该字母，那么代表第一次插入，就需要新建一个TrieNode节点， 如果插入的地方已经存在，那么就直接继续插入下一个字母，直到整个单词的每一个字母都插入完毕后，在最后一个TrieNode节点处标记到目前这个节点处，代表一个完整的单词。
如何查询
查询主要有两种形式，第一种是判断是否存在某个单词在Trie树里面，第二种是判断指定的前缀是否在Trie树里面存在。
这两种case的检索方式大致一样，就是从head节点入手，判断这个单词的第一个字母是否存在，如果就跳到第二级继续搜索，知道遍历完整个字母，返回最后一个节点，然后判断如果该节点有数据，并且有完整单词标记，那么就证明该单词存在，如果没有单词标记，那么证明该前缀存在。如果判断返回的节点没有数据，那么就证明当前的Trie树里面不包含某个单词或者输入的指定的前缀。
如何删除
Trie树的相对来说稍微复杂点，举个例子，比如包含6个单词的Trie树：
("abc")("xy")("xyz")("abb")("xyzb"), ("word")图示如下：
我们看删除的几种情况：
（1）如果要删除的单词不存在，则不做任何操作
（2）如果要删除的单词是没有任何字母被作为公共前缀，那么就要删除每个字母，如上图的单词word
（3）如果要删除的单词全部字母都是公共前缀，那么仅仅在这个单词的尾部标记不是完整单词即可，如上图的单词xyz
（4）如果要删除的单词是超出了公共前缀，那么仅仅删除多出的部分即可，如上图的xyzb，在删除的时候仅仅删除字母b即可。
（5）如果要删除的单词是两条路径的公共前缀，那么仅仅删除非公共前缀的部分即可，这种情况与（4）类似，但不同的是（4）是在一条路径上，而（5）是在两条路径上，如上图要删除abc，因为前缀ab是共用的，所以仅仅删除abc的c字母即可。
上面就是删除的全部情况，不过在Trie树里面，重要的部分是插入和检索部分，删除部分可能比较少的使用。
Trie树的实现方式
Trie树有两种实现策略，第一种使用数组存储所有的可能性，第二种是使用的Map存储所有的可能性，使用数组的方式需要对存储的字符和数组的index之间要有明确的映射规则，这样便于查询，比如如果想做中文的suggest，一种的可行的办法就是将整个中文字符集映射到具体的数值上，然后与上面字母的操作类似，如果选择使用Map作为可能性存储，相对来说会更加灵活一点，毕竟Map在大多数编程语言里面都有封装好的动态实现。
下面给出的是基于数组实现Trie树的方式，基于Map的实现方式可以参考我的github的代码：
https://github.com/qindongliang/Java-Note
public class TrieByArray {
static class TrieNode{ TrieNode[] children;//存储所有的可能性 boolean isWord;//是否是一个完整单词 public TrieNode(){ children=new TrieNode[26]; } }
TrieNode root;
public TrieByArray(){ root=new TrieNode(); }
public void insert(String word){
TrieNode prev=root;
for (int i = 0; i < word.length(); i++) {
if(prev.children[word.charAt(i)-'a']==null){ prev.children[word.charAt(i)-'a']=new TrieNode(); }
prev=prev.children[word.charAt(i)-'a'];
}
prev.isWord =true;
}
public boolean search(String word){ TrieNode result=checkExists(word); if(result!=null&&result.isWord){ return true; } return false;
}
public TrieNode checkExists(String query){
TrieNode cur=root;
for (int i = 0; i < query.length(); i++) { //待查询的字符不存在 if(cur.children[query.charAt(i)-'a']==null){ return cur.children[query.charAt(i)-'a']; }else{ cur=cur.children[query.charAt(i)-'a'];; } }
return cur; }
public void delete(String key){ if(root==null||key==null){ return; }
deleteWord(root,key,key.length(),0);
}
private boolean hasChildren(TrieNode currentNode){ for (int i = 0; i < currentNode.children.length; i++) { if(currentNode.children[i]!=null){ return true; } } return false; }
public boolean deleteWord(TrieNode currentNode,String word,int length,int level){ boolean deletedSelf=false; if(level==length){ //如果当前节点是最后，并且没有孩子节点 if(!hasChildren(currentNode)){ currentNode=null; deletedSelf=true; }else{//有孩子节点 currentNode.isWord =false;//则将其置为非单词属性即可 deletedSelf=false; }
}else { //由下而上递归删除 TrieNode childNode=currentNode.children[word.charAt(level)-'a']; boolean childDeleted=deleteWord(childNode,word,length,level+1); if(childDeleted){//如果单词的最后的字符没有孩子节点，就可以被删除，然后需要继续向上递归判断其前一个字符是否是需要删除 currentNode.children[word.charAt(level)-'a']=null;//设置子节点为null if(currentNode.isWord){//判断父节点是否是一个word的结束，如果是说明是公共前缀就不能再删除了 deletedSelf=false; }else if(hasChildren(currentNode)){//如果这个父节点还有孩子节点，说明也是公共前缀，也不能再删除了 deletedSelf=false; }else{//到这一步，说明父节点也是要删除单词唯一的的字符，可以继续向上删除 currentNode=null; deletedSelf=true; } }else {//如果不需要被删除，则向上传递false即可 deletedSelf=false; } }
return deletedSelf; }
public boolean startsWith(String prefix){ TrieNode result=checkExists(prefix); if(result!=null){ return true; } return false; }
public static void main(String[] args) {
TrieByArray trie=new TrieByArray(); trie.example1();// trie.example2();// trie.example3();
}
private void example1(){ TrieByArray trie = new TrieByArray();
trie.insert("apple"); System.out.println(trie.search("apple")); // returns true
System.out.println(trie.search("app")); // returns false System.out.println(trie.startsWith("app")); // returns true trie.insert("app"); System.out.println(trie.search("app")); // returns true }
private void example2(){ TrieByArray trie = new TrieByArray();
trie.insert("gat"); trie.insert("gag"); System.out.println(trie.search("gat"));//true System.out.println(trie.startsWith("ga"));//true trie.delete("gat"); System.out.println(trie.search("gat"));//false System.out.println(trie.startsWith("ga"));//true System.out.println(trie.search("gag"));//true }
private void example3(){ TrieByArray trie = new TrieByArray(); trie.insert("abcd"); trie.insert("abc");
System.out.println(trie.search("abc")); System.out.println(trie.startsWith("abc"));
trie.delete("abc");
System.out.println(trie.search("abc")); System.out.println(trie.search("abcd")); System.out.println(trie.startsWith("abc")); }
}Trie树的时间和空间复杂度分析
Trie树的时间复杂度为O（k），k=该字符串（单词或者前缀）的长度，在最好最坏的case均为O（k）。
Trie树的空间复杂度，如果重复的前缀比较多，那么一定程度上使用Trie是可以节省存储空间的，但如果重复的前缀不多，这样就会导致Trie消耗大量内存，为什么这么说？
还记得上面数组的实现方式吗？在TrieNode里面需要把每一种可能性都要提前存储到一个数组，方便查找，拿英文单词为例，一个单词cat，看起来只需要3个char字符的空间就可以了，但实际上每个字符都需要存储一个26大小的指针数组，这样就需要O（n*k）的空间来存储，k=字符串的长度，n=共有多少个这样不重复的字符，这么算下来，其实Trie树的原理，可以看做是拿空间换时间的实现策略。
那么有的同学会说使用数组的方式为了查找快速，没办法只能那么存，那么使用Map的方式是不是就节省内存了？其实并不是，不要忘记，Map的底层也是通过数组+链表+红黑树的方式实现的，初始化容量和每次扩容也都是需要开辟大量的前置空间来存储的。所以相比数组的方式可能还要更浪费内存。
总结
本文详细的介绍了Trie树相关的内容，Trie树作为一种特殊的数据结构，虽然在实际开发中并不常用，但其在特定的场景下比如suggest自动补全功能，可以发挥的出色的表现。Trie树本质上是一种通过空间换时间的策略，来提高检索性能，所以在使用的时候要注意内存限制。当然，Trie树在空间上也是有优化策略的，比如对部分前缀或者后缀进行压缩，这样以来能够节省不必要的指针存储，这种实现需要更复杂的编码来支持，感兴趣的朋友可以自己研究下。
腾讯云开发者
