JavaScript 字典树 (Trie)

什么是字典树

字典树（Trie），又称前缀树或键树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值。

字典树的应用场景

• 搜索引擎：当用户输入关键词时，搜索引擎会提供相关的搜索建议。这些搜索建议通常基于用户之前输入的内容。通过使用字典树，搜索引擎可以快速地找到相关的搜索建议。
• 自动补全：字典树是实现自动补全功能的一种常见方法。用户在输入框中输入字符时，程序可以通过查询字典树来提供可能的单词列表。
• 拼写检查器：通过将词典中的所有单词插入到字典树中，拼写检查器可以快速地识别输入文本中的拼写错误。
• IP路由表：路由器使用字典树来存储IP地址前缀，以便快速转发数据包。

字典树的基本结构

节点设计

字典树的每个节点都包含以下属性：

• children：子节点的集合，可以是一个对象或哈希表，键为字符，值为子节点。
• value：节点的值，如果该节点表示一个完整的单词，则存储单词的含义；如果该节点不表示完整的单词，则值为空。
• isEndOfWord：布尔值，标记该节点是否为一个单词的结束节点。

class TrieNode {
    constructor() {
        this.children = {};
        this.value = null;
        this.isEndOfWord = false;
    }
}

根节点

根节点是字典树的起始点，其 children 属性用于存储所有可能的字符作为子节点。

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

字典树的操作

插入操作

向字典树中插入单词时，从根节点开始，逐个字符地遍历并创建相应的子节点，直到单词的所有字符都被处理完。最后，设置最后一个节点的 isEndOfWord 属性为 true，以标识这是一个完整的单词。

// www.javascriptcn.com code example
insert(word, value) {
    let node = this.root;
    for (let char of word) {
        if (!node.children[char]) {
            node.children[char] = new TrieNode();
        }
        node = node.children[char];
    }
    node.value = value;
    node.isEndOfWord = true;
}

查找操作

查找操作是从根节点开始，逐个字符地遍历字典树，直到单词的最后一个字符。如果找到完整的单词，则返回其 value，否则返回 null。

// www.javascriptcn.com code example
search(word) {
    let node = this.root;
    for (let char of word) {
        if (!node.children[char]) {
            return null;
        }
        node = node.children[char];
    }
    return node.isEndOfWord ? node.value : null;
}

删除操作

删除操作较为复杂，需要考虑多种情况：

1. 如果单词不存在于字典树中，直接返回。
2. 如果单词存在，但不是最后一个节点，只需将 isEndOfWord 属性设为 false。
3. 如果单词是最后一个节点，需要递归地删除空节点，直到遇到一个非空节点或者根节点。

// www.javascriptcn.com code example
delete(word) {
    const _delete = (node, index) => {
        if (index === word.length) {
            if (!node.isEndOfWord) return false;
            node.isEndOfWord = false;
            return Object.keys(node.children).length === 0;
        }
        const char = word[index];
        const shouldDeleteCurrentNode = _delete(node.children[char], index + 1);

        if (shouldDeleteCurrentNode) {
            delete node.children[char];
            return Object.keys(node.children).length === 0;
        }

        return false;
    };

    _delete(this.root, 0);
}

前缀匹配

前缀匹配是指找出所有以指定前缀开头的单词。这可以通过从根节点开始，逐个字符地遍历字典树来实现。

// www.javascriptcn.com code example
startsWith(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) {
            return [];
        }
        node = node.children[char];
    }
    return this._collectWordsFromNode(node);
}

_collectWordsFromNode(node) {
    let words = [];
    if (node.isEndOfWord) {
        words.push(node.value);
    }
    for (let char in node.children) {
        words = words.concat(this._collectWordsFromNode(node.children[char]));
    }
    return words;
}

总结

字典树是一种非常强大的数据结构，适用于各种需要高效前缀匹配和字符串搜索的场景。通过合理设计和实现字典树的插入、查找、删除和前缀匹配等操作，可以有效地提高应用程序的性能和用户体验。