单词查找树
一、定义与目标
- 单词查找树（Trie）：一种基于字符串键字符的多叉树结构，用于高效查找和存储键值对。
- 性能目标：
- 查找命中：时间与键长成正比。
- 查找未命中：仅检查少数字符。
- API 扩展：
longestPrefixOf(s)：返回 ( s ) 前缀中最长的键。keysWithPrefix(s)：返回以 ( s ) 为前缀的所有键。keysThatMatch(s)：返回匹配 ( s ) 的所有键（.通配符）。- 示例：键集 "she sells sea shells by the shore"。
二、R 向单词查找树
1. 结构
- 节点：
- ( R ) 个链接（对应字母表大小）。
- 一个值（键尾字符处存储）。
- 键表示：隐式，从根到非空值节点的路径。
- 示例：键 "she" 值存储在 "e" 节点。
2. 操作
- 查找（get）：
- 从根沿键字符路径遍历。
- 结束于尾字符节点（命中返回值，未命中返回 null）或空链接（未命中）。
- 代码：
java private Node get(Node x, String key, int d) { if (x == null) return null; if (d == key.length()) return x; char c = key.charAt(d); return get(x.next[c], key, d + 1); } - 插入（put）：
- 查找至尾字符或空链接。
- 若空链接，创建剩余字符节点；若节点存在，更新值。
- 代码：
java private Node put(Node x, String key, Value val, int d) { if (x == null) x = new Node(); if (d == key.length()) { x.val = val; return x; } char c = key.charAt(d); x.next[c] = put(x.next[c], key, val, d + 1); return x; }
3. 扩展操作
- keys()：递归收集所有键。
- 代码：
java private void collect(Node x, String pre, Queue<String> q) { if (x == null) return; if (x.val != null) q.enqueue(pre); for (char c = 0; c < R; c++) collect(x.next[c], pre + c, q); } - keysWithPrefix(s)：查找 ( s ) 子树，收集键。
- keysThatMatch(s)：匹配模式，
.通配所有字符。 - 代码：
java private void collect(Node x, String pre, String pat, Queue<String> q) { if (x == null) return; int d = pre.length(); if (d == pat.length() && x.val != null) q.enqueue(pre); if (d == pat.length()) return; char next = pat.charAt(d); for (char c = 0; c < R; c++) if (next == '.' || next == c) collect(x.next[c], pre + c, pat, q); } - longestPrefixOf(s)：记录路径上最近非空值节点。
- 代码：
java private int search(Node x, String s, int d, int length) { if (x == null) return length; if (x.val != null) length = d; if (d == s.length()) return length; char c = s.charAt(d); return search(x.next[c], s, d + 1, length); } - delete(key)：置尾节点值为 null，若无子节点则递归删除。
- 代码：
java private Node delete(Node x, String key, int d) { if (x == null) return null; if (d == key.length()) x.val = null; else x.next[key.charAt(d)] = delete(x.next[key.charAt(d)], key, d + 1); if (x.val != null) return x; for (char c = 0; c < R; c++) if (x.next[c] != null) return x; return null; }
4. 性质
- 命题 F：结构唯一，与插入顺序无关。
- 命题 G：查找/插入访问数组次数 ( \leq ) 键长 + 1。
- 命题 H：未命中平均检查 ( \sim \log_R N ) 个节点（随机键）。
- 命题 I：链接总数 ( RN ) 至 ( RNw )（( w ) 为平均键长）。
5. 问题
- 空间：大 ( R )（如 256）时，内存开销 ( RNw ) 巨大。
- 单向分支：长键尾部浪费空间。
三、三向单词查找树（TST）
1. 结构
- 节点：
- 一个字符 ( c )。
- 三条链接：左（小于 ( c )）、中（等于 ( c )）、右（大于 ( c )）。
- 一个值。
- 等价性：R 向 Trie 的每个节点转为 BST。
2. 操作
- 查找（get）：
- 比较键字符与节点字符，选择左/中/右链接。
- 代码：
java private Node get(Node x, String key, int d) { if (x == null) return null; char c = key.charAt(d); if (c < x.c) return get(x.left, key, d); else if (c > x.c) return get(x.right, key, d); else if (d < key.length() - 1) return get(x.mid, key, d + 1); else return x; } - 插入（put）：
- 查找并补全节点，更新尾节点值。
- 代码：
java private Node put(Node x, String key, Value val, int d) { char c = key.charAt(d); if (x == null) { x = new Node(); x.c = c; } if (c < x.c) x.left = put(x.left, key, val, d); else if (c > x.c) x.right = put(x.right, key, val, d); else if (d < key.length() - 1) x.mid = put(x.mid, key, val, d + 1); else x.val = val; return x; }
3. 性质
- 命题 J：链接总数 ( 3N ) 至 ( 3Nw )。
- 命题 K：
- 未命中：( \sim \ln N ) 次字符比较。
- 命中/插入：键长 + ( \sim \ln N ) 次比较。
- 优点：
- 空间紧凑，适应大字母表。
- 自适应键结构（如车牌号字母+数字）。
- 缺点：结构依赖插入顺序，删除复杂。
4. 优化
- 混合 TST：根节点多向分支（如 ( R ) 或 ( R^2 )）。
- 单向分支：消除尾部冗余。
- 命题 L：优化后查找平均 ( \sim \ln N - t \ln R ) 次比较。
四、对比与选择
| 算法 | 未命中检查字符 | 空间 | 优点 |
|---|---|---|---|
| BST | ( c_1(\lg N)^2 ) | ( 64N ) | 随机键 |
| 红黑树 | ( c_2(\lg N)^2 ) | ( 64N ) | 性能保证 |
| 散列表 | ( w ) | ( 32N \sim 128N ) | 内置类型，无序 |
| R 向 Trie | ( \log_R N ) | ( (8R+56)N \sim (8R+56)Nw ) | 短键、小字母表 |
| TST | ( 1.39\lg N ) | ( 64N \sim 64Nw ) | 非随机键、大字母表 |
- R 向 Trie：空间够用时最快，适合小 ( R )。
- TST：平衡时间与空间，适应性强。
- 散列表：不支持有序操作，扩展性差。
五、总结
- R 向 Trie：极致性能，空间换时间。
- TST：紧凑高效，实用性强。
- 选择依据：键长、字母表大小、空间限制及操作需求。