Trie

什么是 Trie

咱们晓得一个线性表的程序查找的工夫复杂度为 O(n)；二分搜寻树的查找为 O(log n)，它们都和数据结构中的元素个数相干。对于线性表和二分搜寻树的工夫复杂度剖析有须要的能够查看 Set 汇合和 BinarySearchTree 的工夫复杂度剖析

本文介绍的 Trie 字典树 (次要用于存储字符串) 查找速度次要和它的元素 (字符串) 的长度相干[O(w)]。

Trie 字典树次要用于存储字符串，Trie 的每个 Node 保留一个字符。用链表来形容的话，就是一个字符串就是一个链表。每个 Node 都保留了它的所有子节点。

咱们日常中应用的通讯录就是一个例子。

如果有 N 个条目，应用树结构查问的工夫复杂度是 O(logn)

而如果用 Trie 查问每个条目标工夫复杂度与字段中一共有多少条目无关！工夫复杂度为 O(W)

W 为查问单词的长度！

每个节点有 26 个指向下个节点的指针

Class Node{
        char c;
        Node next[26];
}

在 Trie 中叶子节点并不一定是单词的结尾，像平底锅的英文是 pan 而熊猫是 panda 咱们不能只依据叶子节点来辨别单词的开端，所以咱们须要一个变量来存储以后节点是否是某个单词的结尾。

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

特点

• 根节点不蕴含字符，除根节点外每一个节点都只蕴含一个字符
• 从根节点到某一节点，门路上通过的字符连接起来，为该节点对应的字符串
• 每个节点的所有子节点蕴含的字符都不雷同

Trie 字典树的新增

public class Trie {
        private class Node{
            public boolean isWord;
            public TreeMap<Character,Node> next;
            public Node() {this(false);
            }
            public Node(boolean isWord){
                this.isWord = isWord;
                next = new TreeMap<>();}
        }
        private Node root;
        private int size;
        public Trie(){root = new Node();
            size = 0;
        }
        // 取得 Trie 中存储单词的数量
        public int getSize(){return size;}
        // 向 Trie 中增加一个新的单词 word
        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 ++;
            }
        }
}

Trie 字典树的查问

    // 查问单词 word 是否在 Trie 中
    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;
    }
    // 查问是否在 Trie 中有单词以 prefix 为前缀
    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;
    }