CC++ & Algorithm

字典树（Trie）的概念与实现

较难3
语言版本：通用
概述：字典树是一种利用字符串公共前缀来高效存储和查询单词的树形数据结构，就像一本神奇的“单词速查手册”。

字典树（Trie）：让程序像查字典一样快速搜索单词

你有没有用过手机输入法的“联想”功能？当你输入“app”时，手机立刻弹出“apple”、“application”等候选词。这种神奇的功能背后，就藏着一种叫做**字典树（Trie）**的数据结构。

字典树是一种专门用来高效存储和查询字符串的树形数据结构。它的名字“Trie”来自英文单词“retrieval”（检索），读作“try”或者“tree”。就像一本神奇的“单词速查手册”，它利用字符串的公共前缀来减少查询时间，同时节省存储空间。

生活中的例子：查字典与自动补全

想象一下，你有一本超厚的英汉字典，里面有几十万个单词。你想查一下“apple”这个单词是否存在。如果从第一页翻到最后一页，那要花很长时间。但字典的编排方式很聪明：所有单词都按照字母顺序排列，而且相同开头的单词都聚集在一起。比如以“a”开头的单词都在前面，以“b”开头的在中间，等等。这样查单词就快多了。

字典树（Trie）正是模仿了这种思想。它把单词的每个字母作为一个节点，从根节点开始一层一层地走下去，就能拼出一个完整的单词。而且，所有共享相同前缀的单词会共用前面的节点，就像字典里以“app”开头的单词都会挤在“app”后面那一小片区域里一样。

下面是一个简单的字典树示意图，里面存储了三个单词：”cat”, “car”, “dog”。我们用节点来表示字母，用箭头表示路径。

        root
        /    \
       c      d
      /        \
     a          o
    / \          \
   t   r          g
   (end) (end)   (end)

在这个图中，root是根节点，不包含字母。从root出发，走左边可以到“c”，再走到“a”，然后分叉：一个走向“t”形成单词“cat”，另一个走向“r”形成单词“car”。右边同理得到“dog”。注意，单词“cat”和“car”共享了前缀“ca”。

字典树的原理与核心思想

字典树（Trie，读作“try”或者“tree”）又叫前缀树。它的核心就是利用字符串的公共前缀来减少查询时间，同时节省存储空间（相比于存一堆字符串的集合）。

节点结构

字典树的每个节点通常包含两部分信息：

  1. 子节点指针：指向下一个可能的字符。因为英语单词通常由26个小写字母组成，所以每个节点最多有26个子节点（可以用一个大小为26的数组或者哈希表来存储）。
  2. 结束标记：表示从根节点到当前节点的路径是否构成一个完整的单词。例如，在根节点->c->a->t的路径上，节点“t”的结束标记为true，而节点“a”的结束标记为false（除非“ca”也是一个单词，比如某些语境下）。

插入操作

每次插入一个单词时，我们从根节点开始，依次取出单词的每个字符。如果当前字符对应的子节点存在，就继续往下走；如果不存在，就创建一个新的节点，然后继续。最后，在单词末尾的节点上设置结束标记为true。

查找操作

与插入类似，沿着单词的字符走一遍。如果中途某个字符找不到对应的子节点，说明单词不存在；如果能走到最后，并且结束标记为true，说明单词存在。

前缀查询

除了查找完整单词，字典树还能支持前缀查询（也叫startsWith）：检查是否存在以某个前缀开头的单词。实现方法很简单：只需沿着前缀的字符走，如果某一步没有子节点，返回false；否则走到最后就返回true（不需要检查结束标记，因为只要前缀存在即可）。

优点和缺点

  • 优点：查询速度非常快，只与单词长度有关（O(L)，L为单词长度），与字典中单词数量无关。而如果使用哈希表或者集合，虽然平均也是O(1)，但可能会出现哈希冲突，而且无法支持前缀查询。字典树天生支持前缀查询。
  • 缺点：比较耗内存，因为每个节点都需要存储多个子节点指针（即使大部分是空指针）。不过可以通过压缩路径（Radix Tree）等方式优化，但这是后话了。

新手容易犯的错误

在学习字典树时，有一些常见的坑需要注意：

  1. 忘记标记结束：插入单词后，最后节点忘了设置isEnd = true，导致搜索时明明插入了单词却返回false。这是最常出的错误。
  2. 混淆路径节点和单词节点：例如插入了“app”和“apple”，路径上的节点“a”“p”“p”是共享的。要记住：只有标记了isEnd的节点才代表一个完整单词。“app”节点和“apple”节点是不同的（虽然“app”节点也是“apple”路径上的中间节点）。
  3. 没有分清根节点：根节点不存储任何字符，只是一个起点。初学者有时会错误地把根节点也当作一个字母。
  4. 字符集处理不当：如果单词中可能出现大写字母或数字，需要统一转换或增大数组大小。用数组时通常固定26个字母，但若遇到其他字符（如空格）就会越界。更灵活的做法是用哈希表（字典）存储子节点。
  5. 内存泄漏：在C++中，如果使用new动态分配节点，需要手动释放。虽然后面可能会讲智能指针，但新手容易忘记析构函数。

C++完整代码实现（带前缀查询和注释）

下面是一个简单的字典树实现，适用于26个小写字母。我们定义了节点结构体，包含一个子节点数组和结束标记。然后实现了插入、查找和前缀查询三个主要函数。

#include <iostream>
#include <cstring>
using namespace std;

// 字典树节点结构体
struct TrieNode {
    TrieNode* next[26];   // 26个小写字母的子节点指针
    bool isEnd;           // 标记该节点是否是某个单词的结尾

    // 构造函数：初始化所有子节点为nullptr，isEnd为false
    TrieNode() {
        for (int i = 0; i < 26; i++) {
            next[i] = nullptr;
        }
        isEnd = false;
    }
};

class Trie {
private:
    TrieNode* root;   // 根节点（不存储字符）

public:
    Trie() {
        root = new TrieNode();   // 创建根节点
    }

    // 析构函数：释放所有节点（防止内存泄漏）
    ~Trie() {
        deleteNode(root);
    }

    // 递归释放节点的辅助函数
    void deleteNode(TrieNode* node) {
        if (node == nullptr) return;
        for (int i = 0; i < 26; i++) {
            deleteNode(node->next[i]);   // 递归删除子节点
        }
        delete node;
    }

    // 插入一个单词
    void insert(string word) {
        TrieNode* cur = root;                // 从根节点开始
        for (char ch : word) {              // 遍历单词的每个字符
            int idx = ch - 'a';             // 计算字符对应的索引 (0~25)
            if (cur->next[idx] == nullptr) {// 如果对应的子节点不存在
                cur->next[idx] = new TrieNode();  // 创建新节点
            }
            cur = cur->next[idx];           // 移动到子节点
        }
        cur->isEnd = true;                  // 标记该节点为单词结尾
    }

    // 查找一个单词是否存在
    bool search(string word) {
        TrieNode* cur = root;               // 从根节点开始
        for (char ch : word) {             // 遍历单词的每个字符
            int idx = ch - 'a';
            if (cur->next[idx] == nullptr) {// 如果字符对应的路径不存在
                return false;               // 单词不存在
            }
            cur = cur->next[idx];           // 继续往下走
        }
        return cur->isEnd;                  // 返回是否到达一个完整的单词
    }

    // 判断是否存在以某个前缀开头的单词
    bool startsWith(string prefix) {
        TrieNode* cur = root;               // 从根节点开始
        for (char ch : prefix) {            // 遍历前缀的每个字符
            int idx = ch - 'a';
            if (cur->next[idx] == nullptr) {// 如果字符对应的路径不存在
                return false;               // 不存在该前缀
            }
            cur = cur->next[idx];           // 继续往下走
        }
        return true;                        // 前缀路径完整，返回true（不检查isEnd）
    }
};

int main() {
    Trie trie;
    trie.insert("cat");
    trie.insert("car");
    trie.insert("dog");

    cout << "查找 'cat': " << (trie.search("cat") ? "存在" : "不存在") << endl;   // 1
    cout << "查找 'ca': " << (trie.search("ca") ? "存在" : "不存在") << endl;     // 0
    cout << "查找 'dog': " << (trie.search("dog") ? "存在" : "不存在") << endl;   // 1

    cout << "前缀 'ca': " << (trie.startsWith("ca") ? "存在" : "不存在") << endl; // 1
    cout << "前缀 'do': " << (trie.startsWith("do") ? "存在" : "不存在") << endl; // 1
    cout << "前缀 'da': " << (trie.startsWith("da") ? "存在" : "不存在") << endl; // 0
    return 0;
}

Python完整代码实现（带前缀查询和注释）

Python中可以使用字典（dict）来灵活存储子节点，不需要固定26个位置，这样更通用。

class TrieNode:
    def __init__(self):
        # 使用字典存储子节点，键为字符，值为TrieNode对象
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()   # 根节点

    def insert(self, word: str) -> None:
        """插入一个单词"""
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = TrieNode()   # 如果字符不存在，创建新节点
            cur = cur.children[ch]             # 移动到子节点
        cur.is_end = True                      # 标记为单词结尾

    def search(self, word: str) -> bool:
        """查找单词是否存在"""
        cur = self.root
        for ch in word:
            if ch not in cur.children:         # 路径不存在
                return False
            cur = cur.children[ch]
        return cur.is_end                      # 必须是完整单词

    def startsWith(self, prefix: str) -> bool:
        """判断是否有以prefix开头的单词"""
        cur = self.root
        for ch in prefix:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return True

if __name__ == "__main__":
    trie = Trie()
    trie.insert("cat")
    trie.insert("car")
    trie.insert("dog")

    print("查找 'cat':", trie.search("cat"))      # True
    print("查找 'ca':", trie.search("ca"))        # False
    print("查找 'dog':", trie.search("dog"))      # True

    print("前缀 'ca':", trie.startsWith("ca"))    # True
    print("前缀 'do':", trie.startsWith("do"))    # True
    print("前缀 'da':", trie.startsWith("da"))    # False

总结要点

  1. 定义：字典树（Trie）是一种树形结构，每个节点代表一个字符，从根到叶子的路径组成一个字符串，共享前缀的字符串共用前面的节点。
  2. 基本操作：插入、查找和前缀查询都是O(L)时间复杂度，L为字符串长度。
  3. 存储结构：每个节点需要保存子节点指针（数组或哈希表）以及一个结束标记。
  4. 优点：前缀查询非常高效，适合实现自动补全、拼写检查、词频统计等。
  5. 缺点：当字符集较大时（如中文），每个节点存储大量指针会消耗内存。可以通过哈希表或压缩字典树来优化。

相关指引

字典树是很多高级字符串算法的基础，比如：

  • AC自动机：在字典树上添加失败指针，实现多模式串的快速匹配（例如在一篇文章中同时找出多个敏感词）。
  • 可持久化Trie：支持在历史版本中查询，常用于解决区间异或问题。
  • 压缩字典树（Radix Tree / Patricia Tree）：将连续的单链路径压缩成一个节点，大幅节省内存。

现在，你可以动手尝试自己实现一个支持单词删除的方法，或者统计字典中每个单词出现的次数。理解字典树的原理，将是你在字符串处理领域迈出的坚实一步。

例题精讲

1单选题

关于Trie树（字典树）的根节点，以下说法正确的是？

A根节点存储一个字符
B根节点通常不存储字符，只作为起点
C根节点存储所有单词的第一个字符
D根节点存储一个特殊标记
2判断题

在Trie树中，查找一个长度为L的单词是否存在于树中，时间复杂度为O(L)，与树中存储的单词总数无关。

3填空题
以下函数用于向Trie树中插入一个单词word。请补全代码。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def insert(root, word):
    node = root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = ___
        node = node.children[ch]
    node.is_end = True
4单选题

以下哪个不是Trie树的典型应用场景？

A搜索引擎中的自动补全
B拼写检查与单词纠正
C对大量字符串进行快速排序
D计算字符串的哈希值
5判断题

在Trie树中，如果每个节点使用固定大小的数组（例如26个指针）存储子节点，那么对于只包含少数单词但字符串长度较长的情况，可能会造成大量的空间浪费。