数据结构与算法 第十二章高级树结构 任课教员:张铭 http://db.pku.edu.cn/mzhang/ds zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究
数据结构与算法 第十二章 高级树结构 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究
主要内容 12.1Trie和 Patricia结构 12.2改进的BST 最佳二叉搜索树 Ⅵ树 伸展树 123空间树结构 12.4决策树和博弈树 北京大学信息学院 张铭编写⊙版权所有,转载或翻印必究 Page 2
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 2 主要内容 12.1 Trie和Patricia 结构 12.2 改进的BST 最佳二叉搜索树 AVL树 伸展树 12.3 空间树结构 12.4 决策树和博弈树
12.1Trie结构和 Patricia树 引子:BST(二叉搜索树)不是平衡的树 n树结构与输入数据的顺序有很大的关系 输入顺序:7、5、4、6、8 输入顺序:4、5、6、7、8 北京大学信息学院 张铭编写⊙版权所有,转载或翻印必究 Page 3
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 3 12.1Trie结构和Patricia树 引子：BST（二叉搜索树）不是平衡的树 树结构与输入数据的顺序有很大的关系 4 5 6 7 8 7 5 8 4 6 输入顺序: 4、5、6、7、8 输入顺序: 7、5、4、6、8
Trie结构 关键码对象空间分解 “rie”这个词来源于“ retrieval 主要应用 信息检索( information retrieva) n自然语言大规模的英文词典 二叉Trie树 用每个字母的二进制编码来代表 编码只有0和1 北京大学信息学院 张铭编写⊙版权所有,转载或翻印必究 Page 4
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 4 Trie结构 关键码对象空间分解 “trie”这个词来源于“retrieval” 主要应用 信息检索（information retrieval） 自然语言大规模的英文词典 二叉Trie树 用每个字母的二进制编码来代表 编码只有0和1
二叉Trie结构 元素为2、5、9、17、41、45、63 0(<32) 1(>32) 0(<16) l(>16) 1(48) 0(<8) 1(>8) 0(<48) 17 1(40)63 0(<4) 1(>4) 9 0(<44 1(>44) 41 45 北京大学信息学院 张铭编写⊙版权所有,转载或翻印必究 Page 5
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 5 二叉Trie结构 元素为2、5、9、17、41、45、63 0(<32) 1(>32) 0(<16) 1(>16) 0(<8) 0(<4) 1(>48) 1(>8) 1(>4) 2 5 9 17 41 1(>40) 63 45 0(<44) 1(>44) 0(<48)