Trie（前缀树）简介-js教程-PHP中文网

Trie（前缀树）简介

碧海醫心

发布： 2025-01-15 08:01:50

原创

583人浏览过

trie（前缀树）简介

Trie树，也称前缀树，是一种用于高效存储和检索字符串的数据结构，广泛应用于自动补全、拼写检查和IP路由等场景。

Trie树的关键特性：

节点: 每个节点代表一个字符。
根节点: 根节点为空，作为树的起始点。
子节点: 每个节点可拥有多个子节点，数量取决于字符集大小（例如，英文字母为26个）。
单词结束标记: 特定节点标记，指示该节点代表一个完整单词的结尾。

基本Trie树操作：

1. 插入单词:

插入新单词需要遍历Trie树，对于不存在的字符，创建新的节点。

2. 查找单词:

查找单词通过遍历Trie树，检查单词是否存在。

3. 前缀查找:

检查Trie树中是否存在以特定前缀开头的单词。

JavaScript实现基本Trie树：

class TrieNode {
    constructor() {
        this.children = {}; // 存储子节点
        this.isWordEnd = false; // 标记单词结尾
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    // 插入单词
    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isWordEnd = true; // 标记单词结尾
    }

    // 查找单词
    search(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return node.isWordEnd;
    }

    // 检查是否存在以指定前缀开头的单词
    startsWith(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return true;
    }
}

// 示例用法
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));   // true
console.log(trie.search("app"));     // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app"));     // true

登录后复制

高级Trie树操作：

1. 删除单词:

删除单词需要递归方法，删除不再需要的节点。

delete(word, node = this.root, depth = 0) {
    if (depth === word.length) {
        if (!node.isWordEnd) return false; // 单词不存在
        node.isWordEnd = false;
        return Object.keys(node.children).length === 0; // 检查节点是否有子节点
    }

    const char = word[depth];
    if (!node.children[char]) return false;

    const shouldDeleteChild = this.delete(word, node.children[char], depth + 1);

    if (shouldDeleteChild) {
        delete node.children[char];
        return Object.keys(node.children).length === 0 && !node.isWordEnd;
    }

    return false;
}

登录后复制

2. 统计以指定前缀开头的单词数量:

计算有多少单词以给定前缀开头。

countWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return 0;
        node = node.children[char];
    }
    return this._countWords(node);
}

_countWords(node) {
    let count = node.isWordEnd ? 1 : 0;
    for (let char in node.children) {
        count += this._countWords(node.children[char]);
    }
    return count;
}

登录后复制

3. 自动补全建议:

给定前缀，返回所有以该前缀开头的单词。

getWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return [];
        node = node.children[char];
    }
    return this._collectWords(node, prefix);
}

_collectWords(node, prefix) {
    let results = [];
    if (node.isWordEnd) results.push(prefix);

    for (let char in node.children) {
        results = results.concat(this._collectWords(node.children[char], prefix + char));
    }

    return results;
}

登录后复制