1.trie是一个n叉树

一个微软的实习生为了解决手机通讯录软件查询储存了多个
联系人而研发了这个trie

trie又称之为前缀树

• 什么是trie?

什么是trie.png

tire是一个n叉树，每一个节点包含单词的标记，以key--value形式的当前字符与下一个节点的映射(由于设计原因，下一个节点的单词标记储蓄的为上一个节点key的单词标记)

二、trie中的操作实现

• trie中添加一个节点:非递归add、递归put
• trie的查询操作:非递归contain、递归include
• trie的前缀查询(LeetCode上208号问题):isPrefix
• Trie的删除操作:remove

Trie的删除操作.png

import java.util.TreeMap;

public class Trie {
    private class Node {
        public boolean isWord;
        public TreeMap<Character, Node> current; /**总感觉叫做next有点别扭*/

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

        public Node() {
            this(false);
        }
    }

    private Node root;
    private int size;

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

    /** 获得Tril中储存的单词的数量*/
    public int getSize() {
        return this.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.current.get(c) == null)
                cur.current.put(c, new Node());
            cur = cur.current.get(c); // 这里有一个坑！要注意
        }

        if(!cur.isWord) {
            size ++;
            cur.isWord = true;
        }
    }

    /** 向trie中添加一个节点，递归实现，思路与传统的有点不一样*/
    public void put(String word) {
        put(root, 0, word);
    }

    private void put(Node cur, int index, String word) {

        if(!cur.current.containsKey(word.charAt(index)))
            cur.current.put(word.charAt(index), new Node());

        cur = cur.current.get(word.charAt(index));
        if(index == word.length() - 1) {
            if(!cur.isWord){
                cur.isWord = true;
                size ++;
            }
            return;
        }

        put(cur, ++index, word);
    }

    /** trie的查询操作，非递归实现*/
    public boolean contain(String word) {
        Node cur = root;
        for(int i = 0; i < word.length(); i ++) {
            if(!cur.current.containsKey(word.charAt(i)))
                return false;
            cur = cur.current.get(word.charAt(i));
        }

        return cur.isWord;
    }

    /** trie 的查询操作，递归实现*/
    public boolean include(String word) {
        return include(root, 0, word);
    }

    private boolean include(Node cur, int index, String word) {
        char c = word.charAt(index);

        if(!cur.current.containsKey(c))
            return false;

        cur = cur.current.get(c);
        if(index == word.length() - 1)
            return cur.isWord;

        return include(cur, ++index, word);
    }

    /** trie的前查询，只要包含被查询的前缀，就返回true*/
    public boolean isPrefix(String prefix) {
        Node cur = root;

        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if(!cur.current.containsKey(c))
                return false;
            cur = cur.current.get(c);
        }

        return true;
    }

    /**查询字典中是否包含一个字符串，模糊匹配, 比如
     *  f.....d 这种，从根节点开始，.表示可以匹配任意字符！
     *  递归实现*/
    public boolean search(String word) {
        return search(root, 0, word);
    }

    private boolean search(Node node, int index, String word) {

        if(index == word.length())
            return node.isWord;

        char c = word.charAt(index);
        if(c != '.') {
            if(node.current.containsKey(c))
                return search(node.current.get(c), index + 1, word);
            else
                return false;
        } else {
            for (char ch :node.current.keySet()) {
                if(search(node.current.get(ch), index + 1, word))
                    return true;
            }
            return false;
        }
    }

    /**删除一个字符串；递归：回溯判断的思想,确认删除下一个节点就
     * 返回true,否则就返回false*/
    public boolean remove(String word) {
        return remove(root, 0, word);
    }

    /**当遍历到单词的末尾，有三种情况
     *  1. 当前并没有标记此单词，只是碰巧遇到了一个前缀
     *  2. 当前节点标记了此单词，但是也是一个前缀
     *  3. 当前节点标记了此单词，是末尾节点。
     *
     **当回溯删除到一定节点，有两种情况
     *  1. 当前节点是公共节点，不能删除
     *  2. 当前节点只有一个子节点，可以删除
     * */
    private boolean remove (Node node, int index, String word) {
        if(index == word.length()) {
            if(!node.isWord)
                return false;

            if(node.current.size() != 0) {
                node.isWord = false;
                return false;
            }

            return true;
        }

        char c = word.charAt(index);
        if(node.current.get(c) == null)
            return false;

        boolean charge = remove(node.current.get(c), ++index, word);

        if(charge && node.current.size() == 1) {
            node.current.remove(c);
            return true;
        }

        return false;

    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.add("abcdefg");
        trie.add("abcdeft");

        trie.add("dsldsaf.dfak");
        trie.add("asdfierdsfe3");
        trie.add("lokjjwdgh");
        trie.add("asrgtaolfeolag");

        trie.remove("abcdeft");
        trie.remove("dsldsaf");
        System.out.println(trie.contain("asrgtaolfeolag"));
    }

}

• 简单的模式匹配:leetCode-211

import java.util.TreeMap;

public class WordDictionary { // WordDictionary  Trie211
    private class Node {
        public boolean isWord;
        public TreeMap<Character, Node> current; /**总感觉叫做next有点别扭*/

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

        public Node() {
            this(false);
        }
    }

    private Node root;

    public WordDictionary() {
        this.root = new Node();
    }

    /** 向trie中添加一个节点,非递归实现*/
    public void addWord(String word) {
        Node cur = root;

        for(int i = 0; i < word.length(); i ++) {
            char c = word.charAt(i);
            if(cur.current.get(c) == null)
                cur.current.put(c, new Node());
            cur = cur.current.get(c); // 这里是一个坑！！！！
        }

        if(!cur.isWord) {
            cur.isWord = true;
        }
    }

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

    private boolean search(Node node, int index, String word) {

        if(index == word.length())
            return node.isWord;

        char c = word.charAt(index);
        if(c != '.') {
            if(node.current.containsKey(c))
                return search(node.current.get(c), ++index, word);
            else
                return false;
        } else {
            for (char ch :node.current.keySet()) {
                if(search(node.current.get(ch), ++index, word))
                    return true;
            }
            return false;
        }
    }

}

• Map Sum Pairs:leetCode-677

import java.util.TreeMap;

public class MapSum {

    private class Node {

        public int value;
        public TreeMap<Character, Node> next;

        public Node(int value) {
            this.value = value;
            this.next = new TreeMap<>();
        }

        public Node() {
            this(0);
        }
    }

    public Node root;

    public MapSum() {
        this.root = new Node();
    }

    public void insert(String key, int val) {
        Node node = root;

        for (int i = 0; i < key.length(); i++) {
            char c = key.charAt(i);
            if(!node.next.containsKey(c))
                node.next.put(c, new Node());
            node = node.next.get(c);
        }

        node.value = val;
    }

    public int sum(String prefix) {
        Node node = root;

        for(int i = 0; i< prefix.length(); i ++) {
            char c = prefix.charAt(i);
            if(!node.next.containsKey(c))
                return 0;
            node = node.next.get(c);
        }

        return sum(node);
    }

    private int sum(Node node) {

        int count = node.value;
        for(char c : node.next.keySet())
            count += sum(node.next.get(c));

        return count;
    }

    public static void main(String[] args) {
        MapSum mapSum = new MapSum();
        mapSum.insert("apple", 3);
        System.out.println(mapSum.sum("ap"));
        mapSum.insert("app", 2);
        System.out.println(mapSum.sum("ap"));
        mapSum.insert("apply", 3);
        System.out.println(mapSum.sum("ap"));

    }
}

三、更多和Trie相关的话题

Trie的局限性 :最大的问题，空间问题

class Node{
    boolean isWord;
    TreeMap<Character, Node> next;
}

对于这个问题，有一个优化--压缩字典树

1.Compressed Trie

压缩字典树.png

但是带来的问题是 维护成本增高了

2.Ternary Search Trie 三分搜索树

三分搜索树1.png

三分搜索树2.png

字符串模式识别 后缀树

更多字符串问题 (计算机科学领域研究的非常深入的一个问题：代码？网页？等等.....)

• 1. 子串查询算法
  • KMP
  • Boyer-Moore
  • Rabin-Karp
• 2. 文件压缩(对一个非常大的字符串压缩)
• 3. 模式匹配(正则表达式引擎)
• 4. 编译原理(编译Java源码的Java编译器)
• 5. DNA 生命科学领域

等等...