字典树是什么（前缀树）
字典树（Trie），也叫前缀树，是一种专门用来高效存储和查找字符串集合的树形数据结构。想象一个电话本，你想快速找到所有以“张”开头的联系人——字典树就是为这种“前缀匹配”而生的。它的每个节点代表一个字符，从根节点到某个节点的路径就对应一个字符串的前缀。
插入与查找流程
插入时，从根节点开始，按照字符串的每个字符向下走：如果当前字符对应的子节点存在，就继续；如果不存在，就创建一个新节点。查找时同样从根节点出发，沿着字符路径走，如果路径完整走完且最后一个节点有结束标记，说明字符串存在；否则不存在。整个过程就像在迷宫里按路标前进，每个字符决定下一个岔路口。
前缀查询与自动补全原理
前缀查询只需找到前缀对应的节点，然后以该节点为根，遍历所有子路径就能得到所有以该前缀开头的单词。自动补全正是利用这一特性：输入“ap”，字典树快速定位到“ap”节点，然后输出所有后续分支（如“apple”、“application”）。这比遍历整个词库快得多，因为只搜索前缀相关的部分。
结束标记 isEnd 的作用
每个节点有一个布尔属性 isEnd，标记从根到该节点的路径是否构成一个完整的单词。例如，字典树中同时有“app”和“apple”，那么“app”节点的 isEnd 为 true，“apple”节点的也为 true。没有这个标记，我们就无法区分“app”是完整单词还是“apple”的前缀。它就像书签，告诉我们在哪里可以“停下来”作为一个有效词。
复杂度、空间权衡与 vs 哈希表
| 对比项 | 字典树 | 哈希表 |
|---|---|---|
| 查找/插入时间复杂度 | O(L)，L 为字符串长度 | 平均 O(L)，最坏 O(L²) |
| 前缀查询 | O(L) 找到前缀节点后，输出所有单词需遍历子树 | 不支持高效前缀查询 |
| 空间占用 | 较高，每个节点存储多个子节点指针（如 26 个字母） | 较低，只存储键值对 |
| 适用场景 | 大量字符串共享前缀、自动补全、拼写检查 | 一般键值存储，无前缀需求 |
字典树用空间换时间：每个节点预留子节点数组（如 26 个字母）导致内存浪费，但查找和插入只与字符串长度有关，与集合大小无关。哈希表虽然空间更省，但无法高效处理前缀查询，且哈希冲突可能退化。因此，在需要前缀匹配的场景（如搜索引擎提示）中，字典树是更优选择。