数据结构之字典树Trie

字典树Trie

字典树也叫前缀树，是一种在字符串查找，前缀匹配等问题广泛应用的算法，为什么使用字典树呢？我们都知道如果对于一个存储有n个条目的数据集做查询，线性结构的时间复杂度是O(n)，这是相当恐怖的，改进的基于红黑树的查询时间复杂度是O(logn)，虽然已经好很多，但是当n非常大时，这个时间复杂度还是不能接受的。而字典树能做到查询的时间复杂度和数据集存储的数目n无关，而仅和被查询的字符串长度有关，所以它在查找时只有O(1)的时间复杂度。这是怎么做到的呢，其实很简单，下图是某存储英文的字典树的结构：

Trie

该树中存储了英语单词，如果要查询某个单词，比如，只需要先找到w，再找到i、n、d即可。可见对每个单词的查找只需要查找单词长度次，而且每次查找只需查找26次之内（即便算上大写也在52次之内）。
Trie数据结构设计要点：

• 添加操作：从根开始向下，如果某个节点没有则拓展一个新节点，添加完毕后在最后一个节点处将标志置true；
• 查询操作：基本过程与插入相同，向下查找，如果中间遇到一次节点不存在，直接返回false，一直向下查找，最终返回标志位；
• 每遍历到一个叶子节点，就查到一个单词（条目）；
• 可能某个单词是其它单词的前缀，如果没到叶子节点就存储了一个单词，则将此处标志置true。

---

字典树的实现
首先考虑节点结构，并假设这里的节点仅存储小写英文单词，故每个节点下应该有26个分支（实际如何存储根据具体情境）：

class Node{
    char c;
    Node next[26];//指向下一个节点
}

不过由于在寻找下一个节点时，我们实际上已经知道了要找哪个，故可以将当前节点和和其指向的节点存储为一个整体（相当于存储是在边上），考虑到Java中TreeMap中键值对中一个键对应的值可以添加多个，这些值组成一个keySet，故节点设计为：

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

其中isWord用于标识单词结尾，从而Trie类：

import java.util.TreeMap;
public class Trie {//不需要泛型，这里仅解决字符串类问题
    private class Node{//Trie的节点类
        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;
    private int size;

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

    //获取Trie中的单词数量
    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)//如果映射中没有包含到c的映射
                cur.next.put(c, new Node());
            cur = cur.next.get(c);
        }
        if (!cur.isWord) {//首先检查该单词是否已经存在
            cur.isWord = true;
            //此时来到了当前添加单词的最后节点，但不一定是叶子节点，因为可能是别的单词前缀
            size++;
        }
    }//作业：使用递归写法完成添加操作

    public boolean contains(String word){
        //查询单词word是否在Trie中
        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;
    }//作业，递归写法

    //其实Trie也是一个集合
    public boolean isPrefix(String prefix){
        //查询Trie中是否有单词以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;//和查询单词操作类似，不过无需检查是否包含单词
        //作业：BSTSet中查询前缀
    }
}

可以看到，Trie类的实现我们借助了TreeMap等底层数据结构，这正是数据结构的魅力，就像乐高积木一样，由一些基础的木块一步步搭建出美丽的艺术品。

Trie的应用——LeetCode207、211

LeetCode207不再介绍，就是设计一个字典树类，支持添加和查找操作，我们实现的类修改下类名即可。
LeetCode211

LeetCode211

这个题目其实和Trie类要完成的工作类似，不过加入了一些更灵活的条件（简易正则表达式），只需对我们的Trie类做小部分修改即可：

import java.util.TreeMap;
class WordDictionary {
    private class Node{//Trie的节点类
        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;
    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new Node();
    }
    public void addWord(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.next.get(c) == null)//如果映射中没有包含到c的映射
                cur.next.put(c, new Node());
            cur = cur.next.get(c);
        }
        if (!cur.isWord) //首先检查该单词是否已经存在
            cur.isWord = true;
    }
    public boolean search(String word) {
        return match(root, word,0);
    }
    private boolean match(Node node, String word, int index) {
        //从index处开始匹配
        if (index == word.length())
            return node.isWord;//递归终止条件,word匹配完毕,若为true则返回匹配成功,false匹配失败
        char c = word.charAt(index);
        if (c == '.') {
            for (char nextChar : node.next.keySet()) {//是.则遍历所有字母
                if (match(node.next.get(nextChar), word, index + 1))
                    return true;
            }
            return false;
        } else {
            if (node.next.get(c) == null)
                return false;
            return match(node.next.get(c), word, index + 1);//继续匹配后面的部分
        }
    }
}

可以发现，我们只对查询函数做了比较大的改动，而查询主要是基于递归实现的。
提交，获得通过！