第十二部分高级树结构教学课件.ppt
《第十二部分高级树结构教学课件.ppt》由会员分享,可在线阅读,更多相关《第十二部分高级树结构教学课件.ppt(232页珍藏版)》请在三一文库上搜索。
1、第十二章 高级树结构,任课教员:张 铭 http:/ 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究,北京大学信息学院 版权所有,转载或翻印必究 Page 2,主要内容,12.1 Trie和Patricia 结构 12.2 改进的BST 最佳二叉搜索树 AVL树 伸展树 12.3 空间树结构 12.4 决策树和博弈树,北京大学信息学院 版权所有,转载或翻印必究 Page 3,12.1Trie结构和Patricia树,BST(二叉搜索树)不是一棵平衡的树,它的树结构与输入数据的顺序有很大的关系,北京大学信息学院 版权所有,转载或翻印必究 Page 4,对象空间( o
2、bject space )分解,BST是一种组织上基于对象空间( object space )分解的数据结构 空间分解是存储在树中的对象(关键码值)决定 最简单的方法就是对对象(这里是关键码)的范围进行划分 平均划分 按照某种方式不平均划分,北京大学信息学院 版权所有,转载或翻印必究 Page 5,假设划分因子为2 每次仅把当前范围分为两部分(对应于二叉树) 在进行插入的时候,只要是小于结点的关键码的都在左子树中 只要是大于结点的关键码的都在右子树中,北京大学信息学院 版权所有,转载或翻印必究 Page 6,关键码空间(key space)分解,不依赖于关键码的插入顺序 树的深度受到关键码精度
3、的影响 最坏的情况下,深度等于存储关键码所需要的位数 例如,如果关键码是0到255之间的整数,那么关键码的精度就是8个二进制位。 如果有两个关键码:10000010和10000011,它们的前面7位都是相同的 所以直到第8次划分才能将这两个关键码分开 这样的搜索树深度也为8,但这是最坏的情况,北京大学信息学院 版权所有,转载或翻印必究 Page 7,基于关键码范围的分解 保证平衡吗? 显然是不行的 如果关键码的分布得很不均衡,将导致树的结构失衡 一种极端的情况,导致所有的关键码都小于根结点,那么以该结点为根的子树的右子树将没有任何的元素,北京大学信息学院 版权所有,转载或翻印必究 Page 8
4、,Trie结构,基于关键码分解的数据结构,叫作Trie结构 “trie”这个词来源于“retrieval” 主要应用 信息检索(information retrieval) 用来存储英文字符串,尤其大规模的英文词典 自然语言理解系统中经常用到,北京大学信息学院 版权所有,转载或翻印必究 Page 9,Trie结构的适用情况,Trie结构主要基于两个原则 有一个固定的关键码集合 对于结点的分层标记 如果所有的元素都可以使用数字或者字母等来标记,那么就可以考虑使用Trie结构 例如,元素可以用0-9的数字来标记 在根结点的地方,它分出10个子结点,分别标记0-9 然后每个子结点又可以分出10个结点
5、 如此下去直到所有的元素都能够被区分开,北京大学信息学院 版权所有,转载或翻印必究 Page 10,Trie结构特点,与B+树一样,基于关键码空间分解的树结构,其内部结点仅作为占位符引导检索过程,数据纪录只存储在叶结点中 Huffman编码树( Huffman coding tree )也是一种二叉Trie树,北京大学信息学院 版权所有,转载或翻印必究 Page 11,Trie结构示意图,北京大学信息学院 版权所有,转载或翻印必究 Page 12,Trie结构 应用:“字符树”,存储字典里面的单词 英文的单词是有26个字母组成的(简单起见,我们忽略大小写), 英文字符树每一个内部结点都有26个
6、子结点 树的高度为最长字符串长度,北京大学信息学院 版权所有,转载或翻印必究 Page 13,英文字符树,一棵子树代表具有相同前缀的关键码的集合。例如“an”子树代表具有相同前缀an-的关键码集合and,ant,北京大学信息学院 版权所有,转载或翻印必究 Page 14,字符树的改进,由于单词可能不等长 ,所以更好的存储是其内部结点不存储单词信息,只有叶结点才存储单词信息,北京大学信息学院 版权所有,转载或翻印必究 Page 15,字符树的改进(续),观察上图中的bad和bee两个单词,它们的父结点都只有一个儿子就是它们自己,也就是说,实际上它们在父结点的时候就已经被区分开了 因为我们真正想做
7、的是要检索每一个单词,不需要在已经能够区分每个单词的情况下继续进行分裂结点的动作,北京大学信息学院 版权所有,转载或翻印必究 Page 16,字符树的改进(续),北京大学信息学院 版权所有,转载或翻印必究 Page 17,字符树中的检索,首先用待查关键码的第一个字符与树林的各个根的字符相比较 然后下一步的检索在前次比较相等的那棵树上进行其中,用待查关键码的第二个字符与选定的这棵树的根的各个子结点进行比较, 接着再沿着前次比较相等的分支进行进一步的检索 . 直到进行到某一层,该层所有结点的字符都与待查关键码相应位置的字符不同,这说明此关键码在树目录里没有出现; 若检索一直进行到树叶,那么就在树目
8、录里找到了给定的关键码,北京大学信息学院 版权所有,转载或翻印必究 Page 18,Trie字符树的缺陷,Trie结构显然也不是平衡的 在它存取英文单词的时候,显然t子树下的分支比z子树下的分支多很多(以t开头的单词比以z开头的单词多很多) 而且,每次有26个分支因子使得树的结构过于庞大,给检索也带来了不便 字母在计算机中是以二进制ASCII码的形式存储的 使用每个字母的二进制编码来代表这个字母 关键码就只有编码0和1 而不是a到z的26个字母 二叉Trie树,北京大学信息学院 版权所有,转载或翻印必究 Page 19,Trie树的插入,Trie树的插入 首先根据插入纪录的关键码找到需要插入的
9、结点位置 如果该结点是叶结点,那么就将为其分裂出两个子结点,分别存储这个纪录和以前的那个纪录 如果是内部结点,则在那个分支上应该是空的,所以直接为该分支建立一个新的叶结点即可,北京大学信息学院 版权所有,转载或翻印必究 Page 20,Trie树的删除,Trie树的删除 根据插入纪录的关键码找到需要删除的结点位置 如果一个被删除结点的父结点没有其他的儿子,那么就需要合并 否则只需要将此分支设置为空即可,北京大学信息学院 版权所有,转载或翻印必究 Page 21,PATRICIA 结构,为了得到更加平衡的结构,D.Morrision发明了Trie结构的一种变体PATRICIA “Practica
10、l Algorithm To Retrieve Information Coded In Alphanumeric” 它不是对整个关键码大小范围的划分 而是根据关键码每一个二进制位的编码来划分 因为每一位要么是0,要么是1,所以分支因子是2, 生成的树是二叉树,北京大学信息学院 版权所有,转载或翻印必究 Page 22,PATRICIA 结构图,北京大学信息学院 版权所有,转载或翻印必究 Page 23,PATRICIA 结构图(续),上图因为最大的数是63,用6位二进制表示即可 每一个结点都有一个标号,表示它是在比较第几位,然后根据那一位是0还是1来划分左右两个子树 标号为2的结点的右子树一
11、定是编码形式为xx1xxx (x表示该位或0或1,标号为2说明比较第2位) 在图中检索5的话,5的编码为000101 首先我们比较第0位,从而进入左子树 然后在第1位仍然是0,还是进入左子树 在第2位还是0,仍进入左子树 第3位变成了1,从而进入右子树,就找到了位于叶结点的数字5,北京大学信息学院 版权所有,转载或翻印必究 Page 24,PATRICIA 结构图改进,观察PATRICIA的图发现有与Trie图类似的情况 在区分2和5、41和45的时候,在第三个二进制位的比较是不能区别它们的 可以将它省略,得到一棵更为简洁的树,北京大学信息学院 版权所有,转载或翻印必究 Page 25,PAT
12、RICIA 结构图改进(续),北京大学信息学院 版权所有,转载或翻印必究 Page 26,PATRICIA的特点,每个内部结点都代表一个位的比较,必然产生两个子结点 所以它是一个满二叉树 进行一次检索,最多只需要关键码位数次的比较即可,北京大学信息学院 版权所有,转载或翻印必究 Page 27,12.2二叉树结构的改进,平衡的二叉搜索树、伸展树和最佳二叉排序树,它们都是对二叉树的结构或者操作规则做部分的改进以使树保持在一种类似于平衡的状态,从而达到较好的效率,北京大学信息学院 版权所有,转载或翻印必究 Page 28,12.2.1最佳二叉搜索树,根据前面章节的二叉树介绍我们知道对应于关键码集合
13、K:K=xal, wan, wil, zol, yo, xul, yum, wen, wim, zi, yon, xem, wul, zom的二叉排序树,北京大学信息学院 版权所有,转载或翻印必究 Page 29,二叉搜索树的多样性,同一个关键码集合,其关键码插入二叉搜索树的次序不同,就构成不同的二叉搜索树。 包括n个关键码的集合中,关键码可以有n!种不同的排列法,因此可以构成n!个二叉搜索树(其中有相同的) 可以用检索效率来衡量二叉搜索树,北京大学信息学院 版权所有,转载或翻印必究 Page 30,如果只计算不同的搜索树,则排列2,1,3的顺序插入关键码与按照排列2,3,1的顺序插入所构成的
14、二叉搜索树完全相同 这种非前序排列的序列,总是可以找到与其相对应的一个合法前序排列 这n!种排列中, 只有 就是说n个结点可以构造 称为Catalan函数,北京大学信息学院 版权所有,转载或翻印必究 Page 31,扩充的二叉树,第4章讨论过扩充的二叉树的概念。扩充的二叉树是满二叉树,新增加的空树叶(以下称为外部结点)的个数等于原来二叉树的结点(以下称为内部结点)个数加1 在扩充的二叉搜索树里,关键码值最小的内部结点的左子女(外部结点)代表了值小于该内部结点的可能关键码的集合;关键码值最大的内部结点的右子女(外部结点)代表了值大于该内部结点的可能关键码的集合 除此之外,每个外部结点代表其值处于
15、原来二叉搜索树的两个相邻结点的关键码值之间的可能关键码的集合,北京大学信息学院 版权所有,转载或翻印必究 Page 32,路径长度,外部路径长度E定义为从扩充的二叉树的根到每个外部结点的路径长度之和。 内部路径长度I定义为扩充的二叉树里从根到每个内部结点的路径长度之和,北京大学信息学院 版权所有,转载或翻印必究 Page 33,二叉搜索树里检索算法,在二叉搜索树里检索算法十分简单:首先用待查的关键码与二叉搜索树的根结点进行比较,若比较相等,则找到了要检索的关键码; 若比较不等,具待查关键码值小于根结点的关键码值,则下一次与根的左子树的根比较;否则与根的右子树的根比较。 如此递归地进行下去,直到
16、某一次比较相等,检索成功;或一直比较到树叶都不相等,检索失败。,北京大学信息学院 版权所有,转载或翻印必究 Page 34,检索一个关键码的比较次数,在检索过程中,每进行一次比较,就进入下面一层。因此,对于成功的检索,比较的次数就是关键码所在的层数加1。对于不成功的检索,被检索的关键码属于哪个外部结点代表的可能关键码集合,比较次数就等于此外部结点的层数 在二叉搜索树里,检索一个关键码的平均比较次数为,北京大学信息学院 版权所有,转载或翻印必究 Page 35,参数意义,其中1i,是第i个内部结点的层数,是第i个外部结点的层数, pi是检索第i个内部结点所代表的关键码的频率 qi是被检索的关键码
17、属于第i个外部结点代表的可能关键码集合(即处于第i个和第i+1个内部结点之间)的频率。pi,qi也叫做结点的权,北京大学信息学院 版权所有,转载或翻印必究 Page 36,最佳二叉搜索树定义,是检索第i个内部结点所代表的关键码的概率, 是被检索的关键码属于第i个外部结点代表的可能关键码集合的概率。 我们把检索中平均比较次数最小,也就是ASL(n)最小的二叉搜索树称作最佳二叉搜索树,北京大学信息学院 版权所有,转载或翻印必究 Page 37,什么样的二叉搜索树是最佳的 ?,检索所有结点的概率都相等,即所有结点的权都相等: 因此,要平均比较次数ASL(n)最小,就是要内部路径长度I最小,北京大学信
18、息学院 版权所有,转载或翻印必究 Page 38,在一棵二叉树里,路径长度为0的结点仅有一个,路径长度为1的结点至多有两个,路径长度为2的结点至多有四个,等等。因此,有n个结点的二叉树其内部路径长度I至少等于序列: 0,1,1,2,2,2,2,3,3,3,3,3,3,3,4,4,的前n项和。这个和写成:,北京大学信息学院 版权所有,转载或翻印必究 Page 39,可以证明: 这种二叉树的特点是只有最下面的两层结点的度数可以小于2,其它结点度数必须等于2。在所有结点的权相等的情况下,这样的二叉搜索树是最佳二叉搜索树,对它进行检索的平均比较次数为 这个ASL(n)是O(log2n)量级的,北京大学
19、信息学院 版权所有,转载或翻印必究 Page 40,最佳二叉搜索树构造举例,首先将集合K里的关键码排序 wan,wen,wil,wim,wul,xal,xem,xul,yo,yon,yum,zi,zol,zom 然后用二分法依次检索这些关键码,并把在检索中遇到的在二叉搜索树里还没有的关键码依次插入二叉搜索树中。 首先检索序列中的第一个关键码wan,用二分法检索wan的过程中会依次遇到关键码xem,wil,wan,这就是最先插入二叉搜索树的三个关键码。,北京大学信息学院 版权所有,转载或翻印必究 Page 41,最佳二叉搜索树构造举例,然后检索序列中的第二个关键码wen,用二分法检索wen的过程
20、中会依次遇到关键码xem,wil,wan,wen,其中只有 wen是二叉搜索树中还没有的,因此第四个插入到二叉搜索树中的关键码是wen。 再检索序列中的第三个关键码wil,如此进行下去,直到所有的关键码都已插入到二叉搜索树中,这样可得到最佳二叉搜索树。,北京大学信息学院 版权所有,转载或翻印必究 Page 42,北京大学信息学院 版权所有,转载或翻印必究 Page 43,二叉搜索树的效率,反过来,如果关键码按值递增的顺序依次插入到二叉搜索树中,则将得到退化为线性的二叉搜索树平均比较次数为O(n) 按任意的顺序把关键码插入到二叉搜索树中,它的检索效率如何呢?平均比较次数是接近最坏的情况O(n)呢
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十二 部分 高级 结构 教学 课件
链接地址:https://www.31doc.com/p-2568505.html