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