第十二章高级树结构 任课教员:张铭 http://db.pku.edu.cn/mzhang/dsl zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究
第十二章 高级树结构 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究
主要内容 12.1Trie和 Patricia结构 12.2改进的BST 最佳二叉搜索树 AⅥL树 伸展树 12.3空间树结构 12.4决策树和博弈树 北京大学信息学院 @版权所有,转载或翻印必究 Page 2
北京大学信息学院 ©版权所有，转载或翻印必究 Page 2 主要内容 ◼ 12.1 Trie和Patricia 结构 ◼ 12.2 改进的BST ◼ 最佳二叉搜索树 ◼ AVL树 ◼ 伸展树 ◼ 12.3 空间树结构 ◼ 12.4 决策树和博弈树
12.1Trie结构和 Patricia树 ■BST(二叉搜索树)不是一棵平衡的树,它的树结构 与输入数据的顺序有很大的关系 输入顺序为4、5、6、7、8 输入顺序为7、5、4、6、8 北京大学信息学院 @版权所有,转载或翻印必究 Page 3
北京大学信息学院 ©版权所有，转载或翻印必究 Page 3 12.1Trie结构和Patricia树 ◼ BST（二叉搜索树）不是一棵平衡的树，它的树结构 与输入数据的顺序有很大的关系
对象空间( object space)分解 BST是一种组织上基于对象空间 ( object space)分解的数据结构 空间分解是存储在树中的对象(关键 码值)决定 最简单的方法就是对对象(这里是 关键码)的范进行划分 平均划分 按照某种方式不平均划分 北京大学信息学院 @版权所有,转载或翻印必究 Page 4
北京大学信息学院 ©版权所有，转载或翻印必究 Page 4 对象空间( object space )分解 ◼ BST是一种组织上基于对象空间 ( object space )分解的数据结构 ◼ 空间分解是存储在树中的对象（关键 码值）决定 ◼ 最简单的方法就是对对象（这里是 关键码）的范围进行划分 ◼ 平均划分 ◼ 按照某种方式不平均划分
假设划分因子为2 每次仅把当前范围分为两部分 (对应于二叉树) 在进行插入的时候,只要是小于结 点的关键码的都在左子树中 只要是大于结点的关键码的都在右 子树中 北京大学信息学院 @版权所有,转载或翻印必究 Page 5
北京大学信息学院 ©版权所有，转载或翻印必究 Page 5 ◼ 假设划分因子为2 ◼ 每次仅把当前范围分为两部分 （对应于二叉树） ◼ 在进行插入的时候，只要是小于结 点的关键码的都在左子树中 ◼ 只要是大于结点的关键码的都在右 子树中