线段树、Trie和并查集02：Trie

Trie，又称字典树、前缀树，是一种N叉树

Trie是一种专门为字典设计的数据结构，通常只用来处理字符串；而之前的Map更适合称为映射而不是字典，因为其存储的对象不一定是字符串

如果用TreeMap和Trie来查询字符串，TreeMap的时间复杂度为O(logn)，而Trie的时间复杂度和总数n无关，只和字符串的长度有关，每个节点只存储一个字符

实现字典树

import java.util.TreeMap;

/**
 * 字典树一般存储的都是字符串，因此不使用泛型
 */
class Trie{

    private class Node{

        /**
         * 每个节点需要一个标志isWord来判断是否是一个字符串的结尾，因为很多字符串有重叠部分
         * 每个节点，其子节点的数目是不确定的，因此定义为TreeMap类型，每个节点的子节点都是一个集合，也即N叉树
         */
        public boolean isWord;
        public TreeMap 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;
    }

    public int getSize(){

        return size;
    }

    /**
     * 增
     * 从根节点出发，先判断子节点集合中有没有当前要放入的字符，没有就添加，然后继续向下寻找（寻找下一个符合的子节点使用Map类的get()方法）
     * 因为字符串可能重复，因此将新字符串的isWord设置为true，此时才能size加1
     */
    public void add(String string){

        Node cur = root;

        for (int i = 0; i < string.length(); i++) {

            char c = string.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++;
        }
    }

    /**
     * 查
     */
    public boolean contains(String string){

        Node cur = root;

        for (int i = 0; i < string.length(); i++) {

            char c = string.charAt(i);

            if (cur.next.get(c) == null){
                return false;
            }
            else {
                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;
            }
            else {
                cur = cur.next.get(c);
            }
        }

        return true;
    }
}

字典树的局限性

最大的问题：空间消耗！每个节点最少有26个子节点，都使用一个TreeMap集合来实现，空间消耗很大

优化的方向：压缩字典树、三分搜索树、后缀树

压缩字典树（Compressed Trie）

将字母合并为词缀

三分搜索树（Ternary Search Trie）

每个节点有三个孩子，分别小于、等于和大于自身