Trie 把字符串的公共前缀合并成路径。根不代表字符，从根沿字符边走到某节点即表示一个前缀；节点还需终止标记，区分“路径存在”和“完整单词存在”。例如插入 app 与 apple 会共享前三个字符。

插入时逐字符寻找孩子，不存在就创建，末节点标记结束；查完整词需路径存在且终止标记为真；查前缀只要求路径存在。若允许重复词或删除，可在节点记录经过数量与结尾数量，删除时递减并在计数归零后释放无用分支。

1
2
3
4
5
6
insert(word):
  node = root
  for c in word:
    node.children[c] ||= new Node
    node = node.children[c]
  node.end = true

设词长为 L，插入和查询时间为 O(L)，与词典中单词数量无直接线性关系。空间与所有不重复前缀总数有关。若字符集固定且小，孩子可用数组以换取快速索引；字符稀疏时用映射节省空槽；数据巨大还可采用压缩 Trie，把单孩子链合并为字符串片段。

Trie 适合自动补全、词典查询、前缀统计和路由匹配。输出所有前缀结果还需遍历子树，成本至少与结果数量相关。Unicode 场景应明确按何种字符单元切分。

误区是没有结束标记、认为空间一定小、删除公共前缀时误删其他词、忽略大小写规范化，以及把查询复杂度说成绝对 O(1)。小结：Trie 用空间换取与词长相关的前缀操作，是否划算取决于前缀共享度和字符集表示。