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

题目描述
Trie树（又称字典树、前缀树）是一种专门用于处理字符串集合的高效树形数据结构。它的核心思想是利用字符串的公共前缀来减少查询时间，典型应用包括搜索引擎的自动补全、拼写检查、IP路由表等。面试中常考察Trie的原理、基本操作实现及复杂度分析。

1. Trie树的基本概念

• 节点结构：每个节点包含两个关键部分：
  • 子节点指针数组（或映射）：用于存储当前字符到下一级节点的引用。例如，若仅支持小写字母，则数组长度为26。
  • 结束标志（boolean类型）：标记从根节点到当前节点的路径是否构成一个完整单词。
• 根节点：不存储字符，作为所有单词的起始点。例如，插入单词"cat"时，路径为：根→c→a→t（在't'节点标记结束）。

2. Trie树的操作步骤详解
（1）插入操作
目标：将单词逐字符插入Trie，确保公共前缀共享路径。
步骤：

1. 从根节点开始，遍历单词的每个字符。
2. 若当前字符对应的子节点存在，则移动到该子节点。
3. 若子节点不存在，则新建节点并链接到当前节点的指针数组。
4. 处理完最后一个字符后，在该节点设置结束标志（如isEnd=true）。

示例：插入"cat"和"can"

• 插入"cat"：根节点创建c子节点→c节点创建a子节点→a节点创建t子节点，标记t为结束。
• 插入"can"：根节点已有c子节点→移动到c节点，c节点已有a子节点→移动到a节点，a节点创建n子节点，标记n为结束。

（2）搜索操作
目标：判断单词是否存在于Trie中。
步骤：

1. 从根节点开始，逐字符向下遍历。
2. 若某字符对应的子节点不存在，立即返回false。
3. 遍历完所有字符后，检查当前节点的结束标志：若为true则返回true，否则返回false（说明单词是前缀而非完整单词）。

示例：搜索"can"

• 根→c→a→n，n节点的结束标志为true，返回true。
  搜索"ca"：
• 根→c→a，但a节点的结束标志为false，返回false。

（3）前缀搜索
目标：判断是否存在以指定前缀开头的单词（与完整搜索的区别在于无需检查结束标志）。
步骤：

1. 类似搜索操作，但遍历完前缀的所有字符后，只要路径存在即返回true。

示例：前缀搜索"ca"

• 根→c→a，路径存在，返回true。

3. 复杂度分析

• 时间复杂度：
  • 插入/搜索/前缀搜索：O(L)，其中L为单词长度。与Trie中存储的单词总数无关。
• 空间复杂度：
  • 最坏情况：O(N×L×K)，N为单词数，L为平均长度，K为字符集大小。但通过共享前缀，实际空间通常小于哈希表。

4. 代码实现要点（以小写字母为例）

class TrieNode:
    def __init__(self):
        self.children = [None] * 26  # 26个小写字母
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def _char_to_index(self, ch):
        return ord(ch) - ord('a')  # 字符映射到0-25的索引
    
    def insert(self, word):
        node = self.root
        for ch in word:
            index = self._char_to_index(ch)
            if not node.children[index]:
                node.children[index] = TrieNode()  # 创建新节点
            node = node.children[index]
        node.is_end = True  # 标记单词结束
    
    def search(self, word):
        node = self.root
        for ch in word:
            index = self._char_to_index(ch)
            if not node.children[index]:
                return False
            node = node.children[index]
        return node.is_end  # 必须为完整单词
    
    def startsWith(self, prefix):
        node = self.root
        for ch in prefix:
            index = self._char_to_index(ch)
            if not node.children[index]:
                return False
            node = node.children[index]
        return True  # 前缀存在即可

5. 实际应用场景

• 输入法提示：输入前缀时快速推荐候选词。
• 路由表匹配：IP地址最长前缀匹配。
• 拼写检查：结合DFS可实现纠错建议（如修改一个字符后是否成词）。

通过以上步骤，Trie树的核心原理和实现已完整覆盖。其优势在于前缀共享的高效性，但需注意字符集较大时可能的空间开销（可改用哈希表存储子节点）。