第34课：字典树（Trie）

课程：数据结构与算法
模块：树结构
难度：中级
标签：Trie, 前缀, 自动补全

1. 学习目标

完成本课后，你将能够：

理解 Trie 的核心结构：解释字典树节点及其连接方式。
实现 Trie 的基本操作：编写插入（Insert）和精确查找（Search）函数。
掌握前缀查找：实现判断一个前缀是否存在，以及获取以某个前缀开头的所有单词的函数。
应用 Trie 解决实际问题：使用 Trie 实现一个简单的自动补全（Autocomplete）功能。

2. 核心概念

字典树（Trie），又被称为前缀树或单词查找树，是一种树形数据结构，用于高效地存储和检索字符串键。它就像一本实体字典的“目录树”：

从根节点（Root）开始，根不包含字符。
每个节点代表一个字符，从根到某个节点的路径连接起来，就构成一个字符串的前缀。
通常，我们用一个特殊标记（如布尔值 is_end）来标识路径到此节点时，是否完整构成了一个单词。

为什么使用 Trie？

查找速度快：在 Trie 中查找一个长度为 L 的字符串，时间复杂度为 O(L)，与字典中存储的单词总数无关。
前缀查询高效：这是 Trie 的杀手锏。它可以轻松地找到所有以某个前缀开头的单词，这在自动补全、拼写检查等场景中非常有用。

节点结构示例：一个 Trie 节点通常包含：

children：一个字典（哈希表），用于存储指向子节点的指针。键是字符，值是对应的子节点。
is_end：一个布尔值，标记从根到当前节点的路径是否是一个完整的单词。

class TrieNode:
    def __init__(self):
        self.children = {}  # 存储子节点，key: 字符, value: TrieNode
        self.is_end = False # 标记该节点是否是一个单词的结尾

3. 代码示例

下面是一个完整的、可运行的 Python 实现，包含了基本的插入、查找、前缀查找和自动补全功能。

class TrieNode:
    """Trie树的节点类"""
    def __init__(self):
        self.children = {}  # 存储子节点
        self.is_end = False # 标记是否为单词结尾

class Trie:
    """Trie树（字典树）类"""
    def __init__(self):
        """初始化根节点（根节点不存储字符）"""
        self.root = TrieNode()

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

    def search(self, word: str) -> bool:
        """精确查找一个单词是否存在"""
        node = self._find_node(word)
        # 不仅要找到路径，还要检查该节点是否标记为单词结尾
        return node is not None and node.is_end

    def starts_with(self, prefix: str) -> bool:
        """检查是否有任何单词以该前缀开头"""
        # 只需要找到路径即可，不关心is_end
        return self._find_node(prefix) is not None

    def _find_node(self, prefix: str) -> TrieNode:
        """查找前缀路径的最后一个节点"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def autocomplete(self, prefix: str) -> list:
        """返回所有以给定前缀开头的单词列表"""
        # 首先找到前缀对应的节点
        node = self._find_node(prefix)
        if node is None:
            return []
        
        # 从该节点开始，进行深度优先搜索（DFS）来收集所有单词
        results = []
        self._dfs(node, list(prefix), results) # 使用list(prefix)避免后续修改原字符串
        return results

    def _dfs(self, node: TrieNode, current_word: list, results: list):
        """深度优先搜索，收集单词"""
        # 如果当前节点标记为单词结束，则将当前路径构成的单词加入结果
        if node.is_end:
            results.append("".join(current_word))
        
        # 遍历当前节点的所有子节点
        for char, child_node in node.children.items():
            current_word.append(char) # 选择
            self._dfs(child_node, current_word, results) # 探索
            current_word.pop() # 撤销选择（回溯）

# --- 使用示例 ---
if __name__ == "__main__":
    trie = Trie()
    words = ["apple", "app", "apt", "bat", "ball", "band"]
    for word in words:
        trie.insert(word)

    print("搜索'app':", trie.search("app"))          # 输出: True
    print("搜索'ap':", trie.search("ap"))              # 输出: False (不是完整单词)
    print("检查前缀'ap':", trie.starts_with("ap"))    # 输出: True
    print("自动补全'app':", trie.autocomplete("app"))  # 输出: ['app', 'apple', 'apt']
    print("自动补全'ba':", trie.autocomplete("ba"))    # 输出: ['ball', 'band', 'bat']

4. 实践练习

练习 1：基础 - 实现删除功能 为 Trie 类实现一个 delete(word) 方法，从 Trie 中删除一个单词。删除后，Trie 应仅删除该单词的标识，但保留其他单词共享的节点。

要求：如果要删除的单词不存在，应静默处理，不报错。
提示：可以考虑使用递归或显式栈。你需要从最后一个字符的节点开始回溯，释放不再使用的节点（即没有子节点且不是其他单词结尾的节点）。

预期输出：

trie.delete("app")
print(trie.search("app"))       # 输出: False
print(trie.search("apple"))     # 输出: True (不应被删除)
print(trie.starts_with("app"))  # 输出: True (因为“apple”还在)

练习 2：进阶 - 带权重的自动补全 在许多真实应用中，自动补全的单词会根据使用频率或关联度进行排序。修改你的 Trie 类。

要求：
1. 为每个单词添加一个整数权重（weight），权重越高的单词，在自动补全结果中排名越靠前。
2. 修改 insert 方法，使其可以接受一个可选的权重参数（如 insert(word, weight=1)）。如果同一个单词被插入多次，取最大的权重。
3. 修改 autocomplete 方法，使其返回一个按权重从高到低排序的单词列表。
提示：你需要在 TrieNode 中增加一个 weight 属性，并在 _dfs 收集结果时连同权重一起收集，最后对结果列表进行排序。

练习 3：挑战 - 实现一个简单的命令行自动补全器 基于你改进的带权重的 Trie 类，创建一个简单的交互式命令行程序。

要求：
1. 程序启动时，从一个预定义的单词列表（或用户输入）初始化一个带权重的 Trie。
2. 提示用户输入一个前缀。
3. 程序使用 autocomplete 函数，并以“:”分隔的格式显示前3个最相关的补全建议。例如，输入 “ap”，输出可能为 “建议: apple:100, app:90, apt:80”。
4. 允许用户循环输入，直到输入“quit”退出。

5. 常见错误

忘记标记单词结束：在插入单词后，忘记设置 node.is_end = True，导致 search 功能失效。这是最普遍的错误。
查找前缀时错误地检查 is_end：在实现 starts_with 时，只需检查路径是否存在，不应要求路径末端的节点是单词结尾。错误地检查 is_end 会导致像 starts_with("app") 返回 False，尽管“apple”存在。
递归/DFS 实现中的状态修改：在自动补全的深度优先搜索中，如果使用同一个列表对象来构建单词，务必注意回溯（pop()）。忘记回溯会导致结果错误（如 ['a', 'p', 'p', 'p', 'l', 'e'] 而不是 ['a', 'p', 'p', 'l', 'e']）。
混淆节点和字符：记住，节点本身通常不存储字符，字符存储在父节点的 children 字典的键（key）中。根节点是特殊的，它不代表任何字符。
不考虑空字符串：在实现中，有时需要单独处理空字符串的插入和查找，这取决于你的设计是否允许。

6. 小结

Trie 是什么：一种专门用于处理字符串（特别是前缀问题）的树形数据结构。它通过共享公共前缀来高效存储和查找字符串。
核心操作：
- 插入：从根开始，按字符逐层创建或遍历节点，最后标记结束。
- 精确查找：从根开始，按字符逐层遍历，最终需验证结束标记。
- 前缀查找：从根开始，按字符逐层遍历，只要路径存在即为真。
- 自动补全：先通过前缀查找定位到中间节点，然后从该节点开始进行深度优先搜索（DFS）来收集所有以该前缀开头的完整单词。
时间复杂度：插入、查找和前缀查找的时间复杂度均为 O(m)，其中 m 是键（字符串）的长度。这使得它在处理大量字符串和频繁前缀查询时性能卓越。
典型应用：自动补全、拼写检查、IP 路由（最长前缀匹配）、电话号码簿等。

掌握了字典树，你就拥有了处理一类重要问题的强大工具。下一课，我们将学习另一种强大的树结构——线段树，它用于高效解决区间查询问题。

练习编辑器

rust