Trie ——前缀树、字典树

逃离我推掉我的手 2023-07-10 13:00 21阅读 0赞

### 说在前面： ###

> `Map`映射数据结构和`Trie`的异同：  
> 相同：都能够根据`key`进行映射得到对应的值。  
> 不同：  
> ① `Trie`中查询/添加的算法复杂度为`O(len)`，即插入/查询的字符串的长度，而`Map`查询/添加的算法复杂度为`O(logn)`，n为输入的查询元素个数。  
> ② `Trie`是用多叉树实现的，而`Map`一般是用二叉树实现的。

## `Trie`：专门为了处理（存储/查询）字符串而设计的 ##

>  *  `Trie`是以时间换空间的，提高了搜索效率但是却浪费了空间
>  *  改良数据结构：① 压缩字典树 ② 三分搜索树

`Trie`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70]  
`压缩字典树`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70 1]  
`三分字典树`：牺牲了一定的时间，但是节省了空间  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70 3]

#### 1. 应用场景： ####

###### ① 子串查询 ######

###### ② 文件压缩（文件实际上是由很长的字符串组成的，故文件压缩是对很长的字符串进行压缩的） ######

###### ③ 模式匹配（eg:正则表达式的引擎） ######

###### ④ DNA(DNA本身就是一个超长的字符串) ######

#### 2. 设计`Trie` ####

> 由于`Trie`是一棵多叉树，则在其每个节点的设计中需要保存多个下一个结点的位置，故需要通过`Map`，即映射的数据结构进行存储下一堆结点的位置，映射数据结构的每一个元素的`key`即为下一个结点对应的标识，而`value`则是下一个结点的位置

##### 下面实现中`Trie`中保存的是一个个单词，故在设计`Trie`时需要给每个节点添加一个`isWord`标识，来判断当前结点以及其祖父能否组成一个单词。 #####

class NodeEle{
        isWords:boolean = false;;
        next = new Map();
    }
    class Trie{
        root:NodeEle;
        size:number;
        constructor(){
            this.root = new NodeEle();
            this.size = 0;
        }
    }

#### 3. `Trie`的相关方法 ####

##### ① `add` #####

add(word:string):void{ 
            let nowNode = this.root;
            for(let i=0;i<word.length;i++){ 
                let c = word.charAt(i);
                let newNode = new NodeEle();
                if(!nowNode.next.get(c)){ 
                    nowNode.next.set(c,newNode);
                }
                nowNode = nowNode.next.get(c);
            }
            if(!nowNode.isWords){ 
                nowNode.isWords = true;
                this.size++;
            }
        }

##### ② `find` #####

find(word:string):boolean{ 
            let newNode = this.root;
            for(let i=0;i<word.length;i++){ 
                let c = word.charAt(i);
                if(!newNode.next.get(c)){ 
                    return false;
                }
                newNode = newNode.next.get(c);
            }
            return newNode.isWords;//有可能像panda这样的单词，如果查找单词为pan，而n未被标识为单词（即查找到的是panda的前缀），则返回false
        }

##### ③ `isPrefix` #####

isPrefix(prefix:string):boolean{ 
            let newNode = this.root;
            for(let i=0;i<prefix.length;i++){ 
                let c = prefix.charAt(i);
                if(!newNode.next.get(c)){ 
                    return false;
                }
                newNode = newNode.next.get(c);
            }
            return true;
        }

##### ④ `match` #####

match = function(nodeEle,matchExe,index){ 
        if(matchExe.length-1==index){ 
            return nodeEle.isWords;
        }
        let c = matchExe.charAt(index);
        if(c!="."){ 
            if(nodeEle.next.get(c)!=null){ 
               return this.match(nodeEle.next.get(c),matchExe,index+1);
            }
            return false;
        }
        //如果为. 则要遍历当前结点的所有下一个结点
        for(let val of nodeEle.next.values()){ 
            if(this.match(val,matchExe,index+1)){ 
                return true;
            }
        }
        return false;
    }

#### 3. `leetCode`相关题目 ####

##### ① 键值映射 #####

> 实现一个 MapSum 类里的两个方法，insert 和 sum
> 
>  *  对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。
>  *  对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。

###### 示例 ######

//示例
    输入: insert("apple", 3), 输出: Null
    输入: sum("ap"), 输出: 3
    输入: insert("app", 2), 输出: Null
    输入: sum("ap"), 输出: 5

###### 实现 ######

/** * Initialize your data structure here. */
    class NodeEle { 
        constructor(val) { 
            this.value=val?val:0;
            this.next = new Map();
        }
        ;
    }
    var MapSum = function() { 
        this.root = new NodeEle();
    };
    
    /** * @param {string} key * @param {number} val * @return {void} */
    MapSum.prototype.insert = function(word, val) { 
        let nowNode = this.root;
            for (let i = 0; i < word.length; i++) { 
                let c = word.charAt(i);
                if (!nowNode.next.get(c)) { 
                    nowNode.next.set(c, new NodeEle());
                }
                nowNode = nowNode.next.get(c);
            }
            nowNode.value = val;
    };
    
    /** * @param {string} prefix * @return {number} */
    MapSum.prototype.sum = function(prefix) { 
        let newNode = this.root;
        for(let i=0;i<prefix.length;i++){ 
            let c = prefix.charAt(i);
            if(newNode.next.get(c)==null){ 
                return 0;
            }
            newNode = newNode.next.get(c);
        }
        return this.mapSum(newNode.value,newNode);
    };
    
    MapSum.prototype.mapSum = function(sum,newNode){ 
        for(let val of newNode.next.values()){ 
            sum += val.value;
            this.mapSum(sum,val);
        }
        return sum;
    }
    /** * Your MapSum object will be instantiated and called as such: * var obj = new MapSum() * obj.insert(key,val) * var param_2 = obj.sum(prefix) */
    var obj = new MapSum()
    obj.insert("apple",3)
    obj.insert("app",5)
    var param_2 = obj.sum("ap")
    console.log(param_2)

###### ② 添加与搜索单词 - 数据结构设计 ######

> 设计一个支持`addWord(word)`和`search(word)`操作的数据结构：
> 
>  *  `search(word)` 可以搜索文字或正则表达式字符串，字符串只包含字母 `.`或`a-z`。`.` 可以表示任何一个字母。

###### 示例 ######

addWord("bad")
    addWord("dad")
    addWord("mad")
    search("pad") -> false
    search("bad") -> true
    search(".ad") -> true
    search("b..") -> true

###### 实现 ######

/** * Initialize your data structure here. */
        class NodeEle { 
            constructor() { 
                this.isWords = false;
                this.next = new Map();
            }
            ;
        }
        var WordDictionary = function() { 
            this.root = new NodeEle();
        };
    
        /** * Adds a word into the data structure. * @param {string} word * @return {void} */
        WordDictionary.prototype.addWord = function(word) { 
            let nowNode = this.root;
            for (let i = 0; i < word.length; i++) { 
                let c = word.charAt(i);
                let newNode = new NodeEle();
                if (!nowNode.next.get(c)) { 
                    nowNode.next.set(c, newNode);
                }
                nowNode = nowNode.next.get(c);
            }
            if (!nowNode.isWords) { 
                nowNode.isWords = true;
            }
            console.log(nowNode)
        };
    
        /** * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. * @param {string} word * @return {boolean} */
        WordDictionary.prototype.search = function(word) { 
           return this.match(this.root,word,0);
        };
    
        WordDictionary.prototype.match = function(nodeEle,matchExe,index){ 
            console.log(nodeEle)
            if(matchExe.length==index){ 
                return nodeEle.isWords;
            }
            let c = matchExe.charAt(index);
            if(c!="."){ 
                if(nodeEle.next.get(c)!=null){ 
                    return this.match(nodeEle.next.get(c),matchExe,index+1);
                }
                return false;
            }
            for(let val of nodeEle.next.values()){ 
                if(this.match(val,matchExe,index+1)){ 
                    return true;
                }
            }
            return false;
        }
        /** * Your WordDictionary object will be instantiated and called as such: * var obj = new WordDictionary() * obj.addWord(word) * var param_2 = obj.search(word) */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020030221031077.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020030221212833.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200302212207254.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200302212236693.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMxNDg0Ng==,size_16,color_FFFFFF,t_70