raw/articles/2026/05/前缀树(Trie)基础
前缀树（Trie）基础
⚠️ 内容不完整：原始文件仅包含核心原理与前缀操作部分，后续内容（如通配符匹配等）缺失。
核心原理（多叉树本质、空间优势、前缀操作复杂度）
Trie 树（又称字典树、前缀树）是 多叉树结构的延伸，专门针对字符串做优化：
- 每个节点代表一个字符串字符，从根节点到某一节点的路径表示一个完整字符串
- 空间优势：不重复存储公共前缀，例如存储
"apple"、"app"、"appl"仅需 5 个字符（HashMap 需存储 12 个字符，重复存储3次"app"、2次"l"） - 前缀操作复杂度：所有前缀相关操作（如
shortestPrefixOf、longestPrefixOf、hasKeyWithPrefix）的时间复杂度为 O(L)，L 为前缀长度，远优于 HashMap/TreeMap 的 O(N*L)（需遍历所有键逐一比对） - 与多叉树的关系：Trie 是特殊的多叉树，子节点对应下一个可能的字符，子节点数量取决于字符集大小（如小写字母为26个）
与现有数据结构对比（核心原理+定位对比）
本站已实现的数据结构定位对比：
| 数据结构 | 底层实现 | 键类型 | 核心操作复杂度 | 特点 |
|---|---|---|---|---|
| HashMap/HashSet | 哈希表 | 任意 | O(1) | 通用键值存储，无大小顺序 |
| TreeMap/TreeSet | 红黑树（自平衡BST） | 任意 | O(logN) | 维护键的大小顺序，支持有序操作 |
| LinkedHashMap | 哈希表+双链表 | 任意 | O(1) | 维护插入顺序 |
| ArrayHashMap | 哈希表+数组 | 任意 | O(1) | 支持 O(1) 随机返回键 |
| TrieMap/TrieSet | 多叉树（Trie） | 仅字符串 | O(L)（L为键长） | 针对字符串优化，支持前缀操作 |
TrieMap/TrieSet 是本文重点，TrieSet 为 TrieMap 的简单封装，实现原理一致。
应用场景（实际应用场景覆盖）
Trie 树的核心优势使其适合以下场景：
- 搜索自动补全：输入前缀实时返回匹配的所有字符串（
keysWithPrefix方法），如搜索引擎下拉提示 - 前缀匹配判断：快速判断是否存在以某前缀开头的键（
hasKeyWithPrefix） - 最短/最长前缀查询：
shortestPrefixOf、longestPrefixOf方法支持 - 字符串集合去重/判重：类似 HashSet，但额外支持前缀操作
- 大规模字符串存储：公共前缀多的场景（如证件号、域名）可大幅节省内存
相关概念
相关实体
- labuladong：算法学习平台作者