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