前缀树（Trie）
前缀树（Trie，又称字典树、前缀树、单词查找树）是一种多叉树：从根到任一节点的路径对应一个字符串前缀，每条边代表一个字符。它专门为「字符串集合上的前缀查询」而生——插入、查找、前缀匹配都只需 O(L)（L = 单词长度），且共享公共前缀的单词在树上共用前缀路径，天然压缩了存储。它由 Edward Fredkin 于 1959 年提出，名字取自 retrieval（检索），是自动补全、词频统计、拼写检查、IP 路由最长前缀匹配等场景背后的核心结构。
Trie 的全部考点都源于一个设计权衡：空间换时间 + 共享公共前缀。由此衍生出三大主题：①核心操作（insert 逐字符向下建节点末尾置 isEnd、search 完整单词查找、startsWith 前缀搜索，复杂度均 O(L)）；②节点结构（isEnd 标志 + children 子节点映射，后者用 Map 通用或定长 Array[26] 适配纯小写字母表）；③工程应用（搜索框自动补全、词频统计节点存 count、IP 路由最长前缀匹配、压缩 Trie / Radix Tree）。其中**「前缀查询是 Trie 独有优势」**是与哈希表对比的核心卖点——哈希表只能精确查找整词，无法高效回答「以 app 开头的单词有哪些」。
评价
优点
- O(L) 插入/查找/前缀搜索：L = 单词长度，与词表规模 n 无关——词表再大，操作时间只随单词长度增长，这是 Trie 区别于哈希表（O(L) 但需哈希且无前缀能力）与二叉搜索树（O(L log n)）的核心优势
- 公共前缀压缩：共享前缀的单词（
app/apple/apply）在树上共用路径，省内存且天然支持「按前缀批量定位」 - 前缀查询是独门绝技：
startsWith("app")只需沿路径走 3 步即定位到前缀子树，哈希表/二叉搜索树做不到（哈希表要遍历全部，BST 要中序扫） - 词频统计顺手：节点里存
count，插入即 +1，统计「某单词出现几次」「某前缀下多少词」都是 O(L) - 字典序遍历友好：对
children按字符顺序深度优先遍历，天然得到字典序排序的单词列表，且无需比较排序（O(总字符数)）
缺点
- 空间开销大（空间换时间）：每个字符一个节点，节点还要存指针/子节点表，公共前缀少时比哈希表更耗内存——这是 Trie 最大的硬伤，也是压缩 Trie（Radix Tree）出现的动因
children选型两难：Map通用但常数大、缓存差；定长Array[26]速度快、O(1) 定位但只适配小字符集（如纯小写字母），且大量空槽更费空间- 对短字符串集合收益有限：词表小、单词短时，哈希表的哈希一次就够，Trie 多次指针跳转反而更慢
- 删除复杂：要递归判断「删除后该节点是否还有子节点 / 是否是其他单词结尾」，不能简单摘节点
本叶地图
- 入门 —— Trie 定义（多叉树字符边）、公共前缀压缩、节点结构（
isEnd+children）、与哈希表对比（前缀查询是独有优势）、空间换时间 - 核心操作 —— insert 逐字符建节点置
isEnd、search 完整查找、startsWith 前缀搜索、delete 递归、O(L) 复杂度、对象childrenvs 数组children[26]代码实现 - 工程应用 —— 自动补全、词频统计节点存
count、拼写检查、IP 路由最长前缀匹配、AC 自动机引入、压缩 Trie（Radix Tree / 基数树） - 参考 —— Trie API、复杂度表（与哈希表/BST 对比）、insert/search 代码模板、节点结构变体、应用清单、易错点
交互演示
- 前缀树可视化演示 —— Trie 的多叉树结构与字符边的插入/查找过程