Trie 前缀树

树、BST 与 Trie · HTML

数学 / 逻辑形态

根代表空前缀；边标字符，根到节点路径拼成一个前缀。节点含 children 映射与 terminal 标记/载荷。insert 逐字符建边；search 走完整路径并检查 terminal；starts_with 只需路径存在。

识别信号

• 大量字符串共享前缀并被反复查询。
• 需要区分完整词存在与前缀存在。
• 字符 DFS 要同时匹配词典中许多词。
• 查询复杂度应依赖查询长度而非词典总词数。
• 需要自动补全、最长前缀或词典剪枝。

容易误判的相似信号

核心不变量

任一 Trie 节点对应唯一前缀；其 children 恰表示字典中该前缀后可能出现的下一字符，terminal 只在完整词末端为真。

状态、转移与处理顺序

Python 骨架

class TrieNode:
    def __init__(self):
        self.children = {}
        self.terminal = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.terminal = True
    def _walk(self, text):
        node = self.root
        for ch in text:
            if ch not in node.children: return None
            node = node.children[ch]
        return node
    def search(self, word):
        node = self._walk(word)
        return bool(node and node.terminal)
    def starts_with(self, prefix):
        return self._walk(prefix) is not None

正确性思路

1. 插入按字符创建/复用边，归纳后根到末节点路径恰拼出 word，并标 terminal。
2. walk 每步只沿与下一个字符相同的边；若缺边，字典中不可能有该前缀。
3. 走完整路径后 terminal 区分‘该路径只是更长词前缀’与‘完整词已插入’，所以两类查询正确。

复杂度

边界条件

• 空字符串是否为词
• 大小写/Unicode 规范化
• 重复插入
• 删除后共享前缀
• terminal 与有 children 可同时存在
• 递归列出补全结果

错误模式

选择与排除规则

• 只有前缀查询/共享剪枝价值明显时选择 Trie。
• 字符域小而密可数组，大而稀用 map。
• 明确 terminal 与 prefix 两种语义。
• 与回溯组合时状态携带 node 而非完整前缀重查。

相关模板

原创微型例子

Recall prompts

• terminal 与 children 分别表达什么？
• 什么时候 hash set 比 Trie 更好？
• Trie 与 DFS 组合时为何传 node？

我的补充