北京大学：《数据结构与算法》课程教学资源（实验班PPT课件）第十二章 高级树结构

数据结构与算法 第十二章高级树结构 任课教员:张铭 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