主要内容
第十二章高级树结构 任课教员:张铭、赵海燕、冯梅萍、王腾蛟 doc.guandang.net北京大学信息科学与技术学院网络与信息系统研究所©版权所有,转载或翻印必究
12.1 Trie和Patricia结构 12.2改进的BST
最佳二叉搜索树 AVL树伸展树
12.3空间树结构 12.4决策树和博弈树 ©版权所有,转载或翻印必究 Page 2
北京大学信息学院
12.1Trie结构和Patricia树
对象空间( object space )分解
BST(二叉搜索树)不是一棵平衡的树,它的树结构与输入数据的顺序有很大的关系 输入顺序为 4、5、6、7、8 4 5 6 7 8 输入顺序为 7、5、4、6、8
BST是一种组织上基于对象空间 ( object space )分解的数据结构
7
空间分解是存储在树中的对象(关键码值)决定
5 4 6 8
最简单的方法就是对对象(这里是关键码)的范围进行划分
平均划分按照某种方式不平均划分 ©版权所有,转载或翻印必究 Page 4
北京大学信息学院
©版权所有,转载或翻印必究
Page 3
北京大学信息学院
关键码空间(key space)分解
假设划分因子为2
不依赖于关键码的插入顺序树的深度受到关键码精度的影响
每次仅把当前范围分为两部分 (对应于二叉树) 在进行插入的时候,只要是小于结点的关键码的都在左子树中 只要是大于结点的关键码的都在右子树中
最坏的情况下,深度等于存储关键码所需要的位数
例如,如果关键码是0到255之间的整数,那么关键码的精度就是8个二进制位。
如果有两个关键码:10000010和10000011,它们的前面7位都是相同的所以直到第8次划分才能将这两个关键码分开这样的搜索树深度也为8,但这是最坏的情况
北京大学信息学院
©版权所有,转载或翻印必究
Page 5
北京大学信息学院
©版权所有,转载或翻印必究
Page 6

第十二章 高级树结构任课教员:张铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ?版权所有,...
第十二章 高级树结构任课教员:张铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ?版权所有,...
第十二章 高级树结构任课教员:张铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ?版权所有,...
压缩的数据库: FP-tree 结构 ? 无需重复扫描整个数据库 1)在挖掘频繁模式时,它需要递归地生 成条件FP-树,并且每产生一个频繁模式 就要生成一个条件FP-树。 ...
数据结构 08 高级搜索树_互联网_IT/计算机_专业资料。8.高级搜索树 (a)?伸展树 我要一步一步往上爬 在最高点乘着叶片往前飞 ——《蜗牛》?周杰伦 邓俊辉 ...
几种特殊的树结构_计算机软件及应用_IT/计算机_专业资料。Jsoi2011 秋季函授 A...End; 作业说明:1、本讲函授时间为 1 个月; 2、请结合高级本、高级本习题第...
基于结构语义树的高级控制结构恢复技术_专业资料。针对高级控制结构嵌套关系难以恢复的问题,提出了一种基于结构语义树的高级控制结构恢复技术。以经典控制流图结构化算法...
树的结构是怎样的 2页 1下载券 各种树结构 22页 1下载券 高级树结构 232页...写出中序遍历二叉树的递归和...
数据结构 第9章:B-树 44页 1下载券 数据结构第十二章 高级树... 232页 ...高级数据结构-B+树 暂无评价
热门文档