5.2 Tries：R向单词查找树、TST与前缀查询

5.2 · Tries覆盖 5 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

  • 能解释“5.2 · Tries”如何用 R 向单词查找树和三向单词查找树支持字符串符号表、前缀与通配查询
  • 能逐项核对 单词查找树、字符串符号表、R向单词查找树、三向单词查找树、前缀与通配操作，并区分作者站内容与本页独立补充
  • 能按“查找长度为 W 的键访问 O(W) 个字符位置；空间由节点数与分支表示共同决定”手算一个最小输入，逐步检查“从根沿键字符可到达且终点携带值才算命中；内部节点也可以同时代表完整键”
  • 能注入“删除前缀键时把仍有孩子的节点一并剪掉，或用 null 值混淆键缺失与显式空值”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“5·2 · Tries”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“5·2 · Tries”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“5·2 · Tries”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：5.2 · Tries

  • 1. 单词查找树：在本页通过“读取下一个字符”连接解释、交互状态和练习验收。
  • 2. 字符串符号表：在本页通过“选择 R 向或三向分支”连接解释、交互状态和练习验收。
  • 3. R向单词查找树：在本页通过“创建或复用节点”连接解释、交互状态和练习验收。
  • 4. 三向单词查找树：在本页通过“标记键值终点”连接解释、交互状态和练习验收。
  • 5. 前缀与通配操作：在本页通过“执行前缀/通配核对”连接解释、交互状态和练习验收。

从“找到了前缀，不等于找到了单词”开始

把 she、shell、shells 放入普通symbol table时，它们是三个atomic keys；放入trie后，它们共享s→h→e这一条prefix path。单词查找树（tries）利用的正是这种共享结构。

先预测：若查询 sh 能沿links走到一个node，contains("sh") 是否为true？不一定。Node存在只证明至少有一个stored key以 sh 为prefix；只有该node的value非null，才证明 sh 本身是key。Prefix existence与word boundary是本节最重要的状态区分。

字符串符号表（string symbol tables）当然可以用hash table或balanced BST实现；tries的价值是exact lookup同样快，同时自然支持prefix enumeration、wildcard matching与longest-prefix lookup。

5.2.1 R-way tries：每个node代表一个prefix

R向单词查找树（R-way tries）为alphabet中的每个character保留一个link slot。Root代表empty prefix；从root沿s、h、e到达的node代表prefix she。

private static final int R = 256;
 
private static class Node {
    private Object val;
    private Node[] next = new Node[R];
}
 
private Node root;
private int n;

Node上的 val 与outgoing links相互独立：

  • val != null：当前prefix本身是一条key。
  • next[c] != null：至少一条更长key继续使用character c。
  • 两者都可同时成立，例如 she 是key且还通向 shell。

若stored keys总字符数为L，new node只在某个prefix第一次出现时创建，因此node count M满足：

1≤M≤1+∑key∣key∣=1+L1\le M\le 1+\sum_{key}|key|=1+L

大量shared prefixes让M远小于1+L；但dense R-way node仍为每个node分配R link slots，包括绝大多数null links。

5.2.2 Get与Put：只在character相等路径上推进digit

Exact get从root与digit 0开始。若node为null，key不存在；若d等于key length，返回current node；否则取 key.charAt(d) 并走对应child：

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);
}
 
public Value get(String key) {
    Node x = get(root, key, 0);
    if (x == null) return null;
    return (Value) x.val;
}

即使 get(root,"sh",0) 返回node，public get仍返回该node的val；若val为null，contains必须为false。Official API约定values不能为null，put(key,null)等价于delete，因而null可安全承担“不是key boundary”的sentinel。

Put与get路径相同，但遇到null node就allocate；只有d等于key length才写value。若此前val为null，size增加；replace existing key不能重复增加size：

private Node put(Node x, String key, Value val, int d) {
    if (x == null) x = new Node();
    if (d == key.length()) {
        if (x.val == null) n++;
        x.val = val;
        return x;
    }
    char c = key.charAt(d);
    x.next[c] = put(x.next[c], key, val, d + 1);
    return x;
}

长度为K的exact get/put最多消费K个characters：

Tget/put=Θ(K)T_{\mathrm{get/put}}=\Theta(K)

这个bound不依赖stored key count N；代价转移到了node memory与character mapping。

5.2.3 Prefix enumeration：定位一次，再collect一个subtrie

前缀与通配操作（prefix and wildcard operations）是trie超过generic hash table的关键能力。

keysWithPrefix(prefix)分两步：

  1. 用exact path traversal定位prefix对应node x。
  2. 从x做DFS collect，维护mutable StringBuilder；每遇到non-null val就输出current prefix。
public Iterable<String> keysWithPrefix(String prefix) {
    Queue<String> results = new Queue<>();
    Node x = get(root, prefix, 0);
    collect(x, new StringBuilder(prefix), results);
    return results;
}
 
private void collect(Node x, StringBuilder prefix, Queue<String> out) {
    if (x == null) return;
    if (x.val != null) out.enqueue(prefix.toString());
    for (char c = 0; c < R; c++) {
        prefix.append(c);
        collect(x.next[c], prefix, out);
        prefix.deleteCharAt(prefix.length() - 1);
    }
}

若P是prefix length，S是被访问subtrie nodes数，Z是output characters总量，则更诚实的成本是：

Tprefix=Θ(P+R⋅S+Z)T_{\mathrm{prefix}}=\Theta(P+R\cdot S+Z)

Dense R-way collect即使child为null也会循环R slots；用sparse child map时可改为按actual children访问，但若要lexicographic output，children需要ordered iteration或额外排序。

Mutable prefix的push/pop必须成对。忘记backtrack会把siblings拼接在一起；过早pop又会截断output key。Certificate可检查每个输出都startsWith(prefix)、存在于terminal set且无遗漏。

5.2.4 Wildcard matching：literal走一条，dot展开所有children

Official keysThatMatch用dot表示exactly one arbitrary character。At digit d：

  • Pattern[d]是literal c：只沿 next[c]。
  • Pattern[d]是dot：对所有non-null children递归。
  • d等于pattern length：只有current node val非null才输出。
private void collect(Node x, StringBuilder prefix,
                     String pattern, Queue<String> out) {
    if (x == null) return;
    int d = prefix.length();
    if (d == pattern.length()) {
        if (x.val != null) out.enqueue(prefix.toString());
        return;
    }
    char c = pattern.charAt(d);
    if (c == '.') {
        for (char ch = 0; ch < R; ch++) {
            prefix.append(ch);
            collect(x.next[ch], prefix, pattern, out);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    } else {
        prefix.append(c);
        collect(x.next[c], prefix, pattern, out);
        prefix.deleteCharAt(prefix.length() - 1);
    }
}

Dot不是zero-or-more regex operator；它必须消费exactly one character，所以result length等于pattern length。若pattern尚未耗尽却看到val，不能提前输出shorter key；若pattern已耗尽，也不能继续收集longer descendants。

Wildcard worst case会探索大量branches，output-sensitive或pattern selectivity比单一K bound更有意义。若pattern全是dots且length较长，visited states接近对应depth的whole trie frontier。

5.2.5 Longest prefix：记录最近一次word boundary

longestPrefixOf(query)用于routing与autocomplete boundary。它沿query characters走唯一path，同时维护 length：每到一个val非null node，就把length更新为当前depth；遇null link或query结束，返回最后记录的length。

private int longestPrefixOf(Node x, String query, int d, int length) {
    if (x == null) return length;
    if (x.val != null) length = d;
    if (d == query.length()) return length;
    char c = query.charAt(d);
    return longestPrefixOf(x.next[c], query, d + 1, length);
}

查询 shellsort 时，path可能经过 she、shell、shells 三个boundaries；最终link在 shells 之后断开，answer必须是最后boundary shells，而不是visited path最长prefix。若从未遇到value，返回null而不是empty string，除非API允许empty key且root本身有value。

IP routing的longest-prefix match与此同构：bits或address segments作为characters，沿destination address前进，最后一个有route value的node就是most specific route。

5.2.6 Delete：清word boundary与剪subtrie是两件事

Lazy delete只把terminal value设null并减少size；所有path nodes保留。Eager delete完成相同语义后回溯：若node val非null或任一child非null，必须保留；只有val null且全部children null才返回null让parent剪link。

private Node delete(Node x, String key, int d) {
    if (x == null) return null;
    if (d == key.length()) {
        if (x.val != null) n--;
        x.val = null;
    } else {
        char c = key.charAt(d);
        x.next[c] = delete(x.next[c], key, d + 1);
    }
    if (x.val != null) return x;
    for (int c = 0; c < R; c++)
        if (x.next[c] != null) return x;
    return null;
}

删除 shell 不能删掉 she boundary，也不能删掉 shells 的continuation。Eager pruning criterion必须同时检查current value与all children；只看current value会把共享prefix整个剪掉。

Lazy delete降低mutation cost但积累dead nodes；eager delete回收空间但每层可能scan R links。Workload中delete很少时lazy可接受，长期动态dictionary则需监控live/dead node ratio。

5.2.7 Ternary search tries：三个links换掉R-sized child array

三向单词查找树（ternary search tries，TST）把R-way node的character-indexed array替换成一个character BST：

  • key character小于node.c：走left，digit不变。
  • key character大于node.c：走right，digit不变。
  • 相等且key未结束：走middle，digit加一。
  • 相等且key结束：读取或写入terminal value。
private Node<Value> put(Node<Value> 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;
}

最常见错误是在left/right branch也执行d+1；那会在尚未找到matching character前就消费input，破坏path semantics。只有middle表示current character已匹配。

Bentley-Sedgewick property指出：对固定input key set，TST node数量与insertion order无关，因为每个distinct nonempty prefix贡献一个对应character node；但left/right的相对shape会随insertion order改变，进而影响character comparison count。Node count invariant不等于performance invariant。

TST通常每node只存3 links，空间远小于large-R dense trie；代价是每个digit可能做多次left/right character comparisons。Randomization、balanced variants或careful insertion order可改善sibling BST shape。

5.2.8 Space与alphabet engineering

若M是nodes数量、pointer size为p，忽略object headers与values，dense R-way与TST child links量级分别是：

SR−way≈MRp,STST≈3MpS_{\mathrm{R-way}}\approx M R p, \qquad S_{\mathrm{TST}}\approx 3 M p

R=256时差距显著；若R=4且keys密集，R-way direct indexing非常合适。Real implementation还可用sorted child vectors、hash maps、adaptive nodes、path compression或compressed radix tree，在lookup comparisons与memory间取折中。

Alphabet contract必须与5.1一致。Direct next[c]只适合c已映射到0至R-1；把arbitrary UTF-16 char直接索引R=256 array会越界。Production trie应先normalize并encode symbols，或用map-based children。

5.2.9 Applications：结构能力比“更快的Map”更重要

Autocomplete先 keysWithPrefix(userInput)，可加frequency ranking；T9把每个digit映射到多个letters，等价于每层受限wildcard branching；spell checking用exact contains；routing用longestPrefixOf；substring reporting可把每个dictionary word的suffixes插入TST，将substring query转成prefix query，但空间会增加。

Trie适合shared-prefix-heavy dictionaries，但不是无条件替代hashing。Exact-only workload、long random keys、large sparse alphabet且memory敏感时，hash table可能更简单。需要ordered iteration、prefix、wildcard与longest-prefix时，trie API避免了全表scan或复杂range boundary。

5.2.10 Independent certificate：从terminal set反推结构

验收trie不能只检查 size 或随机几个get：

  1. DFS enumerate所有val非null nodes，结果multiset应等于expected keys。
  2. 每个terminal key的每个prefix node必须存在，edge character与depth一致。
  3. Exact get的返回value与terminal set一致；internal nonterminal prefixes不得误报。
  4. Eager mode中，每个non-root node都应至少被一个terminal key使用；lazy mode则单独统计dead nodes。
  5. Prefix、wildcard、longest-prefix results与简单reference filter逐query对照。

R-way child link certificate是“index c的edge消费character c”；TST certificate则是left characters小于node.c、right大于node.c、middle消费相等character。两种representation不能共用一套模糊的“像树就对”检查。

5.2.11 逐步运行路线

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“5.2 · Tries”的两个最小情境间切换，再逐项选择正式概念。预测“查找长度为 W 的键访问 O(W) 个字符位置；空间由节点数与分支表示共同决定”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

5.2 · Tries：对象、操作与不变量

用 R 向单词查找树和三向单词查找树支持字符串符号表、前缀与通配查询

选择最小情境

切换正式概念

输入合同操作证书algs4-5.2 · 先给前提，再执行，再验收当前概念：1/6
前缀键
同时插入 she 与 shells，再删除 she
当前观察
tries：只清除 she 的值，保留通向 shells 的后继节点
查找长度为 W 的键访问 O(W) 个字符位置；空间由节点数与分支表示共同决定

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

  • 单词查找树：在实验 1 中指出对应状态，并写出一个通过条件。
  • 字符串符号表：在实验 2 中指出对应状态，并写出一个通过条件。
  • R向单词查找树：在实验 3 中指出对应状态，并写出一个通过条件。
  • 三向单词查找树：在实验 1 中指出对应状态，并写出一个通过条件。
  • 前缀与通配操作：在实验 2 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“查找长度为 W 的键访问 O(W) 个字符位置；空间由节点数与分支表示共同决定”不是孤立结论？

问题 3：故障恢复。 怎样证明“删除前缀键时把仍有孩子的节点一并剪掉，或用 null 值混淆键缺失与显式空值”已经修复？

小结

  • Tries让每个node代表prefix；node存在不等于key存在，non-null value才是word boundary。
  • R-way tries以character直接索引R links，get/put成本与key length成正比，但dense memory为M乘R级。
  • Prefix query定位subtrie后collect；wildcard在dot处展开branches；longest-prefix记录最近一次terminal boundary。
  • Delete先清value，再决定是否eager prune；共享prefix只要有value或child就必须保留。
  • Ternary search tries用left/middle/right三个links降低空间，只有character相等走middle时才推进digit。
  • Independent certificate从enumerated terminal set、prefix paths和representation invariants证明结构正确。

资料与写作方式声明

本章以Algorithms, Fourth Edition的合法公开试读核定可见范围，并以目录限定未公开部分，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…