【12.4】高级数据结构--Trie 树

  • 理想状况:插入、删除、查找时间代价为 O( logn )
  • 输入 9, 4, 2, 6, 7, 15, 12, 21
  • 输入 2, 4, 6, 7, 9, 12, 15, 21

一、Trie 结构

  • 关键码对象空间分解
  • “trie”这个词来源于“retrieval”
  • 主要应用

    • 信息检索 (information retrieval)
    • 自然语言大规模的英文词典
  • 字符树——26叉Trie

  • 二叉Trie树

    • 用每个字母(或数值)的二进制编码来代表
    • 编码只有0和1

二、英文字符树——26叉Trie

不等长的字符树,加“*”标记。

存储单词 an, and, ant, bad, bee

压缩靠近叶结点的单路径

存储单词 an, and, ant, bad, bee

三、二叉 Trie 结构

元素为 2、5、9、17、41、45、63

四、后缀树 (Suffix Trees)

ababc 后缀子串: ababc, babc, abc, bc, c

后缀数组 (Suffix Array)

四、思考

  • 中文是否适合组织字符树?是否适合 二叉 Trie 结构?
  • 查阅后缀树、后缀数组的文献,思考 其应用场景。

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学