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

Trie树（又称字典树、前缀树）是一种用于高效存储和检索字符串集合的树形数据结构。它的核心思想是利用字符串的公共前缀来减少查询时间，特别适合处理前缀匹配、自动补全等场景。

1. Trie树的基本结构

Trie树是一棵多叉树，每个节点包含以下部分：

• 子节点指针数组（或哈希表）：用于指向下一个字符的节点。
• 结束标志：标记当前节点是否是一个单词的结尾。

例如，存储单词["cat", "can", "do", "dog"]的Trie树结构如下（简化表示）：

        root
       /    \
      c      d
     /        \
    a          o
   / \          \
  t   n          g
  |   |          |
 (T) (T)        (T)

（(T)表示单词结束标志）

2. Trie树的操作详解

（1）插入操作

目标：将单词逐字符插入Trie树。
步骤：

1. 从根节点开始，遍历单词的每个字符。
2. 若当前字符对应的子节点存在，则移动到该子节点。
3. 若子节点不存在，则创建新节点，并移动到新节点。
4. 处理完最后一个字符后，在末尾节点标记单词结束。

示例：插入单词"car"

• 根节点 → 检查子节点c（存在）→ 移动到c节点。
• c节点 → 检查子节点a（存在）→ 移动到a节点。
• a节点 → 检查子节点r（不存在）→ 创建r节点，并标记结束。

（2）搜索操作

目标：判断单词是否存在于Trie树中。
步骤：

1. 从根节点开始，按字符顺序遍历单词。
2. 若某字符对应的子节点不存在，返回false。
3. 遍历到最后一个字符时，检查该节点是否有结束标志。若有则返回true，否则返回false。

示例：搜索单词"can"

• 路径c→a→n存在，且n节点标记为结束 → 返回true。

（3）前缀查询

目标：判断是否存在以指定前缀开头的单词。
步骤：与搜索操作类似，但不需要检查结束标志，只需验证前缀路径存在即可。

示例：查询前缀"ca"

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

3. Trie树的代码实现（Python）

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

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

4. Trie树的优缺点

优点：

• 前缀查询高效：时间复杂度为O(L)（L为单词长度）。
• 避免重复存储：共享前缀的单词节省空间。

缺点：

• 空间消耗大：每个节点需存储子节点指针（可优化为压缩Trie）。
• 适合字符集较小的场景（如英文单词），若字符集过大（如Unicode），空间开销显著。

5. 实际应用场景

1. 搜索引擎自动补全：根据输入前缀快速推荐候选词。
2. 拼写检查：判断单词是否存在于字典中。
3. IP路由表最长前缀匹配：用于网络数据包转发。
4. 输入法预测：根据前缀预测后续字符。

6. 扩展优化

• 压缩Trie：合并只有一个子节点的路径，减少空间占用（如Patricia Trie）。
• 双数组Trie：用两个数组存储节点关系，提高缓存友好性（常用于中文分词）。

通过以上步骤，你可以逐步理解Trie树的核心原理、实现方法及其适用场景。