三叉搜索树 TST 是什么？它和 Trie 有什么区别？
简化版
TST，全称 Ternary Search Tree，三叉搜索树，是 Trie 和二叉搜索树思想的结合。
每个节点存一个字符，并有 3 条指针：小于当前字符、等于当前字符、大于当前字符。等于分支表示继续匹配下一个字符，小于和大于分支用于在同一层做字符搜索。
它比普通 Trie 更省孩子指针空间，但查找时多了字符比较和分支判断。
详细版
普通 Trie 的一个节点通常保存多个孩子，比如 a-z。
TST 节点只保存一个字符：
char c
left -> 当前字符更小
middle -> 当前字符相等，匹配下一个字符
right -> 当前字符更大| 结构 | 孩子表示 |
|---|---|
| Trie | 一个节点有多个字符孩子 |
| TST | 一个节点 3 个指针，像 BST 一样比较字符 |
TST 适合字符集较大、普通 Trie 孩子数组太浪费，但又希望保留前缀搜索能力的场景。
完整版教学
1. 为什么会有 TST
普通 Trie 对前缀搜索很友好，但节点孩子结构可能很占空间。
如果每个节点都有 children[256]，而真实孩子只有几个，空间浪费明显。
TST 想做一件事：保留 Trie 的逐字符匹配能力，同时把每个节点的孩子指针数量控制在 3 个。
2. TST 节点结构长什么样
一个 TST 节点通常包含：
char c
Node left
Node mid
Node right
boolean end含义是：
| 指针 | 含义 |
|---|---|
| left | 当前要匹配的字符小于 c |
| mid | 当前字符等于 c，进入下一个字符 |
| right | 当前要匹配的字符大于 c |
它有点像每一层都挂了一棵字符二叉搜索树。
3. 查找过程怎么走
查找单词 cat 时，拿当前字符和节点字符比较。
if ch < node.c: go left
if ch > node.c: go right
if ch == node.c:
if 是最后一个字符: 看 end
else: go mid and match next char只有走 mid 时，才会消费字符串的下一个字符。
TST 最容易混淆的点是：left/right 仍然比较同一个字符，mid 才进入下一个字符。
4. 和普通 Trie 的核心区别
普通 Trie 通过下标或 Map 直接找到某个字符孩子。
TST 则通过比较当前字符，在 left/right/mid 中导航。
| 维度 | 普通 Trie | TST |
|---|---|---|
| 单节点孩子 | 多个 | 3 个 |
| 查找字符 | 数组或 Map 定位 | 比较字符 |
| 空间 | 可能较大 | 通常更省 |
| 实现理解 | 更直接 | 稍绕 |
如果字符集大而稀疏，TST 会更有吸引力。
5. TST 是否支持前缀搜索
支持。
先查找到前缀最后一个字符对应的节点，然后从它的 mid 子树开始收集后续字符串。
如果前缀本身也是单词，还要先输出前缀。
例如前缀 ca：
找到 a 节点
如果 a.end 输出 ca
遍历 a.mid 输出 cat, car ...6. 复杂度怎么回答
TST 的查找复杂度和树形有关。
如果同层字符搜索比较平衡，查找接近：
O(L log A)其中 L 是字符串长度，A 是字符集分支规模。实际实现中也常说与字符串长度和字符比较路径有关。
普通数组 Trie 则更接近 O(L)，但空间常数大。
7. 它适合什么场景
TST 适合：
- 字符集较大；
- 数据集较稀疏；
- 需要前缀搜索；
- 希望比 Map Trie 更紧凑；
- 能接受稍复杂的查找逻辑。
工程中它不如普通 Trie 常见，但作为数据结构面试扩展点很有价值。
8. 常见误区与追问
- 误区：TST 是三叉堆或三叉树。 它是用于字符串搜索的三叉搜索树，不是堆结构。
- 误区：left/right 会消费下一个字符。 只有 mid 分支表示当前字符匹配成功并进入下一个字符。
- 误区：TST 不支持前缀匹配。 它支持，只是遍历入口和普通 Trie 稍有不同。
- 追问：TST 为什么省空间？ 每个节点固定 3 个指针，不需要为完整字符集准备孩子槽。
- 追问：它比 Trie 更快吗？ 不一定，它通常省空间，但字符比较路径可能更长。