字典树（Trie / 前缀树）完全指南：插入、查找、前缀与删除
字典树（Trie / 前缀树）完全指南：插入、查找、前缀与删除
**字典树（Trie，又称前缀树 Prefix Tree）按字符（或比特）**逐层分支，而不是像 BST 那样按「整键」比较大小。
它特别适合：前缀匹配、词典 / 自动补全、字符串集合上的批量查询——键长为L时，单次操作通常是O(L)，与集合里已有多少单词n无关。
本文讲清结点结构、插入 / 精确查找 / 前缀查找 / 删除，给出可直接编译的 C++ 实现（数组版 +unordered_map版思路），并对比哈希表与 BST 的选型。
1. 什么时候想到 Trie？
看到下面信号，可以优先考虑字典树：
- 题目强调前缀：是否存在以某串为前缀的单词、统计前缀出现次数、自动补全
- 键是字符串 / 数字串 / IP / 二进制位，且要共享公共前缀
- 要在很多单词上做逐字符的 DFS / 回溯（如单词搜索、矩阵中的单词）
n很大但单键长度L不大（例如L ≤ 20），希望操作与n解耦
不太适合 Trie 的情况：键极长且稀疏、字符集巨大且每个结点 children 很空——内存可能爆炸，此时要评估压缩 Trie（Radix Tree）或哈希。
2. 结构长什么样？
每个结点表示「从根走到这里所形成的一个前缀」。边（或子指针）上标一个字符；结点常带is_end表示是否有单词在此结束。
插入"cat","car","dog"后（只画'a'..'z'分支）：
(root) c/ \d / \ [a] [o] / \ \ [t] [r] [g]* * * * cat car dog * 表示 is_end = true（该结点是一个完整单词的结尾）共享前缀：cat与car共用c → a两段路径，这是 Trie 相对「每个单词单独存一份」的主要优势。
3. 结点设计
3.1 数组版（小写字母a-z，面试最常见）
structTrieNode{std::array<TrieNode*,26>next{};// next[i] 对应 'a'+iboolis_end=false;};- 优点：访问
O(1)，常数小，实现短。 - 缺点：固定 26 指针，稀疏时浪费内存；仅适合已知小字符集。
3.2 哈希表版（通用字符 / Unicode / 多语言）
structTrieNode{std::unordered_map<char,TrieNode*>next;boolis_end=false;};- 优点：字符集大或稀疏时更省。
- 缺点：哈希常数、指针分散，缓存不如数组版。
3.3 工程里还可以
std::unique_ptr<TrieNode>管理子结点，析构时递归释放（下文代码用裸指针 + 显式delete便于 LeetCode 对齐；生产可改智能指针）。- 结点存
int count：前缀下有多少单词经过（或在此结束的个数），用于LC212 / 前缀计数类题。
4. 核心操作
设单词长度为L，字母表大小为Σ（数组实现里Σ=26）。
| 操作 | 含义 | 时间 |
|---|---|---|
| 插入 | 沿字符走，没有则建结点，最后is_end=true | O(L) |
| 精确查找 | 能否走完整条链且末尾is_end | O(L) |
| 前缀查找 | 能否走完整条链（不要求is_end） | O(L) |
| 删除 | 删单词但保留仍被其它词使用的路径 | O(L) |
空间：最坏O(n · L · Σ)量级（每个字符一层指针）；实际因前缀共享往往小于n个字符串各自存一份。
5. 完整实现（数组版 + 类封装）
#include<algorithm>#include<array>#include<string>#include<vector>classTrie{structNode{std::array<Node*,26>next{};boolis_end=false;Node(){next.fill(nullptr);}};Node*root_=newNode();staticintidx(charc){returnc-'a';}Node*walk(conststd::string&s,intlen=-1){if(len<0)len=static_cast<int>(s.size());Node*cur=root_;for(inti=0;i<len;++i){intid=idx(s[i]);if(!cur->next[id])returnnullptr;cur=cur->next[id];}returncur;}public:Trie()=default;~Trie(){clear(root_);}Trie(constTrie&)=delete;Trie&operator=(constTrie&)=delete;voidinsert(conststd::string&word){Node*cur=root_;for(charc:word){intid=idx(c);if(!cur->next[id])cur->next[id]=newNode();cur=cur->next[id];}cur->is_end=true;}boolsearch(conststd::string&word)const{Node*node=const_cast<Trie*>(this)->walk(word);returnnode&&node->is_end;}boolstartsWith(conststd::string&prefix)const{returnconst_cast<Trie*>(this)->walk(prefix)!=nullptr;}// 删除单词；若路径上无其它词则回收结点（可选优化）boolerase(conststd::string&word){returnerase(root_,word,0);}private:staticvoidclear(Node*node){if(!node)return;for(Node*child:node->next)clear(child);deletenode;}staticboolerase(Node*node,conststd::string&word,inti){if(i==static_cast<int>(word.size())){if(!node->is_end)returnfalse;node->is_end=false;returntrue;}intid=idx(word[i]);Node*child=node->next[id];if(!child)returnfalse;booldeleted=erase(child,word,i+1);if(!deleted)returnfalse;// 子结点无单词结尾且无其它分支 → 释放if(!child->is_end&&std::all_of(child->next.begin(),child->next.end(),[](Node*p){returnp==nullptr;})){deletechild;node->next[id]=nullptr;}returntrue;}};5.1 使用示例
#include<iostream>intmain(){Trie trie;trie.insert("apple");trie.insert("app");std::cout<<trie.search("app")<<'\n';// 1std::cout<<trie.search("apple")<<'\n';// 1std::cout<<trie.search("appl")<<'\n';// 0（前缀存在但不是完整单词）std::cout<<trie.startsWith("appl")<<'\n';// 1trie.erase("apple");std::cout<<trie.search("apple")<<'\n';// 0std::cout<<trie.search("app")<<'\n';// 1（共享前缀仍在）}6. 图解：插入"app"再插入"apple"
插入 app: root --a--> [p] --p--> [p]* 插入 apple（复用 app 路径）: root --a--> [p] --p--> [p]* --l--> [e]* ↑ ↑ app apple精确查找"apple"：沿a→p→p→l→e走到末结点，且is_end == true。
查找"appl"：能走到l，但末结点is_end == false→ 不是完整单词。
7. 删除要注意什么？
删除只标记is_end = false最简单，但会留下「死结点」占内存。
上面erase在确认子树无其它单词、无分叉时递归delete子结点。
词表: app, apple 删 apple 后: 仍保留 app 路径上的 p 结点 删 app 后: 若 apple 已删，可整条 a→p→p 回收坑：删"app"时不能把"apple"的l→e一并删掉——必须先清is_end，再判断子树是否仍被其它词需要。
8. 与哈希表、BST 怎么选？
| 结构 | 精确查单词 | 前缀 / 自动补全 | 内存 | 典型场景 |
|---|---|---|---|---|
哈希unordered_set<string> | 均摊O(L) | 不直接支持 | 较省 | 只问「有没有这个单词」 |
BST /set<string> | O(L log n) | 可做但麻烦 | 中等 | 有序遍历所有键 |
| Trie | O(L) | 天然支持 | 指针多、共享前缀 | 前缀、词典、搜索树 |
LeetCode208. 实现 Trie就是本节的直接应用。
9. 经典题型与套路
9.1 自动补全 / 列出所有前缀匹配
在startsWith(prefix)走到结点node后，从nodeDFS/BFS收集所有is_end路径即可。
9.2 单词搜索 II（LC212）
矩阵 DFS + Trie：把待查单词表建 Trie，在网格上走四方向，沿 Trie 边走；到is_end就收集答案。
Trie 把「很多单词」合成一棵共享前缀的树，避免对每个格重复扫整个单词表。
9.3 前缀计数
结点增加int pass_count（经过次数）或end_count（在此结束的单词数），插入时沿途++，删时--。
9.4 0-1 Trie（最大异或）
把整数按二进制位从高到低建 Trie，每位只有0/1两个孩子，用于最大异或对等题——结构仍是 Trie，只是「字符」变成 bit。
10. 常见坑
- 忘记
is_end：startsWith为真 ≠search为真。 - 数组越界：只对
a-z用c-'a'，要处理大写 / 非字母需换map或统一转小写。 - 内存泄漏：手写
new必须delete或改unique_ptr；LeetCode 有时不要求析构，工程里必须管。 - 删除误伤：删短词不能删掉长词仍需要的中间结点。
- 空串：是否允许
""为单词——要在根上设root->is_end或单独判断。
11. 推荐刷题顺序
- LeetCode 208 — 实现 Trie
- LeetCode 211 — 带
.通配查找（DFS + Trie） - LeetCode 212 — 矩阵 + Trie
- LeetCode 648 — 前缀替换
- LeetCode 677 — 结点存额外数据
12. 一句话总结
- Trie= 按字符（或 bit）分层的路由树，共享前缀，单次操作
O(键长)。 - 结点：子指针数组 / map+
is_end（+ 可选计数）。 - 精确查找看末尾
is_end；前缀查找只要求路径存在。 - 删除先清标记，再在无分叉、无其它词时回收结点。
- 需要前缀、词典、多词网格搜索时优先 Trie；只问成员是否存在用哈希往往更简单。
记住：Trie 的优势不在「单个单词查得快」，而在「很多单词共享前缀时，前缀类问题仍然只扫键长。