前缀树（trie树）通过共享公共前缀提升字符串操作效率，时间复杂度稳定为o(l)；其核心是多叉树结构，节点仅存字符或为空，用哈希表或数组映射子节点，辅以isend标记单词结尾；插入逐字符建链并置末节点isend=true；查找需路径存在且isend=true，前缀匹配只需路径存在；空间优化推荐哈希表及压缩trie。
前缀树（Trie 树）通过将字符串的公共前缀共享存储，显著提升插入、查找、前缀匹配等操作效率，时间复杂度稳定在 O(L)，L 为字符串长度，不依赖数据规模。
核心结构设计：节点怎么组织
Trie 树本质是多叉树，每个节点不存完整字符串，只存一个字符或空（根节点），关键在于子节点映射关系：
- 用哈希表（如 Python 的 dict、Java 的 HashMap）或固定数组（如小写字母用 size=26 的数组）管理子节点，支持 O(1) 查找子节点
- 每个节点增加布尔字段 isEnd，标记是否为某字符串结尾（用于判断单词是否存在，而非仅前缀）
- 无需存储字符本身（若用数组索引隐含字符，如 index 0 表示 'a'）；若用哈希表，则 key 是字符，value 是子节点引用
插入操作：逐字符向下构建
从根节点出发，对目标字符串每个字符依次处理：
- 若当前字符对应子节点不存在，新建节点并挂载
- 沿指针走到该子节点
- 处理完所有字符后，在末节点置 isEnd = true
例如插入 "cat"：根 → 'c' 节点（新建）→ 'a' 节点（新建）→ 't' 节点（新建），最后标记 't' 节点 isEnd=true；再插入 "car"，复用前两个节点，只新增 'r' 节点并标记结束。
查找与前缀匹配：路径存在性决定结果
查找完整单词：遍历字符，每步检查子节点是否存在，最后还需 isEnd == true；
前缀匹配（如 auto-complete）：只需成功走完所有前缀字符，无需 isEnd，路径存在即表示有词以它开头。
- 查找 "car"：根 → 'c' → 'a' → 'r'，且 'r' 节点 isEnd == true ⇒ 存在
- 查前缀 "ca"：走到 'a' 节点即停，只要路径完整 ⇒ 成功
- 查 "cap"：到 'p' 时无子节点 ⇒ 失败
空间优化与实用注意点
Trie 树优势明显，但可能浪费空间，尤其字符集大或单词稀疏时：
- 优先用哈希表而非固定数组，避免 256 字符 ASCII 全开数组；Unicode 场景更需动态结构
- 可结合压缩 Trie（如 Patricia Trie）合并单分支路径，减少冗余节点
- 实际应用中常搭配 DFS/BFS 实现按前缀列出所有词（如搜索框联想），只需从目标前缀节点开始遍历子树
