知识卡片

普通读书笔记卡 · 3566.d.1

基数树以路径表示键前缀

理解等级:中级

基数树(trie)用逐位分支表示位串:第 i 层按第 i 位选左或右,路径本身确定键,内部节点可只用于连接而非存储键。

它适合按公共前缀组织字符串;本章 Θ(n) 字典序排序是问题要求证明的目标,不把它误写成已证结论。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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.