Trie树（字典树）的原理与实现

一、知识点描述
Trie树（发音同"try"），又称字典树或前缀树，是一种专门用于处理字符串集合的高效树形数据结构。它的核心思想是利用字符串的公共前缀来减少查询时间，常用于搜索引擎的自动补全、拼写检查、IP路由表等场景。Trie树的特点是：

• 根节点不包含字符，除根节点外每个节点只包含一个字符
• 从根节点到某一节点的路径上经过的字符连接起来，即为该节点对应的字符串
• 每个节点的所有子节点包含的字符都不相同

二、Trie树的基本结构

1. 节点结构设计
   每个Trie节点包含两个核心部分：

• 子节点指针数组（或映射）：存储指向下一个字符的指针
• 结束标志：标记从根节点到当前节点的路径是否构成一个完整单词

以小写字母组成的单词为例，节点可以这样定义：

class TrieNode:
    def __init__(self):
        self.children = {}  # 字符到子节点的映射
        self.is_end = False  # 标记是否为单词结尾

三、Trie树的基本操作

1. 插入操作（逐字符构建）
   步骤：

• 从根节点开始
• 遍历待插入单词的每个字符：
  • 如果当前字符存在于当前节点的子节点中，移动到对应子节点
  • 如果不存在，创建新节点并添加到当前节点的子节点中
• 处理完所有字符后，在最后一个节点标记为单词结尾

示例：插入"cat"

根节点 → 检查'c'：不存在 → 创建c节点
c节点 → 检查'a'：不存在 → 创建a节点  
a节点 → 检查't'：不存在 → 创建t节点
t节点 → 标记is_end=True

2. 搜索操作（精确匹配）
   步骤：

• 从根节点开始
• 遍历待搜索单词的每个字符：
  • 如果当前字符不在子节点中，返回False
  • 否则移动到对应子节点
• 检查最终节点的is_end标志，为True才表示单词存在

3. 前缀搜索操作
   步骤与搜索类似，但不需要检查is_end标志，只要能够遍历完所有前缀字符就说明存在该前缀

四、Trie树的实现详解

完整代码实现：

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        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.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
    
    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

五、Trie树的复杂度分析

1. 时间复杂度

• 插入：O(L)，其中L为单词长度
• 搜索：O(L)
• 前缀搜索：O(L)
  所有操作的时间复杂度都只与单词长度相关，与字典中单词数量无关

2. 空间复杂度

• 最坏情况：O(N×L)，其中N为单词数量，L为平均单词长度
• 实际应用中由于前缀共享，空间消耗通常优于理论最坏情况

六、Trie树的优化变种

1. 压缩Trie树
   通过合并只有一个子节点的节点来减少空间占用

2. 双数组Trie
   使用两个数组base和check来表示状态转移，节省内存空间

3. 三数组Trie
   在双数组基础上增加tail数组处理后缀，进一步优化

七、Trie树的应用场景

1. 自动补全系统
   输入前缀时快速找出所有以该前缀开头的单词

2. 拼写检查
   快速判断单词是否存在于字典中

3. IP路由查找
   最长前缀匹配，用于路由器转发决策

4. 单词游戏
   如Boggle等文字游戏中的单词验证

Trie树通过空间换时间的策略，在字符串处理场景中提供了高效的查询性能，特别适合前缀相关的操作。