一条成功路径证明什么?
Trie 节点代表从根沿路径读出的前缀。到达节点只证明路径存在,并不证明该前缀本身是已存储键值;另一个终止标记才回答第二个问题。例如在字典 a, an, ant, ante, bat, bath, bats 中,ba 是多个键值的开头,所以路径存在,但 ba 本身没有存储。
前一节介绍了表示法与删除;这里逐步追踪查找和补全,让每个中间状态的意思清楚可见。
定义 7.2.1
(精确查找与前缀补全)
设 为已存储键值的集合, 为查询字符串。精确查找问的是 是否成立。前缀补全问的是所有以 为前缀的键值 ,即对某个字符串 (可以为空)有 。因此与 相等的键值也是 的补全。
阅读时保持不变量
若查询 的前 条边均存在,消耗 个字符后,当前节点恰好代表 。起初 ,当前节点是根;若下一条边存在,走过它便同时令路径及已消耗前缀增加一个字符。若边不存在,就没有已存储键值可以整个查询为前缀:任何以完整查询开头的键值都需要这条缺失的边。
精确查找消耗所有字符后,还要检查终止标记。ba 的两条边存在,但标记为假,所以答案是“不是键值”。an 即使有后代,标记仍为真。节点可以同时是一个完整单词及较长单词的开头。
前缀补全先找到查询节点;若存在,就枚举其子树中的终止节点,当该节点本身终止时也要包括它。ba 的补全是 bat、bath、bats。每个输出键值的路径都经过查询节点,因此具有所求前缀;每个具有该前缀的已存储键值也必在其下方的终止节点结束,所以完整遍历会找到它。
概念视角算法
补全是排序键值中的一段
把键值按字典序排列,则以 为前缀的键值恰好组成连续的一段;若这一段非空,它由第一个不小于 的键值开始。先用二分查找找出这个键值,再在前缀仍然匹配时向后扫描,所得的补全与 trie 相同。对上面词典中的 ba,查找落在第五个键值 bat,扫描输出 bat、bath、bats;对 bad,查找落在 bat,它没有这个前缀,所以这一段为空。
定理 7.2.2
(Trie 查找与补全的正确性)
设某个 trie 以标准形式表示已存储键值的集合 ,意思是它的非根节点恰好是已存储键值的非空前缀,并且节点为终止,当且仅当其字符串已存储。设 为查询字符串。若搜索 时遇到缺失的边,则 中没有以 为前缀的键值。否则搜索终止于 的节点,精确查找回答“是”,当且仅当该节点为终止,也就是当且仅当 。前缀补全恰好输出 中以 为前缀的键值,每个一次。
证明
(从两个方向读取路径)
设搜索遇到缺失的边。反设某个已存储键值以完整查询开头,它的路径便必须包含查询的每条边,包括搜索报告为缺失的边,矛盾。这证明没有补全,特别是 。
若没有缺失的边,不变量说明搜索终止于代表 的节点。在标准 trie 中,该节点为终止,当且仅当 是成员,所以终止标记决定精确查找的结果。
对于补全,每个输出的键值都是查询节点子树中某个终止节点的字符串,所以它的路径经过该节点,并以 为前缀。反过来,以 为前缀的已存储键值,其路径经过查询节点,并在其下方的终止节点或节点本身结束,所以完整遍历子树会到达并输出它。每个节点只被访问一次,所以每个键值只输出一次。
证明透视
为何缺失的边就能决定整个查询
这个论证在同一个结构上朝两个方向进行。已存储键值必有完整路径,因为插入会建立键值的每条边。这使缺失的边具有决定性:证明取一个假设以查询开头的键值并读出它的路径,而不是搜遍所有键值。反过来,终止标记恰好为已存储键值而设,所以路径成功之后,由标记决定成员关系。
两项事实都来自标准形式。若先前的剪枝移除了某个已存储键值仍需要的边,缺失边的结论就不再成立。路径成功走完的结论与缺失边不同:它建立了前缀,之后决定成员关系的是标记,而不是路径。
反例模式
到达节点并不证明键值已存储
一条诱人的规则是:若搜索消耗了 的每个字符而没有遇到缺失的边,则 已存储。在字典 a, an, ant, ante, bat, bath, bats 中,查询 ba 消耗两个字符并到达节点 ba,但 ba 不在七个键值之中,其终止标记为假。规则失败,是因为该节点只是 bat、bath、bats 的前缀。补救办法是在路径成功后检查终止标记。
反过来的直觉也不成立:有后代的节点并不因此不是键值。节点 an 有后代 ant 与 ante,其标记为真,所以 an 已存储。
例题 7.2.3
(三次精确查找)
取字典 a, an, ant, ante, bat, bath, bats。根以下的节点是 a、an、ant、ante、b、ba、bat、bath、bats,其中终止的是 a、an、ant、ante、bat、bath、bats。
查找 ba:边 b 与 a 都存在,标记为假,所以 ba 不是键值。查找 an:边都存在,标记为真,所以 an 是键值,虽然该节点有子节点。查找 bad:搜索到达 ba,但没有边 d,所以 bad 不是键值,而且缺失的边也说明没有键值以 bad 开头。
例题 7.2.4
(两次前缀补全)
对查询 ba,查询节点不是终止,所以不为它输出任何东西。其子树有子节点 bat,它是终止,最先输出;在 bat 之下,按字母次序访问子节点 h 与 s,先后输出 bath、bats。补全是 bat、bath、bats。
对查询 an,查询节点是终止,最先输出。接着其子节点 ant 是终止,其下的 ante 也是终止。补全是 an、ant、ante。键值 a 不是 an 的补全,因为 a 并不以 an 为前缀。
例题 7.2.5
(边界情形:空查询与越过叶节点的查询)
空查询不消耗任何边,停在根。这个字典不含空字符串,所以根不是终止,精确查找回答“否”。作为前缀,空字符串匹配每个键值,所以补全输出全部七个键值,顺序为 a、an、ant、ante、bat、bath、bats。
再看查询 batss。字符 b、a、t、s 沿现有的边走,到达节点 bats。该节点没有子节点 s,所以搜索遇到缺失的边:batss 不是键值,也没有补全。
说清楚计算什么工作
命题 7.2.6
(查找与补全的代价)
假设每次子节点查找为常数时间,并且可以按每个现有子节点常数代价枚举一个节点的子节点。对长度为 的查询,精确查找至多用 次子节点查找,时间为 。若查询节点存在,其子树有 个节点,而输出的键值共有 个字符,补全需要 时间。
证明
(先沿查询前进,再访问子树)
搜索每次子节点查找消耗一个查询字符,在第一条缺失的边或消耗 个字符后停止,所以至多作 次查找,再读取一个标记。补全接着以常数代价访问子树的 个节点各一次,每个现有子节点再花常数代价;含 个节点的子树有 条边,所以合计 。写出输出的键值花费 。
常见错误
(把整个补全称为 )
沿查询前进是 ,但补全接着可能访问大片子树并输出许多字符串。上述字典中查询 a 的长度是 1,却输出四个键值,所以代价不只取决于 。没有额外限制就把整个枚举称为 会造成误解。
常见错误
(以为空查询的两个答案必须一致)
空查询不消耗边,搜索停在根。精确查找为真恰好当根有终止标记,即曾存储空字符串。作为前缀,空字符串匹配每个已存储键值。这两个答案不必相同,上述字典就是例子:查找回答“否”,补全却列出七个键值。
自我检查
快速检查
(查找 bad 到达 ba 后发现缺少 d 边,badger 能否已存储?)
想一想 badger 需要的路径。
解答 · 答案
不能;它的路径会需要缺失的 d 边。
快速检查
(在任意字典中,若 an 终止且有子节点,ant 一定已存储吗?)
有子节点,是否就知道子节点是哪个字母?
解答 · 答案
不。单有子节点不能证明完整 ant 路径存在,也不能证明终点有终止标记。例如若 an 唯一的子节点是 g,字典可能含有 ang 而没有 ant。
快速检查
(在字典 a, an, ant, ante, bat, bath, bats 中,ante 的补全是什么?)
查询节点是否终止?它有没有子树?
解答 · 答案
只有 ante 本身。查询节点是终止,所以它被输出;它没有子节点,所以不再输出其他东西。