Trie 前缀树

Trie 是一种特殊的数据结构，可以看作是 多叉树 与 链表 的结合体，其主要作用是用于 前缀查询 与 模式匹配。

什么是 Trie?

Trie 是一种特殊的数据结构，可以看作是 多叉树 与 链表 的结合体，它长这样:

每一个节点都含有多个指针，指向下一个节点，我们可以用一个Map 来实现这种功能。另外蓝色节点代表这个节点是一个单词的末尾。比如 "p" -> "a" -> "n" 中的 "n" 就是蓝色节点，这代表当前 Trie 中包含 “pan" 这个单词。而"c" -> "a" -> "t" 中的 "t" 是红色节点，则代表当前 Trie 中不包含 “cat" 这个单词。

Trie的性能特性

在现实中，需要存储的字符的种类是有限的（比如英文大小写，数字，还有一些特殊符号），在每一个节点的分叉支路也是有限的，那么我们可以得出以下结论： 在 Trie 中增加，查找 某个字符串的时间复杂度均为 O(h), h 为字符串长度，与Trie 中字符串的个数无关。

实现一个 Trie

构造方法

构造方法非常简单，isWord 表示是否为字符串结尾，true代表是结尾，也就是上图中的蓝色节点。

public class Trie {

    private class  Node{

        public  boolean isWord;

        public TreeMap<Character, Node> next;

        public Node(boolean isWord ) {
            this.isWord = isWord;
            next = new TreeMap<Character, Node>();
        }

        public Node(  ) {
            this(false);
        }

    }

    private  Node root;
    private int size;

    public Trie(){
        root=new Node();
        size=0;
    }
    
}

获取字符串个数

public int getSize(){
    return size;
 }

添加字符串

添加字符串非常简单，只需要依次按照字符串的每一位，在Trie中遍历即可，遇到不曾出现的字符，就新建一个节点。

public void add(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;
        size++;
    }
}

特别的是第12-14行，在最后一个字符时需要判断这个字符串是不是之前就已经存在了，若之前不存在才需要将 isWord 设置为 true, size++。否则 size 会多加1, 出现bug。

查询与前缀查询

查询 与前缀 查询的代码逻辑与 添加 操作类似，都是在 Trie 中一个个查询 字符串的每一位。去别在于 contains 需要确认最后一个字符对应的节点的 is.Word 是否为真，而前缀查询则不需要。

public boolean contains(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;

}

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;
}

模式匹配

Trie 另一个重要应用是模式匹配，比如查询”p...a“ 是否存在，其中的 "."代表可以为任意字符，返回 true 或 false。需要用到树的深度优先算法，我们可以用递归离开完成：

public boolean match(String word){
    return match(root,word,0);
}

private boolean match(Node node, String word, int depth){
    if (depth==word.length()){
        return node.isWord;
    }

    char c=word.charAt(depth);
    if (c!='.'){
        if (node.next.get(c)==null){
            return  false;
        }else{
            return match(node.next.get(c),word,depth+1);
        }
    }else {
        for (char nextChar : node.next.keySet()){
            return match(node.next.get(nextChar),word,depth+1);
        }
        return false;
    }
}

测试一下

简单测试一下我们写的 Trie

public class TrieTest {

    public static void main(String[] args) {

        Trie trieSet=new Trie();
        trieSet.add("cater");
        trieSet.add("dog");
        trieSet.add("deer");
        trieSet.add("pan");
        trieSet.add("panda");

        System.out.println(trieSet.contains("cat"));
        System.out.println(trieSet.isPrefix("cat"));
        System.out.println(trieSet.contains("pan"));
        System.out.println(trieSet.isPrefix("pan"));
        System.out.println(trieSet.match("de.r"));
        System.out.println(trieSet.match("d..d"));

    }
}

输出结果：

false
true
true
true
true
false