字典树（Trie）#

字典树（Trie）是一种树形数据结构，通过公共前缀来组织字符串集合。这种结构能有效节省存储空间，并使自动补全、拼写检查等前缀匹配操作变得异常高效。

字典树的原理#

字典树示例如图所示（图源：OI Wiki），字典树的核心特点如下：

节点不存储字符：字符通常存储在边上，或者由节点在父节点中的位置决定。
共享前缀：路径从根节点到某个节点表示一个字符串。例如，路径 c -> a -> a 表示字符串 "caa"，而 "caa" 和 "cab"共享了前缀 "ca"。
标记结尾：并非所有节点都代表字符串的终点，通常需要一个布尔值（如 is_end_of_word）来标记该节点是否构成了一个完整的单词。

字典树的实现#

字典树的节点数据结构#

字典树的节点一般包含以下几个部分：

children：一个字典或数组，用于存储子节点，key为字符，value为对应的子节点。
is_end_of_word：一个布尔值，表示当前节点是否是一个完整字符串的结尾。
data：可选额外的数据字段，可以存储与字符串相关的信息，例如动态规划中的状态值。

1
struct TrieNode {
2
    std::unordered_map<char, TrieNode*> children; // 存储子节点
3
    bool is_end_of_word; // 是否是一个完整字符串的结尾
4
    int data; // 额外的数据字段
5

6
    TrieNode() : is_end_of_word(false), data(0) {}
7
};

字典树的插入操作#

插入一个字符串到字典树中，首先从根节点开始，依次检查字符串的每个字符。如果当前字符在子节点中不存在，则创建一个新的节点。最后一个字符处理完后，将最后一个节点的 is_end_of_word 设置为 true，表示这是一个完整字符串的结尾。

TIP
根节点通常不存储任何字符，它只是一个起点。它的下一个节点才存储第一个字符。这样设计可以简化插入和查询操作。

1
struct Trie {
2
    TrieNode* root;
3

4
    Trie() {
5
        root = new TrieNode();
6
    }
7

8
    void insert(const std::string& word) {
9
        TrieNode* current = root;
10
        for (char c : word) {
11
            if (current->children.find(c) == current->children.end()) {
12
                current->children[c] = new TrieNode();
13
            }
14
            current = current->children[c];
15
        }
16
        current->is_end_of_word = true; // 标记字符串结尾
17
    }
18
};

字典树的查询操作#

查询一个字符串是否存在于字典树中，首先从根节点开始，依次检查字符串的每个字符。如果当前字符在子节点中不存在，则说明字符串不存在于字典树中。如果所有字符都存在，并且最后一个节点的 is_end_of_word 为 true，则说明字符串存在于字典树中。

1
struct Trie {
2
    \\...（前略）
3
    bool search(const std::string& word) {
4
        TrieNode* current = root;
5
        for (char c : word) {
6
            if (current->children.find(c) == current->children.end()) {
7
                return false; // 字符不存在，字符串不存在
8
            }
9
            current = current->children[c];
10
        }
11
        return current->is_end_of_word; // 检查是否是完整字符串的结尾
12
    }
13
}

字典树的删除操作#

删除一个字符串从字典树中，首先需要检查字符串是否存在于字典树中。如果存在，则需要沿着路径删除对应的节点。删除操作需要注意，如果一个节点的子节点不为空，则不能删除该节点，因为它可能是其他字符串的前缀。

1
struct Trie {
2
    \\...（前略）
3
    bool remove(const std::string& word) {
4
        return remove_helper(root, word, 0);
5
    }
6
private:
7
    //index：当前处理字符串的第index个字符
8
    //返回值：是否需要删除当前节点
9
    bool remove_helper(TrieNode* current, const std::string& word, int index) {
10
        if (index == word.size()) {
11
            if (!current->is_end_of_word) {
12
                return false; // 字符串不存在
13
            }
14
            current->is_end_of_word = false; // 取消字符串结尾标记
15
            return current->children.empty(); // 如果没有子节点，可以删除当前节点
16
        }
17

18
        char c = word[index];
19
        if (current->children.find(c) == current->children.end()) {
20
            return false; // 字符不存在，字符串不存在
21
        }
22

23
        bool should_delete_child = remove_helper(current->children[c], word, index + 1);
24
        if (should_delete_child) {
25
            delete current->children[c]; // 删除子节点
26
            current->children.erase(c); // 从子节点中移除
27
            return current->children.empty() && !current->is_end_of_word; // 如果当前节点没有子节点且不是字符串结尾，可以删除当前节点
28
        }
29

30
        return false; // 不需要删除当前节点
31
    }
32
}

字典树的合并#

暂时没写到这种题目，后续再补充。

字典树的应用#

字典树在许多应用场景中非常有用，以下是一些常见的应用：

自动补全：字典树可以用于实现自动补全功能。当用户输入一个前缀时，字典树可以快速找到所有以该前缀开头的字符串，从而提供建议。
拼写检查：字典树可以用于实现拼写检查功能。当用户输入一个单词时，字典树可以快速检查该单词是否存在于字典树中，从而判断拼写是否正确。
前缀匹配：字典树可以用于实现前缀匹配功能。当用户输入一个前缀时，字典树可以快速找到所有以该前缀开头的字符串，从而提供相关信息。
字符串统计：字典树可以用于统计字符串集合中的字符串数量。例如，可以在每个节点中维护一个计数器，记录以该节点为前缀的字符串数量，从而快速统计以某个前缀开头的字符串数量。
字符串排序：字典树可以用于对字符串集合进行排序。通过深度优先搜索字典树，可以按照字典序输出所有字符串，从而实现字符串排序功能。