Trie

2020-04-18

字典树(Trie)

Trie一般是用来处理字符串。

如果有n个条目，使用树结构的话，我们试想最好的情况下，即不会退化成链表时，查询的时间复杂度为O(logn)。

这个时间复杂度已经很低了，但是当有100万个条目时(2^20)，此时logn大约为20.

而Trie这种数据结构查询每个条目的时间复杂度和字典中一共有多少条目无关！

只与我们查询的字符串的长度相关，时间复杂度为O(w),w为查询单词的长度！这是非常高效的，因为在大多数情况下单词的长度都是小于10的。

如果考虑常规情况，即我们查询26个英文字母的话，每个节点有26个指向下个节点的指针（在不考虑大小写的情况下）并且我们只适用于单词场景，如果用来记录那种邮件名的话，我们还应该加入如”@.”这样的符号.

这时，我们将上述定义改一下 : 每个节点有若干指向下个节点的指针

class Node{
  	char c;
  Map<char,Node>next;
}

这时候我们思考这样一个问题，当我们需要查一个单词时，我们首先知道首字母才会往下查，我们应该把字母标在边上，而不是节点上，我们在来到这个节点之前就知道这个字母是什么了.

1
2
3

class Node{
  Map<char,Node>next;
}

即此时我们不必存储char的值.

在英语单词中，很多单词是某个单词的前缀，比如pan->panda.如果我们以每个单词的结尾作为叶子节点的话，这时候就有矛盾了，明明pan已经结尾了，我们如果还需要查询panda的话，无法查询，这时候我们在Node节点中引入一个标记，标记它是否是某个单词的结尾，某个单词的结尾只靠叶子节点是无法区别的。

class Node{
  boolean isWord;
  Map<char,Node>next;
}

Trie又叫做前缀树，我们在搜索一个单词中，所经过的一路都是目标单词的前缀。

下面就来实现一个Trie吧！

public class Trie{
  private class Node{
    public boolean isWord;
    public TreeMap<Character,Node>next;
  }
  public Node(boolean isWord){
    this.isWord=isWord;
    next=new TreeMap<>();
  }
  public Node(){
    this(false);
  }
  //根节点
  private Node root;
  public int size;
  public Trie(){
        root=new Node();
        size=0;
    }
   /**
     * 获得Trie中存储的单词数量
     * @return
     */
    public int getSize(){
        return size;
    }
 /**
     * 向Trie中添加一个新的单词word
     * @param word
     */
    public void add(String word){
        Node cur=root;

        for (int i = 0; i <word.length() ; i++) {
            char c=word.charAt(i);
            //将c作为一个节点插入到Trie中
            if(cur.next.get(c)==null){
                cur.next.put(c,new Node());
            }
            cur=cur.next.get(c);
        }
        //这个节点以前不表示一个单词的结尾
        if(!cur.isWord){
            cur.isWord=true;
          //维护size
            size++;
        }
       /**
     * 查询单词word是否在Trie中
     * @param word
     * @return
     */
      public boolean contains(String word){
        Node cur=root;
        for(int i=0;i<word.length();i++){
          char c=word.chatAt(i);
          if(cur.next.get(c)==null){
            return false;
          }
          cur=cur.next.get(c);
       }
        return cur.isWord;
      }
       /**
     * 查询是否有单词以prefix为前缀
     * @param prefix
     * @return
     */
    public boolean isPrefix(String prefix){
       Node cur=root;
       for(int i=0;i<prefix.length();i++){
           char c=prefix.charAt(i);
           if(cur.next.get(c)==null){
               return false;
           }
           cur=cur.next.get(c);
       }
       return true;
    }

      
}

通过上述代码，我们简单的实现一棵前缀树，具备增加元素，查询元素以及判断是否有前缀的功能。

关于前缀树

LeetCode 208、实现Trie https://leetcode-cn.com/problems/implement-trie-prefix-tree/

题目要求实现一棵前缀树，我们可以直接将上述的前缀树进行拷贝，就可以AC了。

class Trie {
       private class Node{
           public boolean isWord;
           public Map<Character,Node> next;

           public Node(boolean isWord){
             this.isWord=isWord;
             next=new TreeMap<>();
           }
           public Node(){
               this(false);
           }
       }
       private Node root;
    /** Initialize your data structure here. */
    public Trie() {
        root=new Node();

    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {

            Node cur=root;
            for(int i=0;i<word.length();i++){
                char c=word.charAt(i);
                if(cur.next.get(c)==null){
                    cur.next.put(c,new Node());
                }
                cur=cur.next.get(c);
                
            }
            if(!cur.isWord){
                cur.isWord=true;
            }

    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Node cur=root;
        for(int i=0;i<word.length();i++){
            char c=word.charAt(i);
            if(cur.next.get(c)==null){
                return false;
            }
            cur=cur.next.get(c);
            
        }
        return cur.isWord;

    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
           Node cur=root;
           for(int i=0;i<prefix.length();i++){
               char c=prefix.charAt(i);
               if(cur.next.get(c)==null){
                   return false;
               }
               cur=cur.next.get(c);
           }
           return true;
    }
}