背景彻底搞懂前缀树Trie搜索联想、敏感词过滤的底层神器日常上网时我们经常会遇到这些场景在浏览器、输入法输入几个字自动弹出相关联想词条APP 后台自动过滤文本中的违规敏感词路由器快速匹配 IP 最长前缀完成路由转发这些看似毫不相关的功能底层都依赖同一个经典数据结构——前缀树Trie也叫字典树。很多人觉得树结构复杂难懂但前缀树绝对是「入门简单、威力极大」的特例。今天我们用最通俗的语言从零吃透前缀树的核心原理、操作流程、代码实现、实战场景。一、什么是前缀树一句话核心定义前缀树是一种专门针对字符串设计的多叉树核心思想只有八个字共享前缀、按需分叉。和普通数组、哈希表存储字符串不同前缀树不会单独存储每一个完整单词而是将所有字符串的公共前缀合并存储不同后缀单独分叉极致节省存储空间同时实现高效的前缀匹配。前缀树核心结构规则根节点为空不存储任何字符是所有字符串的起始入口每条边代表一个字符父子节点的连线对应单个字母/字符节点带结束标记每个节点可以标记「是否为单词末尾」用来区分「前缀」和「完整单词」。直观示例我们存入 3 个单词app、apple、apply普通存储需要完整存储 3 个字符串重复的 app 前缀重复占用空间前缀树存储共享 a→p→p 公共前缀后续仅分叉 l→e、l→y大幅压缩空间。树形结构示意根节点 └─ a └─ p └─ p✅ 单词结尾app └─ l ├─ e✅ 单词结尾apple └─ y✅ 单词结尾apply二、为什么要用前缀树对比传统结构处理字符串查找、前缀匹配我们最常用的是数组遍历 和 哈希表HashMap但二者都有明显短板。数组遍历每次匹配前缀都需要遍历所有单词数据量越大速度越慢时间复杂度 O(n*len)海量数据下完全不可用。哈希表查询单个单词速度快但不支持前缀模糊匹配无法实现搜索联想、批量前缀检索且大量重复前缀会造成严重的空间浪费。前缀树的优势查询稳定高效插入、查询、前缀匹配时间复杂度均为 O(字符串长度)和单词总数量无关空间极致优化复用公共前缀字符串越多空间优势越明显天然支持前缀匹配这是哈希表无法替代的核心能力完美适配搜索联想场景。三、前缀树三大核心操作图文流程前缀树所有功能都基于三个基础操作插入、单词查询、前缀匹配。全程逻辑统一简单好记。1. 插入操作构建树结构核心逻辑有则复用无则新建末尾打标记从根节点开始遍历逐个读取单词的每个字符判断当前节点是否存在对应子节点存在则直接跳转子节点不存在则新建子节点所有字符遍历完成后将最后一个节点标记为「单词结尾」。2. 完整单词查询核心逻辑路径完整 末尾是单词结尾从根节点出发逐字符匹配路径中途任意字符缺失直接判定单词不存在路径完全走完后必须判断末尾节点是否为单词结尾关键例树中有 app查询 ap 时路径存在但 ap 不是完整单词返回 false。3. 前缀匹配查询核心逻辑只需路径完整无需判断结尾这是搜索联想的核心只要输入的前缀字符路径能完整匹配就代表存在对应前缀的单词直接返回 true 即可。四、C 实现前缀树#includeiostream#includevector#includestringusingnamespacestd;// 前缀树节点结构structTrieNode{// 26个小写英文字母初始化为空指针TrieNode*children[26]{nullptr};// 标记当前节点是否为单词结尾boolisEndfalse;};classTrie{private:TrieNode*root;// 根节点public:// 构造函数初始化空根节点Trie(){rootnewTrieNode();}// 插入单词voidinsert(string word){TrieNode*noderoot;for(charc:word){intidxc-a;// 字符映射为0-25下标// 节点不存在则新建if(!node-children[idx]){node-children[idx]newTrieNode();}// 移动到子节点nodenode-children[idx];}// 标记单词末尾node-isEndtrue;}// 查找完整单词boolsearch(string word){TrieNode*noderoot;for(charc:word){intidxc-a;// 路径中断单词不存在if(!node-children[idx])returnfalse;nodenode-children[idx];}// 路径走完必须是单词末尾才返回truereturnnode-isEnd;}// 判断是否存在指定前缀boolstartsWith(string prefix){TrieNode*noderoot;for(charc:prefix){intidxc-a;if(!node-children[idx])returnfalse;nodenode-children[idx];}// 仅需路径完整无需判断结尾returntrue;}};// 测试演示intmain(){Trie trie;trie.insert(apple);coutboolalpha;couttrie.search(apple)endl;// truecouttrie.search(app)endl;// falsecouttrie.startsWith(app)endl;// truereturn0;}数组模拟实现前缀树#includeiostream#includestringusingnamespacestd;constintN100010;// 根据题目数据量开大一点inttr[N][26];// 树结构tr[当前节点][字符] 子节点编号boolcnt[N];// 标记是否为单词结尾intidx;// 节点分配器从0开始0是根节点// 初始化前缀树voidinit(){memset(tr,0,sizeof(tr));memset(cnt,0,sizeof(cnt));idx0;}// 插入单词voidinsert(string s){intu0;// 从根节点出发for(charc:s){intpc-a;if(!tr[u][p]){tr[u][p]idx;// 没有则新建节点编号1}utr[u][p];// 走到子节点}cnt[u]true;// 末尾标记为单词}// 查询完整单词boolsearch(string s){intu0;for(charc:s){intpc-a;if(!tr[u][p])returnfalse;utr[u][p];}returncnt[u];// 必须是单词结尾}// 查询是否存在前缀boolstartsWith(string s){intu0;for(charc:s){intpc-a;if(!tr[u][p])returnfalse;utr[u][p];}returntrue;// 路径走完即存在前缀}intmain(){init();insert(apple);coutsearch(apple)endl;// 1coutsearch(app)endl;// 0coutstartsWith(app)endl;// 1return0;}五、前缀树真实落地场景前缀树不是纸上谈兵的算法结构在工程开发中应用极广几乎所有字符串前缀相关的优化场景都能看到它的身影搜索框/输入法联想补全输入部分前缀快速匹配所有关联词条敏感词过滤系统将所有敏感词构建前缀树遍历文本即可快速匹配违规词汇效率远超暴力匹配拼写检查工具快速校验单词是否合法路由最长前缀匹配网络路由器通过前缀树精准匹配最优路由地址字符串统计统计指定前缀的单词数量、高频词筛选。六、前缀树优缺点总结✅ 优点前缀匹配、字符串查询效率极高不受数据总量影响大量相似字符串场景下空间利用率远超哈希表、数组逻辑清晰代码实现简单工程落地性强。❌ 缺点短字符串、无公共前缀的字符串场景空间开销大于哈希表仅擅长前缀匹配不支持后缀、子串匹配可拓展AC自动机解决。七、学习总结前缀树的核心精髓可以浓缩为一句话用空间换时间用前缀共享降本增效。它没有复杂的旋转、平衡逻辑是最友好的树结构之一。掌握插入、查询、前缀匹配三大基础操作就足以应对 90% 的面试算法题和工程开发场景。后续进阶可以学习基于前缀树优化的 AC 自动机解决多模式字符串匹配、批量敏感词过滤等复杂问题。
