2020.9.28 树【前缀树篇】

[SampsonKY]

前缀树

定义

​ 前缀树又称单词查找树，字典树，Trie 树，是一种树形结构，是哈希树的一个变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

性质

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

操作

前缀树的主要操作为插入，查找，删除（删除操作很少见）

源码实现

/**
 * Initialize your data structure here.
 */
class TreeNode {
    constructor(){
        this.END = false
        this.children = new Array(26)
    }
    containKey(letter){
        return this.children[letter.charCodeAt()-97] !== undefined
    }
    getCh(letter){
        return this.children[letter.charCodeAt()-97]
    }
    putCh(letter, TrieNode){
        this.children[letter.charCodeAt()-97] = TrieNode
    }
    setEnd(){
        this.END = true
    }
    isEnd(){
        return this.END
    }
}

let root = null

var Trie = function() {
    root = new TreeNode()
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let cur = root
    for(let i=0; i<word.length; i++){
        if(!cur.containKey(word[i])){
            cur.putCh(word[i], new TreeNode())
        }
        cur = cur.getCh(word[i])
    }
    cur.setEnd()
};

let SearchPrefix = function(word){
    let cur = root
    for(let i=0; i<word.length; i++){
        if(cur.containKey(word[i])) cur = cur.getCh(word[i])
        else return null
    }
    return cur
}

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let cur = SearchPrefix(word)
    return cur !== null && cur.isEnd()
};

/**
 * Returns if there is any word in the trie that starts with the given prefix. 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    return SearchPrefix(prefix) !== null
};

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

leetcode题目

• No.208 实现 Trie

• No.677 键值映射