第 24 页：TST 定义与动机
内容：
存储字符和值在节点中（不是键中）。
每个节点有 3 个子节点：左（smaller）、中（equal）、右（larger）。
引用 Bentley-Sedgewick 论文摘要，说明TST 结合了快速排序和基数排序的思想，用于字符串搜索，比哈希更快，比多路树更省空间。
物理含义：
R-way trie 的问题是每个节点有 R 个槽位，R 大时空间爆炸。
TST 把“一个节点有 R 个孩子”改成“一个节点有 3 个孩子”：左、中、右。
每个节点存储一个字符
c和一个值val。从根到某个节点的路径上，每个节点贡献一个字符。但路径不是简单的“一个字符一个节点”，而是通过“中链”前进，通过“左/右链”在同一层比较字符。具体规则：当前节点字符为
c。如果要查找的字符等于c，走中链，并前进到下一个字符；如果小于c，走左链，当前字符不变（不前进）；如果大于c，走右链，当前字符不变。这样，同一层的左/右链实际上是在字符维度上做二分搜索，而中链是在字符串长度维度上前进。第 25 页：TST 结构演示
内容：
图示 TST 表示一棵 trie。左侧是标准的 26-way trie，右侧是 TST。
标注：“link to TST for all keys that start with a letter before s”、“link to TST for all keys that start with s”、“each node has three links”。
值存储在节点中，字符也存储在节点中。
物理含义：
在 26-way trie 中，根节点有 26 个槽位，分别对应 'a' 到 'z'。在 TST 中，根节点存一个字符（比如 's'），然后有左、中、右三个引用。
如果查找的键以 's' 开头，走中链；如果以小于 's' 的字符开头，走左链；大于 's' 走右链。
到达中链的下一个节点后，处理键的下一个字符。该节点也存一个字符，并有左中右三个引用。
所以 TST 本质上是把“R 路分支”替换成“二叉树式的字符比较”，但中链代表匹配成功，前进到下一个字符。
第 26-28 页：TST 查找演示
第 26 页：get("sea")
从根开始，根节点字符是 's'。键的第一个字符是 's'，相等，走中链，前进到下一个字符 'e'。
中链节点字符是 'e'。键的第二个字符是 'e'，相等，走中链，前进到下一个字符 'a'。
中链节点字符是 'a'。键的第三个字符是 'a'，相等，走中链，前进到键末尾。
到达末尾节点，检查值是否非空。图中显示值 14，命中。
第 27 页：get("sea") 继续
展示路径的完整走法。不匹配时（字符小于或大于当前节点字符），走左或右链，但不前进到下一个字符。
只有字符相等时，才走中链，并前进到下一个字符。
第 28 页：get("shelter")
路径 s→h→e→l 后，下一个字符是 't'。当前节点（l 之后的中链）可能没有 't' 的中链，或者左/右链最终为 null。
返回 null，未命中。
物理总结：
查找时，维护两个索引：一个在键中（第 d 个字符），一个在 TST 中（当前节点）。
比较
key.charAt(d)和当前节点的c：
相等：走中链，
d+1。小于：走左链，
d不变。大于：走右链，
d不变。如果当前节点为 null，返回 null。
如果
d == key.length()，检查当前节点的值。第 31 页：26-way trie vs TST 空间对比
内容：
26-way trie：每个叶子节点有 26 个 null 链接。图中 26-way trie 有 1035 个 null 链接（未画出）。
TST：每个叶子节点有 3 个 null 链接。
物理含义：
26-way trie 的每个节点有 26 个引用槽位，即使只有一个子节点，其余 25 个槽位都是 null。空间浪费严重。
TST 的每个节点只有 3 个引用槽位（left、mid、right），加上一个字符和一个值。节点大小固定，与字母表大小 R 无关。
因此 TST 的空间与 R 无关，只与键的总字符数有关。对于 Unicode 这样的大 R，TST 是唯一可行的选择。
第 32 页：TST 节点表示
内容：
java
private class Node { private Value val; private char c; private Node left, mid, right; }
TST 节点有五个字段：值、字符、左引用、中引用、右引用。
物理含义：
每个节点在堆上分配，包含一个
Value引用（8 字节）、一个char（2 字节）、三个Node引用（各 8 字节），加上对象头（16 字节），对齐后约 48 字节。与 26-way trie 的节点（约 2000 字节）相比，TST 节点小得多。
字符
c显式存储在节点中，用于比较。第 34 页：TST 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; }物理含义：
递归下降。
x是当前节点，d是键中当前字符的索引。如果
x == null，返回 null。取
c = key.charAt(d)。如果
c < x.c，走左链，d不变。如果
c > x.c，走右链，d不变。如果
c == x.c且d < key.length() - 1，走中链，d+1。如果
c == x.c且d == key.length() - 1，到达键的最后一个字符，返回当前节点。调用者检查返回值是否为 null，以及
x.val是否非空。第 35 页：性能对比表
内容：
实现 查找命中 查找未命中 插入 空间 moby.txt 去重 actors.txt 去重 红黑树 L + c lg²N c lg²N c lg²N 4N 1.40 97.4 哈希表 L L L 4N-16N 0.76 40.6 R-way trie L log_R N L(R+1) - 1.12 out of memory TST L + ln N ln N L + ln N 4N 0.72 38.7 底部：TST 和哈希一样快（对字符串键），且空间高效。可以通过旋转构建平衡 TST，达到 L + log N 最坏情况保证。
物理含义：
TST 的查找命中代价是 L + ln N（平均情况）。L 是键长度，ln N 是字符比较的树深度。
查找未命中代价是 ln N，通常只检查少数几个字符。
空间与红黑树相当，约 4N 个引用。
对 actors.txt（键很多、R 很大），R-way trie 内存不够，TST 可以处理。
第 36 页：TST with R² Hybrid
内容：
混合结构：在根节点做 R² 路分支，每个根节点指向一个 TST。
图示：数组 of 26² roots，每个根指向一个 TST。
问题：单字母和双字母单词怎么办？
物理含义：
为了进一步加速，可以把前两个字符用数组直接索引（26² = 676 个槽位），然后每个槽位指向一个 TST 处理剩余字符。
这样，前两个字符的查找是 O(1) 数组访问，不需要在 TST 中比较。
单字母和双字母单词可以单独处理，或者把它们的值存在根数组的对应槽位中。
第 37 页：性能对比表（含 R² Hybrid）
内容：新增 TST with R² 行：
实现 查找命中 查找未命中 插入 空间 moby.txt 去重 actors.txt 去重 TST L + ln N ln N L + ln N 4N 0.72 38.7 TST with R² L + ln N ln N L + ln N 4N + R² 0.51 32.7 底部：比哈希更快（对基准客户端）。
物理含义：
额外的 R² 空间（对于 26 字母表，676 个引用）换来前两个字符的 O(1) 访问，减少了 TST 的深度。
在 moby.txt 和 actors.txt 上，字符访问次数比纯 TST 更少。
第 38 页：TST vs 哈希
内容：
哈希：需要检查整个键；查找命中和未命中代价相同；依赖哈希函数；不支持有序符号表操作。
TST：只适用于字符串（或数字键）；只检查足够的字符；查找未命中可能只涉及少数几个字符；支持有序符号表操作（以及更多）。
底部：TST 比哈希快（尤其是未命中），比红黑树更灵活。
物理含义：
哈希表计算
hashCode必须遍历整个键，无法提前退出。TST 在未命中时可能只检查第一个字符就返回。TST 的中序遍历可以按字典序输出所有键，哈希表不支持。
TST 支持前缀查找、通配符匹配、最长前缀等字符级操作。
一、结构分析
Q：我理解了，它之所以像红黑树，是因为左右子节点和它本身其实是平级的，只有中间子节点才是下级。我理解了，它之所以像红黑树，是因为左右子节点和它本身其实是平级的，只有中间子节点才是下级。
A：没错，这就是它本质的结构特征。
左/右子节点和当前节点是平级的
在 TST 中，当前节点存储字符
c。查找时，比较的是键中第d个字符key.charAt(d)和c。
如果走左链，下一个节点仍然在处理键的第
d个字符。只是它存储的字符比c小。如果走右链，下一个节点也仍然在处理键的第
d个字符。只是它存储的字符比c大。只有走中链，才表示第
d个字符匹配成功，前进到第d+1个字符。所以左链和右链上的所有节点，都在处理同一个字符位置
d。它们之间的比较是“在同一层内，用二叉搜索的方式找到匹配的字符”。中链才是“进入下一层”。物理图示
把 TST 按“字符位置 d”分层：
第 0 层：处理键的第一个字符。这一层是一棵二叉搜索树，节点字符按大小排列。
第 1 层：处理键的第二个字符。从第 0 层某个节点的中链进入。这一层也是一棵二叉搜索树。
第 2 层：处理键的第三个字符。从第 1 层某个节点的中链进入。
以此类推。
每一层内部的左/右链是平级的，中链是垂直向下的。
与 R-way trie 的对比
R-way trie 中，一个节点有 R 个槽位，每个槽位直接对应一个字符。从节点到子节点的跳转，本身就是“进入下一个字符位置”。
TST 把“R 个槽位的数组”替换成“二叉搜索树”。在二叉搜索树中，左/右链是查找同一个字符位置的不同字符，中链才是进入下一个字符位置。
总结
你的判断正确：左/右子节点和当前节点处理的是同一个字符位置，它们是平级的。中链才进入下一个字符位置。这是 TST 用三叉结构模拟 R 路分支的物理机制。
二、性能对比
Q：好吧，现在我想要你来为我分析一下，第三十五页的这张表，尤其是关于这些插入和查找的数，都是如何被算出来的
A：第 35 页的表格是字符串符号表实现的成本对比。表中的search hit、search miss、insert列给出的是平均情况下，每次操作需要访问的字符次数，用 N（键的数量）、L（键的平均长度）、R（字母表大小）表示。dedup列是实际测量值，用于比较实际性能。
红黑树
search hit:
L + c lg² Nsearch miss:
c lg² Ninsert:
c lg² N物理动作：
红黑树是一棵平衡二叉搜索树，查找时从根走到目标节点，路径长度约为
lg N次比较。每次比较是两个字符串的
compareTo。compareTo从第一个字符开始逐个比较，直到找到不同或到达末尾。在红黑树中，比较的两个键（查询键和节点键）在字典序上通常比较接近，它们的公共前缀长度平均约为
lg N（这是 Sedgewick 书中的分析结论，不是随机字符串的公共前缀）。因此，每次比较需要访问约
lg N个字符。总共lg N次比较，字符访问次数约为lg N × lg N = lg² N。查找命中时，最后还需要验证找到的键与查询键完全相等，这需要再访问
L个字符。所以总字符访问为L + c lg² N。查找未命中和插入不需要最后的完整匹配，所以只有
c lg² N。哈希表（线性探测）
search hit:
Lsearch miss:
Linsert:
L物理动作：
每次
put或get都要计算键的hashCode。String.hashCode()的物理动作是遍历字符串的每个字符，用h = 31 * h + c计算哈希值。必须访问全部L个字符，一个都不能跳过。计算完哈希值后，可能还需要在链表或探测序列中用
equals比较键，但equals通常也在第一个不同字符处提前结束，平均代价很小。所以主导成本是计算哈希值的
L次字符访问。查找命中和未命中都需要计算哈希值，所以都是L。R-way Trie
search hit:
Lsearch miss:
log_R Ninsert:
L(R+1)（每个键的平均字符访问次数，用于创建节点和初始化链接）物理动作：
查找命中：沿着键的每个字符走一步，每步访问一个字符，共
L步。查找未命中：平均路径长度是
log_R N（因为每个节点有 R 个子节点，树的高度约为log_R N）。在未命中时，通常只走了一部分路径就遇到 null 链接，所以字符访问次数约为log_R N。插入：需要为每个新字符创建新节点。每个新节点有一个长度为 R 的
next数组，创建时需要初始化 R 个引用槽位（置为 null）。所以每个新节点需要 R 次写。长度为 L 的键需要创建 L 个新节点，所以写访问约为L × R。再加上读取键字符的L次访问，总计约L(R+1)。TST（三叉搜索树）
search hit:
L + ln Nsearch miss:
ln Ninsert:
L + ln N物理动作：
TST 的每个节点存储一个字符，有三个链：左、中、右。
查找时，沿着中链前进表示匹配成功并处理下一个字符，左/右链用于在同一层内做字符的二叉搜索。
查找命中：需要沿着中链走
L步（每个字符一步），每步在左/右链中做二叉搜索，平均深度为ln N（因为左/右链构成一棵随机的二叉搜索树，平均深度约为ln N）。所以总字符访问约为L + ln N。查找未命中：通常在第一层就可能在左/右链中走
ln N步后遇到 null，或者在中链走了几步后遇到 null。平均字符访问约为ln N。插入：与查找命中类似，需要沿着路径走
L + ln N步，并在必要时创建新节点。dedup 列的实际测量值
dedup列（moby.txt 和 actors.txt）是实际运行这些实现，对文件中的单词去重，测量得到的归一化字符访问次数。具体归一化方式可能是“总字符访问次数 / 总字符数”或“每个键的平均字符访问次数 / 平均键长”。这些数字用于验证理论公式，并比较不同实现的实际性能。例如：
红黑树在 moby.txt 上是 1.409，意味着平均每个字符被访问了约 1.409 次。
哈希表是 0.764，说明哈希表访问的字符次数比红黑树少。
TST 是 0.72，比哈希表还少，因为 TST 在未命中时可能只检查少数几个字符。
这些实际数字取决于具体的数据集（单词长度分布、公共前缀情况等），所以与理论公式的常数因子有关，但趋势一致。
总结：表中的公式是理论平均字符访问次数，基于每个实现的操作物理动作推导。
dedup列是实际测量值，用于比较实际性能。理解这些公式的关键是追踪每次操作访问了哪些字符、访问了多少次。
Q：为什么linear probing使用的空间是4N~16N，r way tries使用的空间是（R+1）N而不是（R+1）L？以及，tst胜出的原因是比BST快，和BST空间持平，又和linear probing一样快，比它用的空间少吗？
A：
1. 线性探测哈希表：为什么是 4N ~ 16N
哈希表底层是一个数组，数组长度记为 M。M 必须大于键的数量 N，否则探测会失败。实际实现中，负载因子 α = N/M 通常控制在 1/8 到 1/2 之间，所以 M 的范围是 2N 到 8N。
每个数组槽位存储两个引用：一个指向键，一个指向值。所以每个槽位占 2 个引用。
总引用数 = 2M。代入 M 的范围：
M = 2N 时，总引用 = 4N。
M = 8N 时，总引用 = 16N。
所以空间是 4N 到 16N 个引用。
2. R-way trie：为什么是 (R+1)N，而不是 (R+1)L
R-way trie 的每个节点包含：
一个值引用（指向存储的值）。
一个长度为 R 的子节点引用数组。
所以每个节点占用 R + 1 个引用。
总空间 = 节点总数 × (R + 1)。
节点总数记为 M。M 取决于键的分布。如果所有键都没有公共前缀，每个键需要 L 个节点，M = N × L。如果大量共享前缀，M 会小于 N × L，但通常仍然大于 N。
表格中写的是 (R+1)N，这意味着它假设 M = N，即节点总数等于键的数量。这是一个简化估计。实际上，对于典型字符串数据集，M 通常大于 N，可能是 2N 到 3N。但表格用 (R+1)N 是为了表示“空间与 R 成正比，且与键的数量 N 同一量级”。
为什么不是 (R+1)L？因为 L 是单个键的长度，而总字符数是 N × L。节点数 M 不是 N × L（共享前缀减少了节点），而且每个节点有 R 个引用，所以总空间与 M 和 R 有关，不是直接与 L 有关。用 N 乘以 (R+1) 是一个数量级上的粗略表示。
关键结论：R-way trie 的空间与字母表大小 R 成正比。R 很大时（比如 Unicode 的 65536），空间会爆炸。这就是 actors.txt 直接 out of memory 的原因。
3. TST 为什么胜出
TST 的节点包含：
一个值引用。
一个字符（2 字节，但通常按引用大小对齐，可忽略）。
三个引用：left、mid、right。
所以每个节点约 4 个引用（值 + 三个链）。总空间 = 节点总数 × 4。节点总数与键的总字符数同量级，但每个节点很小。表格中 TST 空间写 4N，与红黑树相同。
速度对比：
红黑树：查找命中 L + c lg² N 字符访问。因为每次 compareTo 要扫描公共前缀，路径长度 lg N，所以有 lg² N 项。
TST：查找命中 L + ln N 字符访问。每个节点只比较一个字符，左/右链的二叉搜索平均深度 ln N。所以TST 更快，因为避免了重复扫描公共前缀。
哈希表：查找命中 L 字符访问（计算哈希值必须遍历整个键）。TST 是 L + ln N。当 L 较大时，ln N 相对 L 很小，所以速度与哈希表相当。
查找未命中：哈希表必须计算整个键的哈希值，访问 L 个字符。TST 通常只走几个字符就遇到 null，平均 ln N 个字符。所以 TST 未命中快得多。
空间对比：
红黑树：4N 引用。
哈希表：4N 到 16N 引用。
TST：4N 引用。
TST 的空间与红黑树持平，比哈希表的下界相同，但哈希表可能膨胀到 16N。所以 TST 在空间上不输给红黑树，且优于哈希表的平均情况。
额外优势：
TST 支持有序操作（按字典序遍历所有键），哈希表不支持。所以 TST 综合了红黑树的空间效率、哈希表的速度，以及有序操作能力。这就是它胜出的原因。
