【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 结构?
• 查阅后缀树、后缀数组的文献，思考 其应用场景。

参考资料

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