数据结构与算法 第十二章高级树结构 任课教员:张铭 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) 0(16) 1(48) 0(8) 0(4) 9 0(44) 41 45 北京大学信息学院 张铭编写⊙版权所有,转载或翻印必究 Page 5
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 5 二叉Trie结构 元素为2、5、9、17、41、45、63 0(32) 0(16) 0(48) 1(>8) 1(>4) 2 5 9 17 41 1(>40) 63 45 0(44) 0(<48)
英文字符树26叉Trie 存单词and、ant、bad、be an”子树代表具有 相同前缀an-的关 a 键码集合{and, ant a e d d and ant bad be 一棵子树代表具有相同前缀的关键码的集合 北京大学信息学院 张铭编写⊙版权所有,转载或翻印必究 Page 6
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 6 英文字符树——26叉Trie 一棵子树代表具有相同前缀的关键码的集合 存单词 and、ant、bad、bee a n d t b a d e e and ant bad bee “an”子树代表具有 相同前缀an-的关 键码集合{and， ant}
字符树的改进(续) 存储单词an、 and ant bad bee e bad bee d ant 北京大学信息学院 张铭编写⊙版权所有,转载或翻印必究 Page 7
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 字符树的改进（续） 存储单词an、and、ant、bad、bee a n d t b a e and ant bad bee an *
Trie字符树的特点 Trie结构也不是平衡的 nt子树下的分支比z子树下的多 26个分支因子庞大的26叉树 北京大学信息学院 张铭编写⊙版权所有,转载或翻印必究 Page 8
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 8 Trie字符树的特点 Trie结构也不是平衡的 t子树下的分支比z子树下的多 26个分支因子——庞大的26叉树
PATRICIA结构 "Practical Algorithm To Retrieve Information Coded In Alphanumeric' D Morrision发明的Trie结构变体 根据关键码二进制位的编码来划分 二叉Trie树 北京大学信息学院 张铭编写⊙版权所有,转载或翻印必究 Page 9
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 PATRICIA 结构 “Practical Algorithm To Retrieve Information Coded In Alphanumeric” D.Morrision发明的Trie结构变体 根据关键码二进制位的编码来划分 二叉Trie树
PATRICIA结构图 Xxxxx xxxxx OOxxxx Olxxxx 1Oxxx ixxxx 00Oxxx 0Olxxx lxxx 1010x 101lxx 0000xx 0001x 5 编码:2:0000105:0001019:001001 17:01000141:10100145:10110163:111lll 北京大学信息学院张铭编写@版权所有,转载或翻印必究 age 10
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 PATRICIA 结构图 101xxx 10xxxx 0000xx 001xxx 0001xx 编码： 2：000010 5：000101 9：001001 17：010001 41：101001 45：101101 63：111111 0 1 1 2 2 3 0xxxxx 1xxxxx 00xxxx 01xxxx 11xxxx 000xxx 2 5 9 17 41 63 3 1010xx 1011xx 45