字典树（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）。

空间：最坏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 怎么选？

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. 常见坑

1. 忘记is_end：startsWith为真 ≠search为真。
2. 数组越界：只对a-z用c-'a'，要处理大写 / 非字母需换map或统一转小写。
3. 内存泄漏：手写new必须delete或改unique_ptr；LeetCode 有时不要求析构，工程里必须管。
4. 删除误伤：删短词不能删掉长词仍需要的中间结点。
5. 空串：是否允许""为单词——要在根上设root->is_end或单独判断。

11. 推荐刷题顺序

1. LeetCode 208 — 实现 Trie
2. LeetCode 211 — 带.通配查找（DFS + Trie）
3. LeetCode 212 — 矩阵 + Trie
4. LeetCode 648 — 前缀替换
5. LeetCode 677 — 结点存额外数据

12. 一句话总结

• Trie= 按字符（或 bit）分层的路由树，共享前缀，单次操作O(键长)。
• 结点：子指针数组 / map+is_end（+ 可选计数）。
• 精确查找看末尾is_end；前缀查找只要求路径存在。
• 删除先清标记，再在无分叉、无其它词时回收结点。
• 需要前缀、词典、多词网格搜索时优先 Trie；只问成员是否存在用哈希往往更简单。

记住：Trie 的优势不在「单个单词查得快」，而在「很多单词共享前缀时，前缀类问题仍然只扫键长。