【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