数据结构——Trie 字典树前缀树

清疚 2022-05-14 15:27 328阅读 0赞

## 一、什么是Trie ##

Trie不同于二分搜索树、堆、线段树等二叉树结构，**Trie是一个多叉树**。使用场景：通讯录高效搜索，专为处理字符串设计的。

比如字典中有n条数据，**如果使用树结构**，查询的时间复杂度是O(logn)，如果有100万条数据的话，logn大约是20，如果有1亿条数据的话，logn大约是30([参考2的N次方计算器][2_N])

**如果使用Trie这种数据结构，查询每条数据的时间复杂度和字典中一共有多少条数据没有关系**！是不是屌炸天呢？

Trie查询的时间复杂度与查询的字符长度有关，**时间复杂度为：O(w)**，w为单词的长度。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 1][]

## 二、构建一个Trie ##

### Trie的基本结构与添加方法： ###

public class Trie {
        private class Node {
            public boolean isWord;
            public TreeMap<Character, Node> 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;
        }
    
        //获得Trie中存储的单词数量
        public int getSize(){
            return this.size;
        }
    
        //传递入一个字符串(单词),拆分成一个个的字符char
        public void add(String word){
            Node cur = root;
            for(int i = 0 ; i < word.length() ; i ++){
                char c = word.charAt(i);
                //判断当前的cur节点下一节点隐射中是否有指向c的节点
                if(cur.next.get(c) == null)
                    cur.next.put(c,new Node());
                //循环结束后cur来到字符串最后一个字符所处节点，但并不一定是叶子节点,如pan和panda
                cur =  cur.next.get(c);
            }
            //如果已经存在panda,则在add(pan)时候,只是走了3遍cur =  cur.next.get(c);
            //不重复添加元素
            if(!cur.isWord) {
                cur.isWord = true;
                size++;
            }
        }
    }

### 判断某个单词在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字典树的前缀查询 ##

//Trie字典树的前缀查询
        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;
        }

## 四、Trie字典树搜索和正则匹配 ##

对应Leetcode  [211题添加与搜索单词][211]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 2][]

参考模型：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 3][]

import java.util.TreeMap;
    
    /**
     * Your WordDictionary object will be instantiated and called as such:
     * WordDictionary obj = new WordDictionary();
     * obj.addWord(word);
     * boolean param_2 = obj.search(word);
     */
    class WordDictionary {
    
        private class Node{
            public boolean isWord;
            public TreeMap<Character,Node> next;
    
            public Node(boolean isWord){
                this.isWord = isWord;
                next = new TreeMap<>();
            }
    
            public Node(){
                this(false);
            }
        }
        private Node root;
    
        /** Initialize your data structure here. */
        public WordDictionary() {
            root = new Node();
        }
        
        /** Adds a word into the data structure. */
        public void addWord(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);
            }
            cur.isWord = true;
        }
        
        /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
        public boolean search(String word) {
            return match(root,word,0);
        }
    
        private boolean match(Node node, String word, int index) {
            if(index == word.length())
                return node.isWord;
            char c = word.charAt(index);
            if(c!='.') {
                if (node.next.get(c) == null)
                    return false;
                return match(node.next.get(c),word,index + 1);
            }else{
                for(char nextChar : node.next.keySet())
                    if(match(node.next.get(nextChar),word,index + 1))
                        return true;
                return false;
            }
        }
    }

## 五、Letcode键值映射——前缀开头的键的值的总和 ##

对应Letcode  667题  键值映射

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 4][]

代码实现：

class MapSum {
    
        private class Node{
            private int value;
            private TreeMap<Character,Node> next;
    
            public Node(int value){
                this.value = value;
                next = new TreeMap<>();
            }
    
            public Node(){
                this(0);
            }
        }
    
        private Node root;
        /** Initialize your data structure here. */
        public MapSum() {
            root = new Node();
        }
        
        public void insert(String word, int val) {
            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);
            }
            cur.value = val;
        }
        
        public int sum(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 0;
                cur = cur.next.get(c);
            }
           return sum(cur);
        }
    
        private int sum(Node node) {
            int res = node.value;
            for(char c : node.next.keySet())
                res += sum(node.next.get(c));
            return res;
        }
    }

[2_N]: https://www.99cankao.com/algebra/exponent2.php
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2018102815075524.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg==,size_27,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 1]: /images/20220503/126fc020dcfd4423ab406dce3deb1c9d.png
[211]: https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/description/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 2]: /images/20220503/33e94eebe20748b0a8a9c348648de1a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 3]: /images/20220503/8f4422b71d1e4b00bdef34be789e81bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 4]: /images/20220503/a02641f3e0b24b2e940a3f2589761f8d.png