字典树（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 很空——内存可能爆炸此时要评估压缩 TrieRadix 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::arrayTrieNode*,26next{};// next[i] 对应 aiboolis_endfalse;};优点访问O(1)常数小实现短。缺点固定 26 指针稀疏时浪费内存仅适合已知小字符集。3.2 哈希表版通用字符 / Unicode / 多语言structTrieNode{std::unordered_mapchar,TrieNode*next;boolis_endfalse;};优点字符集大或稀疏时更省。缺点哈希常数、指针分散缓存不如数组版。3.3 工程里还可以std::unique_ptrTrieNode管理子结点析构时递归释放下文代码用裸指针 显式delete便于 LeetCode 对齐生产可改智能指针。结点存int count前缀下有多少单词经过或在此结束的个数用于LC212 / 前缀计数类题。4. 核心操作设单词长度为L字母表大小为Σ数组实现里Σ26。操作含义时间插入沿字符走没有则建结点最后is_endtrueO(L)精确查找能否走完整条链且末尾is_endO(L)前缀查找能否走完整条链不要求is_endO(L)删除删单词但保留仍被其它词使用的路径O(L)空间最坏O(n · L · Σ)量级每个字符一层指针实际因前缀共享往往小于n个字符串各自存一份。5. 完整实现数组版 类封装#includealgorithm#includearray#includestring#includevectorclassTrie{structNode{std::arrayNode*,26next{};boolis_endfalse;Node(){next.fill(nullptr);}};Node*root_newNode();staticintidx(charc){returnc-a;}Node*walk(conststd::strings,intlen-1){if(len0)lenstatic_castint(s.size());Node*curroot_;for(inti0;ilen;i){intididx(s[i]);if(!cur-next[id])returnnullptr;curcur-next[id];}returncur;}public:Trie()default;~Trie(){clear(root_);}Trie(constTrie)delete;Trieoperator(constTrie)delete;voidinsert(conststd::stringword){Node*curroot_;for(charc:word){intididx(c);if(!cur-next[id])cur-next[id]newNode();curcur-next[id];}cur-is_endtrue;}boolsearch(conststd::stringword)const{Node*nodeconst_castTrie*(this)-walk(word);returnnodenode-is_end;}boolstartsWith(conststd::stringprefix)const{returnconst_castTrie*(this)-walk(prefix)!nullptr;}// 删除单词若路径上无其它词则回收结点可选优化boolerase(conststd::stringword){returnerase(root_,word,0);}private:staticvoidclear(Node*node){if(!node)return;for(Node*child:node-next)clear(child);deletenode;}staticboolerase(Node*node,conststd::stringword,inti){if(istatic_castint(word.size())){if(!node-is_end)returnfalse;node-is_endfalse;returntrue;}intididx(word[i]);Node*childnode-next[id];if(!child)returnfalse;booldeletederase(child,word,i1);if(!deleted)returnfalse;// 子结点无单词结尾且无其它分支 → 释放if(!child-is_endstd::all_of(child-next.begin(),child-next.end(),[](Node*p){returnpnullptr;})){deletechild;node-next[id]nullptr;}returntrue;}};5.1 使用示例#includeiostreamintmain(){Trie trie;trie.insert(apple);trie.insert(app);std::couttrie.search(app)\n;// 1std::couttrie.search(apple)\n;// 1std::couttrie.search(appl)\n;// 0前缀存在但不是完整单词std::couttrie.startsWith(appl)\n;// 1trie.erase(apple);std::couttrie.search(apple)\n;// 0std::couttrie.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_setstring均摊O(L)不直接支持较省只问「有没有这个单词」BST /setstringO(L log n)可做但麻烦中等有序遍历所有键TrieO(L)天然支持指针多、共享前缀前缀、词典、搜索树LeetCode208. 实现 Trie就是本节的直接应用。9. 经典题型与套路9.1 自动补全 / 列出所有前缀匹配在startsWith(prefix)走到结点node后从nodeDFS/BFS收集所有is_end路径即可。9.2 单词搜索 IILC212矩阵 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_endstartsWith为真 ≠search为真。数组越界只对a-z用c-a要处理大写 / 非字母需换map或统一转小写。内存泄漏手写new必须delete或改unique_ptrLeetCode 有时不要求析构工程里必须管。删除误伤删短词不能删掉长词仍需要的中间结点。空串是否允许为单词——要在根上设root-is_end或单独判断。11. 推荐刷题顺序LeetCode 208 — 实现 TrieLeetCode 211 — 带.通配查找DFS TrieLeetCode 212 — 矩阵 TrieLeetCode 648 — 前缀替换LeetCode 677 — 结点存额外数据12. 一句话总结Trie 按字符或 bit分层的路由树共享前缀单次操作O(键长)。结点子指针数组 / mapis_end 可选计数。精确查找看末尾is_end前缀查找只要求路径存在。删除先清标记再在无分叉、无其它词时回收结点。需要前缀、词典、多词网格搜索时优先 Trie只问成员是否存在用哈希往往更简单。记住Trie 的优势不在「单个单词查得快」而在「很多单词共享前缀时前缀类问题仍然只扫键长。