字典树

基本概念

字典树（Trie），又称前缀树或单词查找树，是一种用于高效存储和检索字符串集合中键值的数据结构。它的每个节点代表一个字符，从根节点到某个节点路径上的字符组成一个字符串。字典树广泛应用于字符串前缀匹配、自动补全、单词计数等场景，能够在 O(L) 时间内完成插入、查找和前缀查询（L 为字符串长度）

数据结构的三要素

逻辑结构：树形结构，每个节点包含若干指向子节点的指针（通常用字典或数组实现），根节点为空字符，每个节点可以标记是否为一个单词的结尾。
存储结构：
- 链式存储：每个节点维护一个字典（如 Python 的 dict）或固定大小的数组（如 26 个字母），存储指向子节点的引用。
- 字典实现适用于字符集较大的场景（如 Unicode），数组实现适用于小字符集（如英文小写字母），访问速度更快但空间固定。
数据的运算：
- 插入：从根节点开始，依次将字符串的每个字符作为键创建子节点，最后标记节点为单词结尾。
- 查找：沿着字符路径遍历，若路径存在且最终节点被标记为单词结尾，则查找成功。
- 前缀查询：给定前缀，检查是否存在以该前缀开头的单词，只需路径存在即可（无需结尾标记）。
- 删除（可选）：需注意释放无用的节点，通常递归处理。

算法步骤

插入单词：
- 设当前节点为根节点。
- 对单词中的每个字符 c：
  - 如果当前节点的子节点中不存在 c，则新建一个节点。
  - 移动到子节点。
- 最后一个字符对应的节点标记为单词结尾（is_end = True）。
查找单词：
- 从根节点开始，依次遍历单词中的字符。
- 若某个字符在当前节点的子节点中不存在，则返回 False。
- 到达最后一个字符后，检查该节点的 is_end 标记，若为 True 则返回 True，否则返回 False（说明该前缀存在但不是完整单词）。
前缀查询：
- 类似查找，但只需要路径存在，不检查结尾标记。若路径存在，则返回 True，否则返回 False。

内部实现

class TrieNode:
    def __init__(self):
        self.children = dict()   # 子节点映射
        self.is_end = False      # 是否为单词结尾

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        current = self.root
        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.is_end = True

    def search(self, word: str) -> bool:
        current = self.root
        for char in word:
            if char not in current.children:
                return False
            current = current.children[char]
        return current.is_end

    def startsWith(self, prefix: str) -> bool:
        current = self.root
        for char in prefix:
            if char not in current.children:
                return False
            current = current.children[char]
        return True

复杂度分析

操作	时间复杂度	空间复杂度	说明
插入	O(L)	O(L)	L 为单词长度，每次插入可能新增节点
查找	O(L)	O(1)	沿路径遍历，不额外占用空间
前缀查询	O(L)	O(1)	同查找
空间总体	-	O(N·L)	N 为单词总数，L 为平均长度，但节点数通常小于 N·L，因为有公共前缀

说明：

时间复杂度与单词长度成正比，与单词总数无关，这是字典树的主要优势。
空间复杂度取决于字符集大小和单词的共享前缀程度。对于大量共享前缀的单词集（如词典），空间利用较为高效。

应用场景

字符串检索：实现敏感词过滤、拼写检查、单词自动补全（如搜索引擎搜索框提示）。
最长公共前缀：快速找出多个字符串的最长公共前缀。
词频统计：在节点中增加计数，统计单词或前缀出现次数。
实现其他数据结构：如 AC 自动机（Aho-Corasick）在多模式匹配中基于 Trie 构建失败指针，实现高效匹配；基数树（Radix Tree）压缩存储空间。
实际系统应用：
- Redis 的 Rax 结构（基数树）用于存储键空间；Linux 内核中的 radix tree 用于管理页面缓存。
- 搜索引擎（如 Elasticsearch）利用前缀树实现自动补全和搜索建议。
- 编译器（如词法分析器）可能使用 Trie 来识别关键字。

总结

字典树是一种以空间换时间的字符串存储结构，通过共享前缀极大提升了字符串插入和查找的效率。它特别适合处理大量具有公共前缀的字符串集合，广泛应用于前缀匹配、自动补全、词频统计等场景。尽管空间开销可能较大，但通过压缩节点（如基数树）可以进一步优化。理解和掌握 Trie 是学习更高级字符串处理算法（如 AC 自动机）的基础。