JavaScript 字典树的应用

概述

字典树（Trie），又称前缀树或键树，是一种用于快速查询字符串前缀的数据结构。它是一种多叉树，通常用于存储大量的字符串（但不仅限于字符串），以便进行快速检索。字典树的主要优势在于其高效的查找速度和插入操作。

字典树的基本概念

定义

字典树是一种树形数据结构，每个节点表示一个字符。根节点不包含任何字符，子节点包含的字符组成从根节点到该节点的路径上的字符串。通常，根节点到某个节点的路径表示一个单词或字符串的前缀。

节点结构

在 JavaScript 中，可以使用对象来表示字典树的节点。每个节点通常包含以下属性：

• children：表示当前节点的所有子节点，一般是一个对象，键是字符，值是对应的子节点。
• isEndOfWord：表示是否为一个完整单词的结束节点，通常为布尔值。

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

创建字典树

初始化字典树

创建一个字典树时，首先需要初始化一个根节点，根节点不包含任何字符。

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

插入单词

插入单词的过程是从根节点开始，逐个字符地检查是否存在对应的子节点。如果不存在，则创建一个新的子节点；如果存在，则继续沿着路径向下搜索，直到单词的所有字符都被处理完。最后，在最后一个字符对应的节点上标记 isEndOfWord 为 true。

// www.javascriptcn.com code example
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.isEndOfWord = true;
}

查找单词

查找单词的过程与插入过程类似，也是从根节点开始，逐个字符地检查是否存在对应的子节点。如果所有字符都存在且最后一个字符的 isEndOfWord 为 true，则说明单词存在于字典树中；否则，单词不存在。

// www.javascriptcn.com code example
search(word) {
    let node = this.root;

    for (let char of word) {
        if (!node.children[char]) {
            return false;
        }
        node = node.children[char];
    }

    return node.isEndOfWord;
}

搜索前缀

字典树的一个重要应用是可以高效地搜索具有相同前缀的所有单词。这可以通过遍历从根节点到指定前缀节点的所有路径实现。

// www.javascriptcn.com code example
startsWith(prefix) {
    let node = this.root;

    for (let char of prefix) {
        if (!node.children[char]) {
            return false;
        }
        node = node.children[char];
    }

    return true;
}

删除单词

删除单词的过程稍微复杂一些，因为我们需要确保不会意外删除共享相同前缀的其他单词。具体步骤如下：

1. 从根节点开始，逐个字符地检查是否存在对应的子节点。
2. 如果找到对应节点，则递归地删除该节点的子节点，直到遇到一个非空子节点或到达单词的末尾。
3. 如果该节点不是任何其他单词的前缀，则可以安全地删除该节点及其子节点。
4. 如果删除后该节点没有子节点且 isEndOfWord 为 false，则可以删除该节点。

// www.javascriptcn.com code example
remove(word, node = this.root, index = 0) {
    if (index === word.length) {
        // 如果单词的末尾节点，将 isEndOfWord 设为 false
        node.isEndOfWord = false;
        // 如果该节点没有子节点，可以安全地删除该节点
        return Object.keys(node.children).length === 0;
    }

    const char = word[index];

    if (!node.children[char]) {
        return false;
    }

    const shouldDeleteCurrentNode = this.remove(word, node.children[char], index + 1);

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

    return false;
}

实际应用示例

自动补全功能

自动补全功能是字典树的一种常见应用。通过在用户输入过程中不断搜索前缀，可以动态地提供可能的完成选项。

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

    const results = [];

    function search(node, path) {
        if (node.isEndOfWord) {
            results.push(path.join(''));
        }
        for (let char in node.children) {
            search(node.children[char], [...path, char]);
        }
    }

    search(node, prefix.split(''));

    return results;
}

拼写检查器

拼写检查器也可以利用字典树来提高效率。通过预先构建一个包含大量正确单词的字典树，可以在用户输入时快速判断单词是否正确。

// www.javascriptcn.com code example
spellCheck(word) {
    let node = this.root;

    for (let char of word) {
        if (!node.children[char]) {
            return false;
        }
        node = node.children[char];
    }

    return node.isEndOfWord;
}

总结

字典树是一种非常强大的数据结构，特别适合用于需要频繁搜索、插入和删除字符串的应用场景。通过合理地设计和使用字典树，可以显著提高这些操作的效率。以上介绍了字典树的基本概念、插入、查找、前缀搜索、删除以及实际应用示例等内容，希望对理解和使用字典树有所帮助。