知识卡片
基数树以路径表示键前缀
基数树(trie)用逐位分支表示位串:第 i 层按第 i 位选左或右,路径本身确定键,内部节点可只用于连接而非存储键。
它适合按公共前缀组织字符串;本章 Θ(n) 字典序排序是问题要求证明的目标,不把它误写成已证结论。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第12章 二叉搜索树 · 查看原书依据
ap, go left at a node of depth i if ai = 0 and right if ai = 1.
参考来源
- 位置:《算法导论(第4版)》第 12 章问题 12-2(`OEBPS/chapter012.xhtml`,文本字符 [25000, 30000);图 12.5、Art_P420)。
- 结论依据:问题 12-2 按位串第 i 位决定深度 i 节点的左右分支;图 12.5 注明节点键由根到节点路径确定、连接节点可不存键;Θ(n) 字典序排序是题目要求证明的目标。
- 原始内容:When searching for a key a = a 0 a 1 … a p , go left at a node of depth i if a i = 0 and right if a i = 1.