【字典树 C++ 实现】

前言

字典树（Trie，也叫前缀树）适合用于实现自动补全、前缀搜索、单词字典、敏感词过滤等功能。

一、字典树（Trie）是什么？

Trie 是一棵多叉树（每个结点代表一个字符），从根节点到某个结点的路径表示一个字符串的前缀或整个单词。常见特征：

• 根节点代表空字符串。
• 每个边对应一个字符（例如英语小写字母 a–z），结点可以有多个子结点。
• 结点通常保存“是否是单词结尾”的标记（isEnd）。
• 查询单词或判断前缀都可以在树上沿字符逐层访问完成，时间复杂度与单词长度成线性关系。

优点：查询、插入、前缀查询时间优秀（O(L)），适合海量字符串前缀操作。缺点：内存消耗可能较大（尤其当字母表大或字符串稀疏时）。

二、基本操作与算法思路

1. 插入（Insert）

从根开始，对单词的每个字符：

• 若当前结点没有对应子结点则创建。
• 移动到子结点，处理下一个字符。
  最后标记当前结点为单词结尾。

时间复杂度：对单词长度为 L，插入为 O(L)。

2. 查找（Search）

类似插入，不创建结点，只沿字符查找：

• 若任一字符对应子结点缺失，则单词不存在。
• 如果遍历完字符且当前结点 isEnd 为真，则单词存在。

时间复杂度：O(L)。

3. 前缀判断（StartsWith）

沿字符查找，若能走完前缀字符则存在前缀。时间复杂度：O§，P 为前缀长度。

4. 删除（Remove）

删除相对复杂，要保证只删除不再被任何单词使用的结点。常用办法是递归：

• 递归到单词末尾，取消 isEnd 标记。
• 如果该结点没有子结点，则返回 true 表示该结点可删除，父结点将其指针置空并继续判断。
• 否则不可删除，返回 false。

时间复杂度：O(L)。

5. 自动补全（Autocomplete）

先定位到前缀结点，然后对该子树做 DFS/BFS 收集最多 k 个单词或全量单词。时间复杂度：查找前缀 O§ + 遍历匹配单词的复杂度（取决于输出量与深度）。

三、C++ 实现

#include<bits/stdc++.h>usingnamespacestd;/* Trie 实现（26 小写字母） 提供：insert, search, startsWith, remove, autocomplete */classTrieNode{public:boolisEnd;// 子结点指针数组（26）array<TrieNode*,26>children;TrieNode():isEnd(false){children.fill(nullptr);}~TrieNode(){for(autop:children){if(p)deletep;}}};classTrie{private:TrieNode*root;// 删除单词的递归函数，返回是否可以删除当前节点boolremoveHelper(TrieNode*node,conststring&word,intdepth){if(!node)returnfalse;if(depth==(int)word.size()){if(!node->isEnd)returnfalse;// 单词不存在node->isEnd=false;// 如果没有子节点，则可以删除该节点for(autoch:node->children)if(ch)returnfalse;returntrue;}intidx=word[depth]-'a';TrieNode*child=node->children[idx];if(!child)returnfalse;boolshouldDeleteChild=removeHelper(child,word,depth+1);if(shouldDeleteChild){deletechild;node->children[idx]=nullptr;// 判断当前节点是否能被删除：非单词结尾且无任何子节点if(!node->isEnd){for(autoch:node->children)if(ch)returnfalse;returntrue;}else{returnfalse;}}returnfalse;}// 自动补全：从 node 开始 DFS 收集单词voiddfsCollect(TrieNode*node,string&path,vector<string>&out,intlimit){if(!node)return;if((int)out.size()>=limit)return;if(node->isEnd)out.push_back(path);for(inti=0;i<26&&(int)out.size()<limit;++i){if(node->children[i]){path.push_back('a'+i);dfsCollect(node->children[i],path,out,limit);path.pop_back();}}}public:Trie(){root=newTrieNode();}~Trie(){deleteroot;}voidinsert(conststring&word){TrieNode*cur=root;for(charc:word){intidx=c-'a';if(idx<0||idx>=26){// 简化：本实现只支持小写字母，遇到其他字符可以选择跳过或抛错continue;}if(!cur->children[idx])cur->children[idx]=newTrieNode();cur=cur->children[idx];}cur->isEnd=true;}boolsearch(conststring&word)const{TrieNode*cur=root;for(charc:word){intidx=c-'a';if(idx<0||idx>=26)returnfalse;if(!cur->children[idx])returnfalse;cur=cur->children[idx];}returncur->isEnd;}boolstartsWith(conststring&prefix)const{TrieNode*cur=root;for(charc:prefix){intidx=c-'a';if(idx<0||idx>=26)returnfalse;if(!cur->children[idx])returnfalse;cur=cur->children[idx];}returntrue;}voidremove(conststring&word){removeHelper(root,word,0);}// 返回最多 limit 个以 prefix 为前缀的单词（按字典序）vector<string>autocomplete(conststring&prefix,intlimit=10){vector<string>res;TrieNode*cur=root;for(charc:prefix){intidx=c-'a';if(idx<0||idx>=26)returnres;if(!cur->children[idx])returnres;cur=cur->children[idx];}string path=prefix;dfsCollect(cur,path,res,limit);returnres;}};

四、测试

intmain(){Trie trie;vector<string>words={"apple","app","application","apt","banana","band","bandit","bat"};for(auto&w:words)trie.insert(w);// 测试 searchcout<<boolalpha;cout<<"search(\"app\") = "<<trie.search("app")<<"\n";// truecout<<"search(\"apply\") = "<<trie.search("apply")<<"\n";// false// 测试 startsWithcout<<"startsWith(\"ap\") = "<<trie.startsWith("ap")<<"\n";// truecout<<"startsWith(\"ba\") = "<<trie.startsWith("ba")<<"\n";// truecout<<"startsWith(\"cat\") = "<<trie.startsWith("cat")<<"\n";// false// 自动补全autocands=trie.autocomplete("ap",5);cout<<"autocomplete(\"ap\"):\n";for(auto&s:cands)cout<<" "<<s<<"\n";// 删除trie.remove("app");cout<<"after remove(\"app\") search(\"app\") = "<<trie.search("app")<<"\n";// depends: app was word, now falsecout<<"after remove(\"app\") startsWith(\"app\") = "<<trie.startsWith("app")<<"\n";// true (because application, apple)// 删除 "application" 再测试trie.remove("application");cout<<"after remove(\"application\") startsWith(\"app\") = "<<trie.startsWith("app")<<"\n";// still true because "apple"trie.remove("apple");cout<<"after remove(\"apple\") startsWith(\"app\") = "<<trie.startsWith("app")<<"\n";// maybe false if none leftreturn0;}

五、复杂度分析

• 插入 / 查找 / 前缀判断：对长度为 (L) 的单词为 (O(L))。
  （逐字符访问，最多做 L 次指针查找与数组索引。）

• 删除：最坏情况也为 (O(L))，因为需要沿路径向下再递归回溯判断删除条件。

• 空间复杂度：取决于树中结点数量。最坏情况（没有共享前缀）结点数等于所有单词长度之和，即 (\sum_{w\in S} |w|)。每个结点保存 26 个指针（或使用 map/哈希表以节省稀疏树的内存）。

• 实际工程中可以通过以下方式优化内存：

  1. 把 children 从array<TrieNode*,26>换成vector<pair<char, TrieNode*>>或unordered_map<char, TrieNode*>（节省稀疏树内存，但查找成本上升）。
  2. 使用内存池（pool allocator）减少频繁 new/delete 的开销。
  3. 使用压缩字典树（Radix Tree / Patricia Trie）合并只有一个孩子的链，减少结点数。
  4. 如果只处理小写字母且数据量大，使用array+bitset 带来时间优先的实现。