Trie前缀树是专为字符串前缀操作设计的结构，所有操作稳定在O(L)，支持高效前缀匹配、自动补全与敏感词过滤；其节点只存单字符与子节点引用，通过isEnd标志单词结尾，根为空，路径拼接为前缀。

trie前缀树不是“更快的哈希表”，而是专为字符串前缀操作而生的结构——它把重复前缀压进同一路径，让搜索、插入、前缀匹配全部稳定落在o(l)（l为字符串长度），和词典总数量完全无关。这正是自动补全、敏感词过滤、拼写检查等场景离不开它的根本原因。

核心结构怎么搭才轻量又可靠

每个节点不存完整字符串，只管一个字符和它的“下家”：

• 子节点用数组（如26字母）或哈希表（支持任意字符）组织，平衡查询速度与内存占用
• 必须设一个标志位（如isEnd或count），标记此处是否构成合法单词结尾
• 根节点为空，不对应任何字符；从根到某节点的路径拼起来，就是该节点对应的前缀

三个基础操作的底层逻辑

所有操作都从根出发，逐字符“往下走”，不回溯、不遍历其他分支：

• 插入：对每个字符，若子节点不存在就新建；走到末尾，把isEnd设为true
• 精确查找：走完所有字符后，检查最终节点的isEnd是否为true
• 前缀匹配：只走完前缀字符，中途不断链即返回true，无需判断是否结尾

实际应用中容易踩的坑

高效不等于无脑套用，几个关键点直接影响效果：

• 字符集大（如Unicode）时，别硬用固定大小数组，改用哈希表存储子节点更省空间
• 频繁删除场景需额外维护子节点引用计数，否则可能产生“幽灵节点”影响前缀统计
• 做敏感词过滤时，建议在isEnd外再加一个isForbidden字段，支持分级策略（如高危词立即拦截，低危词仅标记）

比哈希表强在哪？看真实瓶颈

哈希表查“hello”很快，但查“he*”毫无办法；而Trie只要走两步就定位到所有以“he”开头的路径分支：

• 前缀查询天然支持，无需扫描全量数据
• 相同前缀（如“application”“apply”“app”）共用前3个节点，节省约50%+指针开销
• 配合DFS可快速枚举某个前缀下的全部词，自动补全候选列表生成极快