深入理解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树在空间上也是有优化策略的,比如对部分前缀或者后缀进行压缩,这样以来能够节省不必要的指针存储,这种实现需要更复杂的编码来支持,感兴趣的朋友可以自己研究下。

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2019-05-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券