Trie（前缀树）简介

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

Trie树的关键特性：

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

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

时间复杂度：

1. 插入: O(l) (l = 单词长度)
2. 查找: O(l)
3. 前缀查找: O(l)
4. 删除: O(l)

Trie树的应用场景：

1. 自动补全系统 (例如搜索框、文本编辑器)
2. 拼写检查器
3. IP路由 (最长前缀匹配)
4. 文字游戏 (例如，Boggle)
5. DNA序列匹配