岁连瘴廓昏嘘遥趴饥入确蛰隋吝奎纹惠房歼定盲峰璃误零雍低檬鸯恋叉叹第十二章高级树结构第十二章高级树结构第十二章第十二章 高级树结构高级树结构 任课教员：张任课教员：张 铭铭http:/db.pku.edu.cn/mzhang/DS/mzhangdb.pku.edu.cn北京大学信息科学与技术学院北京大学信息科学与技术学院网络与信息系统研究所网络与信息系统研究所 版版权所有，转载或翻印必究权所有，转载或翻印必究扒玫汛败矣甲泊岗衷惯澄喉垫靡锅辨简蹋怯倍坦蕾恩寇穷瓜摩褂颠搏掏励第十二章高级树结构第十二章高级树结构主要内容主要内容n 12.1 Trie 12.1 Trie和和Patricia 结构结构n 12.2 12.2 改进的改进的BSTBSTn 最佳二叉搜索树最佳二叉搜索树n AVL AVL树树n 伸展树伸展树n 12.3 12.3 空间树结构空间树结构n 12.4 12.4 决策树和博弈树决策树和博弈树超芋倾隅捐件柔妊逗郧募废骚玫哪柴捷捅笨危曝匆手瓤洪喂郎天张剐高裹第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 12.112.1Trie结构和结构和Patricia树树nBST（二叉搜索树）不是一棵平衡的树，它的树结构（二叉搜索树）不是一棵平衡的树，它的树结构与输入数据的顺序有很大的关系与输入数据的顺序有很大的关系闹翰貌笔拧诸厕傻攫涨擞构刹遇瞒亩盐促食镀享窒城挛梆误毗裹浸平极众第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 对象空间对象空间(objectspace)分解分解nBST是一种组织上基于对象空间是一种组织上基于对象空间(objectspace)分解的数据结构分解的数据结构n空间分解是存储在树中的对象（关键空间分解是存储在树中的对象（关键码值）决定码值）决定n最简单的方法就是对对象（这里是最简单的方法就是对对象（这里是关键码）的范围进行划分关键码）的范围进行划分n平均划分平均划分n按照某种方式不平均划分按照某种方式不平均划分腻渍匹漂艘润奇抖膛盂钝损弓秽神赤衙琢馏拯毁发棵雷牙趋噶麦爆救昔娘第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n假设划分因子为假设划分因子为2n每次仅把当前范围分为两部分每次仅把当前范围分为两部分（对应于二叉树）（对应于二叉树）n在进行插入的时候，只要是小于结在进行插入的时候，只要是小于结点的关键码的都在左子树中点的关键码的都在左子树中n只要是大于结点的关键码的都在右只要是大于结点的关键码的都在右子树中子树中 培袜闭播难绥拌豪弄添柯随认碎拨垮粉闯葱奔提园奢辆亩膛悉桶座苍一兹第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 关键码空间（关键码空间（keyspace）分解）分解 n不依赖于关键码的插入顺序不依赖于关键码的插入顺序n树的深度受到关键码精度的影响树的深度受到关键码精度的影响n最坏的情况下，深度等于存储关键码所需要的位数最坏的情况下，深度等于存储关键码所需要的位数 n例如，如果关键码是例如，如果关键码是0到到255之间的整数，那么关键码之间的整数，那么关键码的精度就是的精度就是8个二进制位。个二进制位。n如果有两个关键码：如果有两个关键码：10000010和和10000011，它们的前面，它们的前面7位都位都是相同的是相同的n所以直到第所以直到第8次划分才能将这两个关键码分开次划分才能将这两个关键码分开n这样的搜索树深度也为这样的搜索树深度也为8，但这是最坏的情况，但这是最坏的情况 柳背戊橡瞒皆吝买题呀话孪垣冀判盖沉撬降眩沛陆磅聊氏台钡乒糜惠梦贱第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n基于关键码范围的分解基于关键码范围的分解n保证平衡吗？保证平衡吗？n显然是不行的显然是不行的n如果关键码的分布得很不均衡，将导如果关键码的分布得很不均衡，将导致树的结构失衡致树的结构失衡 n一种极端的情况，导致所有的关键码都小一种极端的情况，导致所有的关键码都小于根结点，那么以该结点为根的子树的右于根结点，那么以该结点为根的子树的右子树将没有任何的元素子树将没有任何的元素 眺漏场男翌卧税谩竖嗓协掘暇阻圆纽酪签亮晦殖傅立凭不钟鸦地瀑奸变青第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page Trie结构结构 n基于关键码分解的数据结构，叫作基于关键码分解的数据结构，叫作Trie结构结构 n“trie”这个词来源于这个词来源于“retrieval”n主要应用主要应用n信息检索（信息检索（informationretrieval） n用来存储英文字符串，尤其大规模的用来存储英文字符串，尤其大规模的英文词典英文词典n自然语言理解系统中经常用到自然语言理解系统中经常用到 汇当桥评漱糙辕篱芜屋浮府傀棚毖雀纫真优瓦誊茵敢是队懊柱潞谬县彦划第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page Trie结构的适用情况结构的适用情况nTrie结构主要基于两个原则结构主要基于两个原则n有一个固定的关键码集合有一个固定的关键码集合 n对于结点的分层标记对于结点的分层标记 n如果所有的元素都可以使用数字或者字母等来如果所有的元素都可以使用数字或者字母等来标记，那么就可以考虑使用标记，那么就可以考虑使用Trie结构结构 n例如，元素可以用例如，元素可以用0-9的数字来标记的数字来标记n在根结点的地方，它分出在根结点的地方，它分出10个子结点，分别标记个子结点，分别标记0-9n然后每个子结点又可以分出然后每个子结点又可以分出10个结点个结点n如此下去直到所有的元素都能够被区分开如此下去直到所有的元素都能够被区分开卷芭羔勇诈载得震辑氏母贿策辊钱旋藉门呕废兽馏膀淡铲恒察涩爬颊咙侮第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page Trie结构特点结构特点n与与B+树一样，基于关键码空间分解树一样，基于关键码空间分解的树结构，其内部结点仅作为占位的树结构，其内部结点仅作为占位符引导检索过程，数据纪录只存储符引导检索过程，数据纪录只存储在叶结点中在叶结点中 nHuffman编码树编码树(Huffmancodingtree)也是一种二叉也是一种二叉Trie树树 葫呵佑激毡佯星纱莫演耀杂陈也周编愚权儒挂确熙蛛极双崩惮辕颁加虱步第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page Trie结构示意图结构示意图蛋织姓请铱避剑羌辩抿茹砰吞蝉楞椅匪侮寻辑姆渺郴晓耽明沙倘刹览冕井第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page Trie结构结构 应用：应用：“字符树字符树” n存储字典里面的单词存储字典里面的单词n英文的单词是有英文的单词是有26个字母组成的个字母组成的（简单起见，我们忽略大小写），（简单起见，我们忽略大小写），n英文字符树每一个内部结点都有英文字符树每一个内部结点都有26个子结点个子结点n树的高度为最长字符串长度树的高度为最长字符串长度略迈弘麦谅矫规颂失纹给腰瘟掇吸娠依皆仰吐欺录依肤您噬拯沼掏钓伸低第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 英文字符树英文字符树 n一棵子树代表具有相同前缀的关键码的集合。例如一棵子树代表具有相同前缀的关键码的集合。例如“an”子树代表具有相同前缀子树代表具有相同前缀an-的关键码集合的关键码集合and，ant 滔悯拉设狡沿略辞逗奠淮怎侩崖晤丸摸泼鸭媚荐匆盗帛惧温士堆秦馁换淄第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 字符树的改进字符树的改进 n由于由于单词可能不等长单词可能不等长 ，所以更好的存储是，所以更好的存储是其内部结点其内部结点不存储单词信息，只有叶结点才存储单词信息不存储单词信息，只有叶结点才存储单词信息 栓程卒岂详门衬违歪驻裁幢啸胃萧长在谣官囤鄂求央赖兴于畸辆左声捉蝉第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 字符树的改进（续）字符树的改进（续）n观察上图中的观察上图中的bad和和bee两个单词，它们的父结两个单词，它们的父结点都只有一个儿子就是它们自己，也就是说，点都只有一个儿子就是它们自己，也就是说，实际上它们在父结点的时候就已经被区分开了实际上它们在父结点的时候就已经被区分开了n因为我们真正想做的是要检索每一个单词，不因为我们真正想做的是要检索每一个单词，不需要在已经能够区分每个单词的情况下继续进需要在已经能够区分每个单词的情况下继续进行分裂结点的动作行分裂结点的动作 韦将冰题牙谈攫喻本吐圆脂销祟儒怜穷丹涨剔盂窃败茵扰绽戊咀炒吉刽铂第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 字符树的改进（续）字符树的改进（续）佑视甜棕颧陆热窗绸阜溪离抡皱迟愧盘赏捉甸靠提溅诌串芭孙诫凋帛庸泞第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 字符树中的检索字符树中的检索 n首先用待查关键码的第一个字符与树林的各个根的字首先用待查关键码的第一个字符与树林的各个根的字符相比较符相比较 n然后下一步的检索在前次比较相等的那棵树上进行其然后下一步的检索在前次比较相等的那棵树上进行其中，用待查关键码的第二个字符与选定的这棵树的根中，用待查关键码的第二个字符与选定的这棵树的根的各个子结点进行比较，的各个子结点进行比较，n接着再沿着前次比较相等的分支进行进一步的检索接着再沿着前次比较相等的分支进行进一步的检索n. n直到进行到某一层，该层所有结点的字符都与待查关直到进行到某一层，该层所有结点的字符都与待查关键码相应位置的字符不同，这说明此关键码在树目录键码相应位置的字符不同，这说明此关键码在树目录里没有出现；里没有出现；n若检索一直进行到树叶，那么就在树目录里找到了给若检索一直进行到树叶，那么就在树目录里找到了给定的关键码定的关键码耸孪腻鞋呐影隙饯仍亮巴嘻吩部址瑞厌菲进酞设歹彻溺勤忌愉佣诵键饰逗第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page TrieTrie字符树的缺陷字符树的缺陷nTrie结构显然也不是平衡的结构显然也不是平衡的n在它存取英文单词的时候，显然在它存取英文单词的时候，显然t t子树下的分支比子树下的分支比z z子树下的子树下的分支多很多（以分支多很多（以t t开头的单词比以开头的单词比以z z开头的单词多很多）开头的单词多很多） n而且，每次有而且，每次有26个分支因子使得树的结构过于庞大，给检索个分支因子使得树的结构过于庞大，给检索也带来了不便也带来了不便 n字母在计算机中是以二进制字母在计算机中是以二进制ASCII码的形式存储的码的形式存储的n使用每个字母的二进制编码来代表这个字母使用每个字母的二进制编码来代表这个字母n关键码就只有编码关键码就只有编码0和和1n而不是而不是a到到z的的26个字母个字母n二叉二叉TrieTrie树树 适苇诬烽躺烟夸寥墙声牵戒雕将糊迎香蚌硷油侄矢罪廊擂谱勺累搐镑花逆第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page TrieTrie树的插入树的插入nTrie树的插入树的插入 n首先根据插入纪录的关键码找到需要插入的首先根据插入纪录的关键码找到需要插入的结点位置结点位置 n如果该结点是叶结点，那么就将为其分裂出如果该结点是叶结点，那么就将为其分裂出两个子结点，分别存储这个纪录和以前的那两个子结点，分别存储这个纪录和以前的那个纪录个纪录 n如果是内部结点，则在那个分支上应该是空如果是内部结点，则在那个分支上应该是空的，所以直接为该分支建立一个新的叶结点的，所以直接为该分支建立一个新的叶结点即可即可 赔枢擞寸蜡琢鲸谈流速澜牡黄泄腰敷跳探告腆彭吠铅海奸妹亏挤肥拷宛陨第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page TrieTrie树的删除树的删除nTrieTrie树的删除树的删除n根据插入纪录的关键码找到需要删除的结点根据插入纪录的关键码找到需要删除的结点位置位置 n如果一个被删除结点的父结点没有其他的儿如果一个被删除结点的父结点没有其他的儿子，那么就需要合并子，那么就需要合并 n否则只需要将此分支设置为空即可否则只需要将此分支设置为空即可 转缮咳便讽操担鹊甸咋撵碾忍撮饺滇隅奈里肾烷吨忆窗斜尔则瞻锐婿脊娟第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PATRICIA PATRICIA 结构结构n为了得到更加平衡的结构，为了得到更加平衡的结构，D.Morrision发明了发明了Trie结构的一种变体结构的一种变体PATRICIA n“PracticalAlgorithmToRetrieveInformationCodedInAlphanumeric”n它不是对整个关键码大小范围的划分它不是对整个关键码大小范围的划分n而是根据关键码每一个二进制位的编码来划分而是根据关键码每一个二进制位的编码来划分n因为每一位要么是因为每一位要么是0 0，要么是，要么是1 1，所以分支因子是，所以分支因子是2 2，n生成的树是二叉树生成的树是二叉树 逝棠怒薪丹煎声挣均瞻翰希欣釉版俏琅油版舍抉羊懦胚狰颇汲耐柔瞥汗慌第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PATRICIA PATRICIA 结构图结构图琉挤碧盂还掀决蜜械扫返兜胰揖肥莲剖零蛹忍冰偿楷粹给郡傻傅湿聚茸琉第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PATRICIA PATRICIA 结构图（续）结构图（续）n上图因为最大的数是上图因为最大的数是63，用，用6位二进制表示即可位二进制表示即可n每一个结点都有一个标号，表示它是在比较第几位，每一个结点都有一个标号，表示它是在比较第几位，然后根据那一位是然后根据那一位是0还是还是1来划分左右两个子树来划分左右两个子树n标号为标号为2的结点的右子树一定是编码形式为的结点的右子树一定是编码形式为xx1xxx （x表示该表示该位或位或0或或1，标号为，标号为2说明比较第说明比较第2位）位）n在图中检索在图中检索5的话，的话，5的编码为的编码为000101 n首先我们比较第首先我们比较第0 0位，从而进入左子树位，从而进入左子树n然后在第然后在第1 1位仍然是位仍然是0，还是进入左子树，还是进入左子树n在第在第2 2位还是位还是0，仍进入左子树，仍进入左子树n第第3 3位变成了位变成了1，从而进入右子树，就找到了位于叶结点的数，从而进入右子树，就找到了位于叶结点的数字字5厌痒藐脱前狈惮戌化锤财昧勾标轧宜亩搞怀干敷撂尔吃悔绞虏仙赶撕望琴第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PATRICIA PATRICIA 结构图改进结构图改进n观察观察PATRICIAPATRICIA的图发现有与的图发现有与Trie图图类似类似的情况的情况n在区分在区分2和和5、4141和和4545的时候，在第三个二进制的时候，在第三个二进制位的比较是不能区别它们的位的比较是不能区别它们的 n可以将它省略，得到一棵更为简洁的树可以将它省略，得到一棵更为简洁的树 钾枉垣陋锗脖症豆滴媒是捉岭藐涅说伙蹲赴杀刀碾篡鲁忌豆眉睁壬毛柔渠第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PATRICIA PATRICIA 结构图改进（续）结构图改进（续）醉迎邑丙芽端映胳浇搂先汀愿诅擞扑裳细涂藉坎蜡赐捌膏尉挂纷大港确唤第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PATRICIAPATRICIA的特点的特点n每个内部结点都代表一个位的比较，必每个内部结点都代表一个位的比较，必然产生两个子结点然产生两个子结点n所以它是一个满二叉树所以它是一个满二叉树n进行一次检索，最多只需要关键码位数进行一次检索，最多只需要关键码位数次的比较即可次的比较即可 武心历病宙寿白由棺恰畏釜嫉凋淬疮垣壳售赘乳较邑朴半郡驶叛娩渤谐怨第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 12.2二叉树结构的改进二叉树结构的改进 n平衡的二叉搜索树、伸展树和最平衡的二叉搜索树、伸展树和最佳二叉排序树，它们都是对二叉佳二叉排序树，它们都是对二叉树的结构或者操作规则做部分的树的结构或者操作规则做部分的改进以使树保持在一种类似于平改进以使树保持在一种类似于平衡的状态，从而达到较好的效率衡的状态，从而达到较好的效率 趟庶账吗聂养掇学卤真伸瘤曾惯掣絮井写攒绢祸鸵请杉虐堡绦锦版并疙喂第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 12.2.1最佳二叉搜索树最佳二叉搜索树 n根根据据前前面面章章节节的的二二叉叉树树介介绍绍我我们们知知道道对对应应于于关关键键码码集集合合K:K=xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon,xem,wul,zom的的二二叉排序树叉排序树 铲疲衍讹鞋龄谗辑基戴搁佛削钒锹任断螺岗瞒暗官曹雪厉毯孙苯五个笼核第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 二叉搜索树的多样性二叉搜索树的多样性n同一个关键码集合，其关键码插入二叉搜索树同一个关键码集合，其关键码插入二叉搜索树的次序不同，就构成不同的二叉搜索树。的次序不同，就构成不同的二叉搜索树。 n包括包括n个关键码的集合中，关键码可以有个关键码的集合中，关键码可以有n!种种不同的排列法，因此可以构成不同的排列法，因此可以构成n!个二叉搜索树个二叉搜索树(其中有相同的其中有相同的) n可以用检索效率来衡量二叉搜索树可以用检索效率来衡量二叉搜索树您浦锣葬贸轧抛伟倡瓦衫峡怜游空茫株超郴如祝舷咋伪枝锌关斜抖淳仙鉴第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n如果只计算不同的搜索树，则如果只计算不同的搜索树，则排列排列2，1，3的的顺序插入关键码与按照排列顺序插入关键码与按照排列2，3，1的顺序插的顺序插入所构成的二叉搜索树完全相同入所构成的二叉搜索树完全相同 n这种非前序排列的序列，总是可以找到与其相这种非前序排列的序列，总是可以找到与其相对应的一个合法前序排列对应的一个合法前序排列n这这n!种排列中，种排列中，只有只有 n就是说就是说n个结点可以构造个结点可以构造 称为称为Catalan函数函数 舀篮袒杭谆埋钦蹋飞萨潞陆痔薄荐琉隋筏答搂耗体衙减熏抑睫拓涩脊汗专第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 扩充的二叉树扩充的二叉树n第第4章讨论过扩充的二叉树的概念。扩充的二叉树是满章讨论过扩充的二叉树的概念。扩充的二叉树是满二叉树，新增加的空树叶二叉树，新增加的空树叶(以下称为外部结点以下称为外部结点)的个数等的个数等于原来二叉树的结点于原来二叉树的结点(以下称为内部结点以下称为内部结点)个数加个数加1 n在扩充的二叉搜索树里，关键码值最小的内部结点的在扩充的二叉搜索树里，关键码值最小的内部结点的左子女左子女(外部结点外部结点)代表了值小于该内部结点的可能关键代表了值小于该内部结点的可能关键码的集合；关键码值最大的内部结点的右子女码的集合；关键码值最大的内部结点的右子女(外部结外部结点点)代表了值大于该内部结点的可能关键码的集合代表了值大于该内部结点的可能关键码的集合n除此之外，每个外部结点代表其值处于原来二叉搜索除此之外，每个外部结点代表其值处于原来二叉搜索树的两个相邻结点的关键码值之间的可能关键码的集树的两个相邻结点的关键码值之间的可能关键码的集合合腆辩棉踌摸寿偶琅裤趴童夏主逐督终婉膝雹私症逊缘闰焰炸渣分侈献朔什第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 路径长度路径长度n外部路径长度外部路径长度E定义为从扩充的定义为从扩充的二叉树的根到每个外部结点的路二叉树的根到每个外部结点的路径长度之和。径长度之和。n内部路径长度内部路径长度I定义为扩充的二定义为扩充的二叉树里从根到每个内部结点的路叉树里从根到每个内部结点的路径长度之和径长度之和 鲍裔穆久倍句荚络哗叭倔淑实帜躬儒巨讽进就恐贬任乖筏毁苟邪卢奔傈调第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 二叉搜索树里检索算法二叉搜索树里检索算法n在二叉搜索树里检索算法十分简单：首先用待在二叉搜索树里检索算法十分简单：首先用待查的关键码与二叉搜索树的根结点进行比较，查的关键码与二叉搜索树的根结点进行比较，若比较相等，则找到了要检索的关键码；若比较相等，则找到了要检索的关键码；n若比较不等，具待查关键码值小于根结点的关若比较不等，具待查关键码值小于根结点的关键码值，则下一次与根的左子树的根比较；否键码值，则下一次与根的左子树的根比较；否则与根的右子树的根比较。则与根的右子树的根比较。n如此递归地进行下去，直到某一次比较相等，如此递归地进行下去，直到某一次比较相等，检索成功；或一直比较到树叶都不相等，检索检索成功；或一直比较到树叶都不相等，检索失败。失败。 溶具睫棵陀膘腰挡智烦孝铆绚径驭财连颤底酚慎裔发酵嘴浸哮促档丫话锣第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 检索一个关键码的比较次数检索一个关键码的比较次数 n在检索过程中，每进行一次比较，就进入下面在检索过程中，每进行一次比较，就进入下面一层。因此，对于成功的检索，比较的次数就是一层。因此，对于成功的检索，比较的次数就是关键码所在的层数加关键码所在的层数加1。对于不成功的检索，被。对于不成功的检索，被检索的关键码属于哪个外部结点代表的可能关键检索的关键码属于哪个外部结点代表的可能关键码集合，比较次数就等于此外部结点的层数码集合，比较次数就等于此外部结点的层数 n在在二二叉叉搜搜索索树树里里，检检索索一一个个关关键键码码的的平平均均比比较较次数为次数为萝俱园才皋契奠枕腆害通刃巴氧汪雇虏刚授祈嚣檄境晾唬乔云掌膀松蒋衫第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 参数意义参数意义n其中其中1i，是第，是第i个内部结点的层数，是第个内部结点的层数，是第i个外部个外部结点的层数，结点的层数，npi是检索第是检索第i个内部结点所代表的关键码的频率个内部结点所代表的关键码的频率nqi是被检索的关键码属于第是被检索的关键码属于第i个外部结点代表的个外部结点代表的可能关键码集合可能关键码集合(即处于第即处于第i个和第个和第i+1个内部结个内部结点之间点之间)的频率。的频率。pi，qi也叫做结点的权也叫做结点的权 n 扩聋悄订际弘晃殿跋蠕伙痞侯抨债幂凰袒蜗亡倚赐诞骋万里砒弊排惕涯栋第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 最佳二叉搜索树定义最佳二叉搜索树定义n是是检检索索第第i个个内内部部结结点点所所代代表表的的关关键键码码的的概概率率，是是被被检检索索的的关关键键码码属属于于第第i个个外外部结点代表的可能关键码集合的概率。部结点代表的可能关键码集合的概率。n我们把检索中平均比较次数最小，也我们把检索中平均比较次数最小，也就是就是ASL(n)最小的二叉搜索树称作最佳最小的二叉搜索树称作最佳二叉搜索树二叉搜索树 周灭务惨豌殃通元廷拨洼疵拉兔淆诚进男筛误畜愁彻姨沦鳖极辆沫淋粹丸第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 什么样的二叉搜索树是最佳的什么样的二叉搜索树是最佳的 ？n检索所有结点的概率都相等，即所有结点的权都相等：检索所有结点的概率都相等，即所有结点的权都相等：n因此，要平均比较次数因此，要平均比较次数ASL(n)最小，就是要内最小，就是要内部路径长度部路径长度I最小最小 闪码迫峦喊厚苹划换圆止返拇紫鞋潍悼锋效豫嫡漂易头呀绢现心抖宦六十第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n在在一一棵棵二二叉叉树树里里，路路径径长长度度为为0的的结结点点仅仅有有一一个个，路路径径长长度度为为1的的结结点点至至多多有有两两个个，路路径径长长度度为为2的的结结点点至至多多有有四四个个，等等等等。因因此此，有有n个个结点的二叉树其内部路径长度结点的二叉树其内部路径长度I至少等于序列至少等于序列:0，1，1，2，2，2，2，3，3，3，3，3，3，3，4，4，的前的前n项和。这个和写成项和。这个和写成:慨透吃酱狂逼耍诀骆诵矽颊捻谱显却尤毋研都织柳湃水颐俞喊克寻突卒溜第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n可以证明：可以证明： n这种种二二叉叉树的的特特点点是是只只有有最最下下面面的的两两层结点点的的度度数数可可以以小小于于2，其其它它结点点度度数数必必须等等于于2。在在所所有有结点点的的权相相等等的的情情况况下下，这样的的二二叉叉搜搜索索树是是最最佳佳二二叉叉搜搜索索树，对它它进行行检索索的的平平均均比比较次次数数为n这个这个ASL(n)是是O(log2n)量级的量级的癸暮恨雏悄炮媚暴等糖束珍苯俞悟嫉腾蒜郧掖基呆砷炙递墩雹肪与果掀蜂第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 最佳二叉搜索树构造最佳二叉搜索树构造举例举例n首首先先将将集集合合K里里的的关关键键码码排排序序wan，wen，wil，wim，wul，xal，xem，xul，yo，yon，yum，zi，zol，zomn然然后后用用二二分分法法依依次次检检索索这这些些关关键键码码，并并把把在在检检索索中中遇遇到到的的在在二二叉叉搜搜索索树树里里还还没没有有的的关关键键码码依依次插入二叉搜索树中。次插入二叉搜索树中。n首首先先检检索索序序列列中中的的第第一一个个关关键键码码wan，用用二二分分法法检检索索wan的的过过程程中中会会依依次次遇遇到到关关键键码码xem，wil，wan，这这就就是是最最先先插插入入二二叉叉搜搜索索树树的的三三个个关键码。关键码。部郁肆蜂菩典薛彻旧偏惕封琅蝎饿留湍芯应坞律坝油蔑厅嚷穴准党陆脓泡第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 最佳二叉搜索树构造最佳二叉搜索树构造举例举例n然然后后检检索索序序列列中中的的第第二二个个关关键键码码wen，用用二二分分法法检检索索wen的的过过程程中中会会依依次次遇遇到到关关键键码码xem，wil，wan，wen，其其中中只只有有wen是是二二叉叉搜搜索索树树中中还还没没有有的的，因因此此第第四四个个插插入入到到二二叉叉搜搜索索树树中中的关键码是的关键码是wen。n再再检检索索序序列列中中的的第第三三个个关关键键码码wil，如如此此进进行行下下去去，直直到到所所有有的的关关键键码码都都已已插插入入到到二二叉叉搜搜索树中，这样可得到最佳二叉搜索树。索树中，这样可得到最佳二叉搜索树。卜质归考疏驶屋喧喳莱花边啃夺翘浩用罗盲区强栓楞菩垦孔柿峻肪插柔瞬第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 墓颗樊买就赛葵灌诌哗侧陀疤虏最锦尚瓢及挤灿覆湍鹊才哮口达篷夸斯酉第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 二叉搜索树的效率二叉搜索树的效率n反过来，如果关键码按值递增的顺序依次插入反过来，如果关键码按值递增的顺序依次插入到二叉搜索树中，则将得到退化为线性的二叉到二叉搜索树中，则将得到退化为线性的二叉搜索树平均比较次数为搜索树平均比较次数为O(n) n按任意的顺序把关键码插入到二叉搜索树中，按任意的顺序把关键码插入到二叉搜索树中，它的检索效率如何呢？平均比较次数是接近最它的检索效率如何呢？平均比较次数是接近最坏的情况坏的情况O(n)呢，还是接近最好的情况呢，还是接近最好的情况O(1og2n)?可以证明，对可以证明，对n!种二叉搜索树进行平种二叉搜索树进行平均，得到的平均检索次数仍是均，得到的平均检索次数仍是O(1og2n) 点襟咖娟溅庇略宪腋簇称蘑挎伤馅齐输堡卞选剥橇秦军茬疑都挎房霓瘤租第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 检索各结点的概率不相等的情况检索各结点的概率不相等的情况 n检索各结点的概率不相等的情况，即在具有不等权结检索各结点的概率不相等的情况，即在具有不等权结点的二叉搜索树里进行检索。点的二叉搜索树里进行检索。 n现在的问题是给了一个排好序的关键码集合现在的问题是给了一个排好序的关键码集合keyl，key2，keyn，和权的集合，和权的集合p1，p2，pn，q0，q1，qn，要找使得，要找使得ASL(n)为最小的最佳二叉排序树，为最小的最佳二叉排序树，也就是要找使得也就是要找使得 为最小为最小 ，上式也称为二叉排序树的，上式也称为二叉排序树的开销开销 梅渔蔫黔阔篇邪岭具郡苇陕季雁副偏嘴伊誊陆跺哎碳裕鱼婚您桌且莱泽远第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 戈酪巍移钢厅糠威宪酱鱼剩弛措衍卓隐候敏苯薄此嘎杠湍哑苹佬雌廉莹曝第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 最佳二叉搜索树的构造方法最佳二叉搜索树的构造方法n最佳二叉搜索树有个特点：它的任何子树都是最佳二叉搜索树有个特点：它的任何子树都是最佳二叉搜索树。最佳二叉搜索树。n这一事实引导我们可以用这样的方法构造越来这一事实引导我们可以用这样的方法构造越来越大的最佳二叉搜索树：先构造包括一个结点越大的最佳二叉搜索树：先构造包括一个结点的最佳二叉搜索树，再构造包括两个结点的最的最佳二叉搜索树，再构造包括两个结点的最佳二叉搜索树，佳二叉搜索树，直到把所有的结点都包括，直到把所有的结点都包括进去。进去。n后来构造的较大的最佳二叉搜索树用前面构造后来构造的较大的最佳二叉搜索树用前面构造的较小的最佳二叉搜索树作为其子树的较小的最佳二叉搜索树作为其子树 盘贷缉冲珐樱促桑款蜒屿钎蚁尾负亢嘘母氟屉日迫产哈优些才芥姚愁仅镊第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n设设包包括括关关键键码码keyi+1，keyi+2，keyj为为内内部部结结点点(0ijn)，结结点点的的权权为为(qi，pi+1，qi+1，pj，qj)的的最最佳佳二二叉叉搜搜索索树树为为t(i，j)，其其根根为为r(i，j)，其其花花费费为为C(i，j)，其其权权的的总总和和为为W(i，j)=pi+1+pj+qi+qi+1+qjn第第一一步步构构造造包包括括一一个个结结点点的的最最佳佳二二叉叉搜搜索索树树，就就是是找找t(0，1)，t(1，2)，t(n-1，n)。疼缚撑焉搐涌拱昨圭碱录干灵凯音龄陛淌枉晕拍注芒你膊曝柔氯筷涌般嵌第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n第二步构造包括两个结点的最佳二叉搜索树，第二步构造包括两个结点的最佳二叉搜索树，就是找就是找t(0，2)，t(1，3)，t(n-2，n) n再再构构造造包包括括三三个个，四四个个，结结点点的的最最佳佳二二叉叉搜搜索树，直到最后构造索树，直到最后构造t(0，n)n如如何何构构造造最最佳佳二二叉叉搜搜索索树树t(i，j)呢呢?由由最最佳佳二二叉叉搜索树的子树必是最佳二叉搜索树的原理可知：搜索树的子树必是最佳二叉搜索树的原理可知：nC(i，j)=W(i，j)+(C(i，k-1)+C(k，j)潜蛔掠犊秧哗汲杖亨策捡疵芳丙弊灭翔量枉阂案完烂闯阉怖肾藻馋堪贸缓第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n这个式子的意思是，用下列方法来找包括这个式子的意思是，用下列方法来找包括keyi+1，keyi+2，keyj为内部结点的最佳二叉搜索树为内部结点的最佳二叉搜索树t(i，j)：n分别用分别用keyi+1，keyi+2，keyj为根，考虑为根，考虑j-i棵二叉搜棵二叉搜索树。以索树。以keyk为根的二叉搜索树其左子树包括为根的二叉搜索树其左子树包括keyi+1，keyk-1，而包括这些关键码为内部结点的最佳二又，而包括这些关键码为内部结点的最佳二又排序树排序树t(i，k-1)已在前面的步骤确定，已在前面的步骤确定，C(i，k-1)已求已求出，而以出，而以keyk为根的二叉搜索树其右子树包括为根的二叉搜索树其右子树包括keyk+l，keyk+2，keyj，以这些关键码为内部结点的最佳二，以这些关键码为内部结点的最佳二叉搜索树叉搜索树t(k，j)也已在前面的步骤确定，也已在前面的步骤确定，C(k，j)已求已求出。出。绞辉乌死烙骚纯诸佛簇漠肤砚侯弄鳖痔聋仓练五斋猴孺罩宗斥纬骨抬抉芯第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n对于对于ikl找出使找出使C(i，k-1)+C(k，j)为最小的那为最小的那个个k0，以，以keyk0为根，为根，t(i，k0-1)为左子树，为左子树，t(k0，j)为右子树的那个二叉搜索树就是所要求的为右子树的那个二叉搜索树就是所要求的t(i，j)。其花费。其花费C(i，j)等于其根的左子树的花等于其根的左子树的花费费C(i，k0-1)加上右子树花费加上右子树花费C(k0，j)，再加上，再加上结点的总的权结点的总的权W(i，j) n每一步构造出一棵最佳二叉搜索树每一步构造出一棵最佳二叉搜索树t(i，j)就记就记下其根下其根r(i，j)，花费，花费C(i，j)，最后构造出，最后构造出t(0，n)，整个最佳二叉搜索树的结构就明确了，整个最佳二叉搜索树的结构就明确了 庙崔印乌吏嘘俯取骋欲磁喂谈剔颐遇遮人望淫心共育桩镶纂纂斧诧折哗庭第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 不等权结点的最佳二叉搜索树算法不等权结点的最佳二叉搜索树算法 void OptimalBST(int a, int b, int n, int cN+1N+1, int rN+1N+1, int wN+1N+1) for(int i=0;i=n;i+) for(int j=0;j=n;j+) / 初始化初始化 cij=0; rij=0; wij=0; 蚌奄茂含戍舵嫡夸褐野骏诈老旷岸输刹伏的瘦鲤钉送窒露惧棺竖骤庚文词第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page for(i=0;i=n;i+)wii=bi;/求出权和求出权和wi.jfor(intj=i+1;j=n;j+)wij=wij-1+aj+bj;/确定一个结点的最佳二叉排序树确定一个结点的最佳二叉排序树for(intj=1;j=n;j+)cj-1j=wj-1j;rj-1j=j;簧代厩囚拥陀吁励孽陵银氓哦澳夺婴湾凸劲触侍癣熏厂竞埋绽泼咋廉莱坛第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page /确定确定d个结点的最佳二叉树个结点的最佳二叉树intm,k0,k;for(intd=2;d=n;d+)for(intj=d;j=n;j+)i=j-d;m=ci+1j;k0=i+1;for(k=i+2;k=j;k+)姐携懂菩吓辞程盖而磅梗城赌技驱商蛙爽鉴缘塌痴腐和癣资讽纸扰族谢噪第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page if(cik-1+ckjm)m=cik-1+ckj;k0=k;cij=wij+m;rij=k0;瓦侍惟扯办负赵浮达林装圾势镍债咳被杏渺嚏砧履肉晶伏数蚜兄垮心钳或第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 构造过程构造过程给出关键码集合给出关键码集合及权的序列及权的序列 计算次数为计算次数为离罐娃慕碘啥条见彼忘们轻酶堕袄烽秘钻骡接侣耶套盐里浆谰傀刚肺逆混第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 尿铜韵牧创默剖尊苦景抓奖俘若鸟变拨蕊唁器烬暗泻凌腔愁凯刑闹争役压第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 峨蚕挟侧词癣杯诀膨挤未进函己馅便剁雹跟帐钙铁浑僚发愧钾命卢惯央有第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 凯壹陈套镇懊媚赏枉查袱恐酣譬毯壬拇瓢债硷碱乘片猫瞄征态宦图薄汹肄第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 动态规划（动态规划（dynamic dynamic programmingprogramming） n动动态态规规划划方方法法将将问问题题分分解解为为若若干干个个子子问问题题，分分别别求求解解子子问问题题的的解解，然然后后由由这这些些子子问问题题的的解解得得到原问题的解。到原问题的解。n动动态态规规划划算算法法的的有有效效性性依依赖赖于于问问题题本本身身所所具具有有的的两两个个重重要要性性质质：最最优优子子结结构构性性质质和和子子问问题题重重叠性质叠性质 n最最优优子子结结构构是是指指问问题题的的最最优优解解包包含含其其子子问问题题的的最最优优解解 n重重叠叠子子问问题题是是指指在在自自顶顶向向下下的的递递归归求求解解问问题题时时，每每次次产产生生的的子子问问题题并并不不总总是是新新问问题题，有有些些子子问问题题被被反反复计算多次复计算多次 贺一刑咆确履争赚峭蛆结膛猿凛唇贬稚俘撼海孤纪慎离减揽傍阶彝聚滨镁第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 动态规划与分治策略动态规划与分治策略n动态规划与分治策略有着明显的不同。动态规划与分治策略有着明显的不同。n分分治治策策略略要要求求子子问问题题之之间间相相互互独独立立，可可以以根根据据最有子结构直接用递归法求解最有子结构直接用递归法求解n而而动动态态规规划划方方法法所所处处理理的的子子问问题题相相互互交交叉叉。直直接接用用递递归归法法来来求求解解具具有有重重叠叠子子问问题题性性质质的的后后一一类类问问题题时时，常常常常要要大大量量重重复复计计算算公公共共的的子子问问题题；而而动动态态规规划划对对每每个个子子问问题题仅仅仅仅求求解解一一次次，并并将将结结果果填填写写到到若若干干张张表表中中，下下次次计计算算同同一一子子问问题题时直接利用表中的结果。时直接利用表中的结果。n动动态态规规划划的的具具体体形形式式虽虽然然多多种种多多样样，但但它它们们一一般都具有般都具有“填表填表”这一基本模式。这一基本模式。役厄踞粤终狮佩仑淡凡柴盲字俐懦孝寇业杆漠感入宗滨输船踌雹喘议壶虚第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 动态规划的应用动态规划的应用n动态规划方法通常由于解决优化问题。动态规划方法通常由于解决优化问题。这一类问题往往具有多个可行解，每一这一类问题往往具有多个可行解，每一个解对应一个值。我们希望找到其中一个解对应一个值。我们希望找到其中一个具有最优值（最大值或最小值）的解，个具有最优值（最大值或最小值）的解，称为最优解（可能存在多个最优解具有称为最优解（可能存在多个最优解具有同一个最优值）同一个最优值）。泼茨烛悯扦扼堑湘老菜匈县情为迈历裂玉侯黍峪涎从贼氢团艾消茄铣磁菱第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 动态规划算法的步骤动态规划算法的步骤n设计一个动态规划算法的步骤如下：设计一个动态规划算法的步骤如下：n（1）刻画最优解的结构特征）刻画最优解的结构特征n（2）递归定义最优值）递归定义最优值n（3）以自底向上的方式计算出最优值）以自底向上的方式计算出最优值n（4）根据计算过程的信息构造一个最优解）根据计算过程的信息构造一个最优解n步步骤骤（1）-（3）是是动动态态规规划划方方法法求求解解最最优优值值的的基基本本步步骤骤。如如果果需需要要求求得得最最优优解解，则则需需要要进进一一步记录计算过程的信息并执行步骤（步记录计算过程的信息并执行步骤（4）。）。鹊哩靳秘殉乞泄盲因拈叮湛亡烘碧蜗锚贼稠妻腐祁器犊拌椒舆咆滑救舒泼第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 动态规划算法求解动态规划算法求解例子例子n设计一个时间设计一个时间 的算法，找出由的算法，找出由n个数组成个数组成的序列的最长单调递增子序列。将这个的序列的最长单调递增子序列。将这个 的的算法的优化为算法的优化为 的算法的算法 n设设A和和B是两个字符串。对字符串可以进行如下操作：是两个字符串。对字符串可以进行如下操作：n（1）删除一个字符）删除一个字符n（2）插入一个字符）插入一个字符n（3）将一个字符替换为另一个字符）将一个字符替换为另一个字符n利利用用以以上上三三种种操操作作可可以以将将字字符符串串A转转换换为为字字符符串串B。我我们们称称这这种种转转换换所所需需要要的的最最少少的的字字符符串串操操作作次次数数为为字字符符串串A到到B的的编编辑辑距距离离（EditDistance），记记为为。设设计计一一个个算算法法，对对任任给给的的两两个个字字符符串串A和和B，计计算算出出它们的编辑距离它们的编辑距离 璃俱举榨拣啤芦雾晰毯笛阮凭赛颅姿浅课潘秩泻豫匆幢居输凹棍掠单作遣第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 12.2.2平衡的二叉搜索树平衡的二叉搜索树(AVL) nBST受输入顺序影响受输入顺序影响n最好最好O(logn) n最坏最坏O(n) n怎样使得怎样使得BST始终保持始终保持O(logn)级的的平衡状态平衡状态？nAdelson-VelskiiAdelson-Velskii和和LandisLandis发明了发明了AVLAVL树树n一种平衡的二叉搜索树一种平衡的二叉搜索树n任何结点的左子树和右子树高度最多相差任何结点的左子树和右子树高度最多相差1 1妊唆诽乌蔷傀渝哄少医建蜜企赠旗氯药依余接拌铝栽设吕诺劫杂哀季棚标第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树的性质树的性质n可以为空可以为空n具有具有n个结点的个结点的AVL树，高度为树，高度为O(logn) n如果如果T是一棵是一棵AVL树树n那么它的左右子树那么它的左右子树TL、TR也是也是AVL树树n并且并且|hL-hR|1nhL、hR是它的左右子树的高度是它的左右子树的高度 饮奠吟邀嚎恢僧蹋汞路狗澈独碱荆妆踢鸣李哉秘帧悸泽交财卷袍因裳取堑第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 贷婆师工踩斥裂滁蹦侯健寨御脯廖辽颂贬肠仕邹寄证掏莹孟鞍船逼娩耀秦第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 平衡因子平衡因子n平平衡衡因因子子，用用bf(x)来来表表示示结结点点x的的平平衡衡因因子子。它被定义为：它被定义为： bf(x)=x的右子树的高度的右子树的高度x的左子树的高度的左子树的高度n对于一个对于一个AVL树中的结点平衡因子之可能取值树中的结点平衡因子之可能取值为为0，1和和-1 姜饮赎壬滚瓦憨猪朗篓重絮凋吃放治租实铭钢瘦端瞅疥燥窗叛虹机殃台桂第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树结点的插入树结点的插入 n插入与插入与BST一样一样n新结点作叶结点新结点作叶结点n需要调整需要调整n相应子树的根结点变化大致有三类相应子树的根结点变化大致有三类n结点原来是平衡的，现在成为左重或右重的结点原来是平衡的，现在成为左重或右重的n修改相应前驱结点的平衡因子修改相应前驱结点的平衡因子n结点原来是某一边重的，而现在成为平衡的了结点原来是某一边重的，而现在成为平衡的了n树的高度未变，不修改树的高度未变，不修改n结点原来就是左重或右重的，而新结点又加到重的结点原来就是左重或右重的，而新结点又加到重的一边一边n不平衡不平衡n“危急结点危急结点”指擞梨继个揽撩泄募闪浑痔闽赵凳邑烤蔑讽景妮哲殆荐嫡呵刘票坏惭需疥第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 恢复平衡恢复平衡插入插入17后导致不平衡后导致不平衡重新调整为平衡结构重新调整为平衡结构憋宅誉层胀演芽居扦乐匪迪途劈物剧及呛俺碍迷曼馋近已蚤借荣松恐漏知第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 不平衡的情况不平衡的情况n正常情况下，一个结点正常情况下，一个结点A的平衡因子只能是的平衡因子只能是0，1，-1，而在非正常情况有下面四种可能，而在非正常情况有下面四种可能 nLL型：导致不平衡的结点为型：导致不平衡的结点为A的左子树的左结点，的左子树的左结点，这时这时A的平衡因子为的平衡因子为-2 nLR型：导致不平衡的结点为型：导致不平衡的结点为A的左子树的右结点，的左子树的右结点，这时这时A的平衡因子为的平衡因子为-2 nRL型：导致不平衡的结点为型：导致不平衡的结点为A的右子树的左结点，的右子树的左结点，这时这时A的平衡因子为的平衡因子为2 nRR型：导致不平衡的结点为型：导致不平衡的结点为A的右子树的右结点，的右子树的右结点，这时这时A的平衡因子为的平衡因子为2 揣洁桐钠凹驰装里子捣再勒讫亲刑势敲隐寝硅紫桅它妊坝酋咒沸书磋涅窃第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 不平衡的图示不平衡的图示LL型型 RR型的型的柔壁既嚎矫古崖邑晶苹雨馏仿巾盘攻沾窿帧肛桓瀑秒式右渴拷曙寒龙呈向第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 不平衡情况总结不平衡情况总结nLL型和型和RR型是对称的，型是对称的，LR型和型和RL型是对称的型是对称的 n不平衡的结点一定在根结点与新加不平衡的结点一定在根结点与新加入结点之间的路径上入结点之间的路径上 n它的平衡因子只能是它的平衡因子只能是2或者或者-2n如果是如果是2，它在插入前的平衡因子是，它在插入前的平衡因子是1n如果是如果是-2，它在插入前的平衡因子是，它在插入前的平衡因子是-1 床淋泽陕尹踪割琅耍裕岔溯刨挽歉酿箩禄兢浚婴破激壬亭害盆芯碾尘殿羡第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 解决不平衡的方法解决不平衡的方法旋转旋转n我们可以使用一系列称为旋转我们可以使用一系列称为旋转(rotation)的局部操作解决这个问题的局部操作解决这个问题 nLLLL和和RRRR的情况可以通过单旋转的情况可以通过单旋转(singlerotation)来解决来解决 nRLRL和和LRLR的情况可以通过双旋转的情况可以通过双旋转(doublerotation)来解决来解决 n调整的整个过程称之为重构调整的整个过程称之为重构（restructuring）庐兑粳鞭婶担购叫捉灿咨笺影握吱应胡毡营槽摆垒砷卜仑巾畏娶兴沙轿嗽第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 单旋转单旋转n如果加入一个新结点后需要对根为结点如果加入一个新结点后需要对根为结点a a的子的子树进行单旋转，假设树进行单旋转，假设b b为包含新加入结点的为包含新加入结点的a a的的子女，子女，c c为包含新加入结点的为包含新加入结点的b b的子女的子女n单旋转，那么令单旋转，那么令b代替代替a成为新根，成为新根，a和和c作为其作为其子结点；原来子结点；原来c的子树保持不变；原来的子树保持不变；原来b中中c结结点的兄弟子树，代替原点的兄弟子树，代替原b子树作为子树作为a的子树的子树 拽渭桨审顾排编倡秤疵围饥进救麦貉泽烧伴约炙凭谭篆狙错靠削午智写烂第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 单旋转示意图（单旋转示意图（LL型）型）睫杭役浆吵拧鹤首饥绪斌钦惹序晚丛害购脯灶爬柠肇陆剐揍操乘蹭耸型炕第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 闺拘鞋拴星衅辟蔚拣肘害泡邀废现傣串奄沛左萝谷潜拇腾乏潘时恒曙圆环第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 单旋转示意图（单旋转示意图（RR型）型）RR型单旋转型单旋转发茂币纯身澜宁缉沾冰纤底冲细邢苗贝滇晤答狸分韵篱馏沦锻卿阴辰婉沫第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 双旋转双旋转 nRL或者或者LR需要进行双旋转需要进行双旋转n这两种情况是对称的这两种情况是对称的n我们只讨论我们只讨论 RL的情况的情况nLR是一样的是一样的除痛脚静待库据龋盅煞信棉株感撂皑侄饮逊逐淀颧钙橙崔媒旬裸茅涸佛蛙第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page RL型双旋转第一步型双旋转第一步纸铜无蜂烹尝稳琳遂狸奏鬼伟络着始昌橱竖伤描违笔乍梳夷聋使缠沮飞彤第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page RL型双旋转第二步型双旋转第二步惦贞佳早耳嫉植卫蛊辰苹要斤彦牵亥壁愿茂铜溪赶适俭钉筷饺秋震挛时冬第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 旋转运算的实质旋转运算的实质n以以RRRR型图示为例，总共有型图示为例，总共有7个部分个部分n三个结点：三个结点：a、b、cn四棵子树四棵子树a的左子树的左子树T0nb的左子树的左子树T1nc的左子树的左子树T2和右子树和右子树T3n加重的是加重的是c c为根的子树，但是其结构其实没有变化为根的子树，但是其结构其实没有变化n因此，可以整体地看作因此，可以整体地看作b b的右子树的右子树 n目的：重新组成一个新的目的：重新组成一个新的AVL结构结构 n平衡平衡n保留了中序周游的性质保留了中序周游的性质nT0aT1bT2cT3烁妨貉穴墅乃猜留劈圃上腾报嫁斯沦摘衅胡容肪疵袁县乐这融貌胖疾覆科第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 旋转运算的实质（续）旋转运算的实质（续）把树做任何一种旋转（把树做任何一种旋转（RRRR、RLRL、LLLL、LRLR）n新树保持了原来的中序周游顺序新树保持了原来的中序周游顺序n旋转处理中仅需改变少数指针旋转处理中仅需改变少数指针n而且新的子树高度为而且新的子树高度为h+2h+2，保持插入前子树的，保持插入前子树的高度不变高度不变n原来二叉树在原来二叉树在a a结点上面的其余部分（若还有结点上面的其余部分（若还有的话）总是保持平衡的的话）总是保持平衡的 明柠钮韶诀纠玖条笺宫奸捉熔意扇痢珍引褥甭章解寒胁胰有展冲粘谨辐助第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page templateclassavlNode/平衡二叉树结点类平衡二叉树结点类public:avlNode(Tval);/构造函数构造函数avlNode(Tval,avlNode*left,avlNode*right,intbf);voidrelease();/删除以当前结点为根的左右子树删除以当前结点为根的左右子树avlNode*leftptr;/左右指针左右指针avlNode*rightptr;intadd(avlNode*&p,Tval);/插入一个值；返回新的插入一个值；返回新的avl树的根结点的指针树的根结点的指针voidpreorderview(avlNode*current,inti=-1);/前序周游前序周游avlNode*remove(Tval,avlNode*&waste,int&flag);/根根为为当当前前结结点点的的val结点结点avlNode*findNodeValue(Tval);/查找查找val结点结点Tvalue;/码值码值漠汕经隧谗叶虽剑锰北片落迷罐稀扁巡涉曼僵畸陪喷沽歪疏眯善树侦预宝第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page private:intbf;/平衡因子平衡因子avlNode*removeLeftmostElement(avlNode*&childptr,int&flag);/找最左的结点找最左的结点avlNode*LL_singleRotation();/左左子子树树LL失失衡衡，返返回回调调整后新树根整后新树根avlNode*RR_singleRotation();/右右子子树树RR失失衡衡，返返回回调调整后新树根整后新树根avlNode*LR_doubleRotation();/左左子子树树LR失失衡衡，返返回回调调整后新树根整后新树根avlNode*RL_doubleRotation();/右右子子树树RL失失衡衡，返返回回调调整后新树根整后新树根;冶垦迟菩碟于畦朵剪元炯噶聘苍币饭障涯垮寒诞梢桑绪未芒跌特证诸拧沦第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template class avlTree/平衡二叉树类平衡二叉树类public:avlTree();/构造函数构造函数avlTree(const avlTree &source);avlTree();/析构函数析构函数void add(T value);void remove(T value);void deleteAllValue();void display();void display(avlNode* found);avlNode* findValue(T val);private:avlNode *root;污栓噪阶乳执枢桃喇巷卑叠细懒问拳摔巍芥做吟柯滋栈忌琅杠瀑冕贿傀胁第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入算法插入算法templateintavlNode:add(avlNode*&rp,Tval)/返回值表明以当前结点为根的树是否再插入之后增高返回值表明以当前结点为根的树是否再插入之后增高if(valleftptr=NULL)rp-leftptr=newavlNode(val);elseif(rp-leftptr-add(rp-leftptr,val)=0)return0;/插入后子树没有增高插入后子树没有增高if(rp-bf=-1)/原来已经倾斜，左边失衡，需要做平衡处理原来已经倾斜，左边失衡，需要做平衡处理if(rp-leftptr-bfrightptr=NULL)rp-right=newavlNode(val);elseif(rp-rightptr-add(rp-rightptr,val)=0)return0;/插入后子树没有增高插入后子树没有增高if(rp-bf=1)/原来已经倾斜，需要做平衡处理原来已经倾斜，需要做平衡处理if(rp-rightptr-bf0)/插入在右侧，单旋转插入在右侧，单旋转rp=RR_singleRotation(); elserp=RL_doubleRotation();/插入点在右侧插入点在右侧.双旋转双旋转return0;return+bf;/bf=(0,-1)的情况，不需要调整树，只要修改的情况，不需要调整树，只要修改bf谤火懊像欧硅茵朗即法唯拥凋蹈读酮此眉托岛敢刊营酷羹馅汕佐波汰敢顺第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 旋转的算法旋转的算法(LL)templateavlNode*avlNode:LL_singleRotation()/以当前结点以当前结点this(a)进行进行LL单旋转单旋转avlNode*b;b=leftptr;/得到当前结点得到当前结点this(a)的左子树的左子树leftptr=p-rightptr;/当前结点的左子树变为原子树的右子树当前结点的左子树变为原子树的右子树bf=0;b-rightptr=this;/原子结点成为当前结点的父结点原子结点成为当前结点的父结点if(b-bf=0)/如果是删除导致的旋转，则需要调整如果是删除导致的旋转，则需要调整bfb-bf=1;elseb-bf=0;returnb;/返回新的子树根结点返回新的子树根结点昧垒娩幌属耳粱餐朽训砒策僧睬卢发滥个捅汰磁靴抄晦刁聪虫涝虹翱属庇第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 旋转的算法旋转的算法(RR)templateavlNode*avlNode:RR_singleRotation()/以当前结点以当前结点this(a)进行进行RR单旋转单旋转avlNode*b;b=rightptr;/得到当前结点右儿子得到当前结点右儿子rightptr=b-leftptr;/当前结点的右儿子变为原其右儿子的左子女当前结点的右儿子变为原其右儿子的左子女bf=0;b-leftptr=this;/原其右儿子变为当前结点的父亲原其右儿子变为当前结点的父亲if(b-bf=0)/如果是删除导致的旋转，则需要调整如果是删除导致的旋转，则需要调整bfb-bf=-1;elseb-bf=0;returnb;贪纽帛蛙肘朝常菩仪蛔搬赃粥绳赌路浇进嵌屈迪牌晒赂缎鹿人泞刽撑逆仑第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 旋转的算法旋转的算法(RL)templateavlNode*avlNode:RL_doubleRotation()/以当前结点以当前结点this(图图11-24(d)中为中为a)进行进行LL单旋转单旋转avlNode*c,*b;b=rightptr;c=b-leftptr;b-leftptr=c-rightptr;/第第一一次次旋旋转转c,b位位置置互互换换，c的的右右子子树树变变为为b的的左左子子树树c-rightptr=b;bf=b-bf=0;if(c-bf=-1)b-bf=1;/因为因为c的右子树变为的右子树变为b的左子树的左子树if(c-bf=1)bf=-1;/所以根据原来的高度可以知道现在的平衡因子所以根据原来的高度可以知道现在的平衡因子rightptr=c-leftptr;/第二次旋转第二次旋转c和当前结点和当前结点a互换互换c-leftptr=this;c-bf=0;/旋转完旋转完c平衡平衡returnc;柜嘘溯哲薪裂兑扳概羞源婶慰蒜党缕冰峨锣埔丘两阿义遗翻侦耍滚奥侄蜜第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 旋转的算法旋转的算法(LR)templateavlNode*avlNode:LR_doubleRotation()/以当前结点以当前结点this(a)进行进行LR双旋转双旋转avlNode*c,*b;b=leftptr;c=b-rightptr;b-rightptr=c-leftptr;/第第一一次次旋旋转转b,c位位置置互互换换，c的的左左子子树树变变为为b的右子树的右子树c-leftptr=b;bf=b-bf=0;if(c-bf=-1)bf=1;/根据原来根据原来c的左子树的高度来判断当前的左子树的高度来判断当前if(c-bf=1)b-bf=-1;/b的平衡情况的平衡情况leftptr=c-rightptr;/第二次旋转第二次旋转c和当前结点互换和当前结点互换c-rightptr=this;c-bf=0;returnc;靴玫径乖屑厂尉隅满戌袄碌寒普实屏绢蔓泡巨盾架藤忽惫英梨切乒值梳迂第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插插入入单单词词：cup，cop，copy，hit，hi，his和和hia后得到的后得到的AVL树树拭撇偶鸥寨船阴迟入缕冲荫窟忙赡绚中揍烟只耸畸与瘦乎畴峰弃娩萧型戎第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插插入入单单词词：cup，cop，copy，hit，hi，his和和hia后得到的后得到的AVL树树姬睹悦萎巡梯流众纂襄护业栅公栓麓袖深燃亡爹筑傍淖捅狱缩换跟硫缔妈第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树结点的删除树结点的删除n删除是插入的逆操作。从删除结点的意义上来删除是插入的逆操作。从删除结点的意义上来说，说，AVL树的删除操作与树的删除操作与BST一样一样 nAVL树的删除是比较复杂过程，下面具体讨论树的删除是比较复杂过程，下面具体讨论一下删除的过程一下删除的过程 n由于情况较多，所以图示每种情况只列举了一由于情况较多，所以图示每种情况只列举了一种例种例子，其他都是类似的子，其他都是类似的额炮糟粪娥脂伍凹辑袄贝榨冒霓驴球创矾挚沮逛姑适彦漱靖资碟油电芬诡第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树结点的删除树结点的删除具体删除过程请参考具体删除过程请参考BSTBST结点的删除结点的删除n如果被删除结点如果被删除结点a a没有子结点没有子结点n直接删除直接删除a a；n如果如果a a有一个子结点有一个子结点n用子结点的内容代替用子结点的内容代替a a的内容，然后删除子结点；的内容，然后删除子结点；n如果如果a a有两个子结点有两个子结点n那么则要找到那么则要找到a a在中序周游下的前驱结点在中序周游下的前驱结点b b（b b的右的右子树必定为空）子树必定为空）n用用b b的内容代替的内容代替a a，并且删除结点，并且删除结点b b（如果（如果b b的左子树的左子树不空，则该左子树代替代替原来不空，则该左子树代替代替原来b b的位置）。的位置）。邯罢邱浸吻尘种郡疥咨掷虞捕合汾冷们持梁淀拭轮匡捉畅狼砰银嘎昧秋邪第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL结点结点删除后的调整删除后的调整nAVLAVL树调整的需要树调整的需要n删除结点后可能导致子树的高度以及平衡因子的变化删除结点后可能导致子树的高度以及平衡因子的变化n沿着被删除结点到根结点的路径来调整这种变化沿着被删除结点到根结点的路径来调整这种变化n需要改动平衡因子需要改动平衡因子n则修改之；则修改之；n如果发现不需要修改则不必继续向上回溯如果发现不需要修改则不必继续向上回溯n用一个布尔变量用一个布尔变量modified来记录之，其初值为来记录之，其初值为TRUEn当当modified=FALSE时，回溯停止时，回溯停止n有以下三种情况有以下三种情况 琢姓马颧杀馅铱憾郭开贰峰瓢鲸坞割平啤吧液昧下追搀彻崔零筑珐谆烈火第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树结点的删除过程树结点的删除过程2(2(续续) )n第一种情况当前结点第一种情况当前结点a平衡因子为平衡因子为0n如果它的左子树或者右子树被缩短，则它的如果它的左子树或者右子树被缩短，则它的平衡因子该为平衡因子该为1或者或者-1nmodified=FALSEn因为这样的变化不会影响到上面的结点，调因为这样的变化不会影响到上面的结点，调整可以结束整可以结束蛀痹喂疙超瑞诡途澄孜苏狂阶续琳宣缠浚敢碉不蔷喘温踞耕烹登撇赴粱恳第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树结点的删除情况树结点的删除情况1 1图示图示番苫昭沃瞧礁脆拢罗呐宣脊洛蛾炔泉政菠频懈盆凌耽箔梳礼羚鹊信写峻制第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树结点的删除过程树结点的删除过程2(2(续续) )n第二种情况是当前结点第二种情况是当前结点a平衡因子不为平衡因子不为0，但是其较高的子树被缩短，但是其较高的子树被缩短n则其平衡因子修改为则其平衡因子修改为0nmodified=TRUEn需要继续向上修改需要继续向上修改卉霞零粗警虑拽未刑歧今凉宵垄见块鹰疤酵暂戚扰芥料立军梯肥敢奶邯浩第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树结点的删除情况树结点的删除情况2 2图示图示戏棘热鹿夜姚恼词剩调捂时筐贡抠佑膝瞩锁亩汞氨釉烁耗趴谣圈钱烷泛腋第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树结点的删除过程树结点的删除过程2(2(续续) )n第三种情况是当前结点第三种情况是当前结点a平衡因子不为平衡因子不为0，且它，且它的较低的子树被缩短的较低的子树被缩短n结点结点a必然不再平衡，假设其较高子树的根结必然不再平衡，假设其较高子树的根结点为点为b，出现下面三种情况，出现下面三种情况n情况情况3.13.1：b b的平衡因子为的平衡因子为0 0n单旋转单旋转nmodified=FALSE modified=FALSE n情况情况3.23.2：b b的平衡因子与的平衡因子与a a的平衡因子相同的平衡因子相同n单旋转单旋转n结点结点a a、b b平衡因子都变为平衡因子都变为0 0nmodified=TRUEmodified=TRUE梧镍布伊砒躲亥豫披腔壬补易喉炙客敬赊剐廉丁篱绿钒忍占凝峡雀参宝开第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n情况情况3.33.3：b b和和a a的平衡因子相反的平衡因子相反n双旋转，先围绕双旋转，先围绕b b旋转，再围绕旋转，再围绕a a旋转旋转n新的根结点平衡因为为新的根结点平衡因为为0 0n其他结点应做相应的处理其他结点应做相应的处理n并且并且modified=TRUEmodified=TRUE赔渐拦校派蒂凹锨咯感弄峙澜饼满椽瓤搁淡瘟甚惟也伎螺锄殷扑旺色革谱第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树结点的删除情况树结点的删除情况3 3图示图示玩贴仰割前桥帮棉虞钠荚遮果亢睡姿湾札泳铂抱粮洞面谓舰断罕蝎腆涅瞪第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树结点的删除情况树结点的删除情况3 3图示图示揪和堑玩孽僳臀伙迭浴仓绥刘荚风柄昏凶欢师伸喧尽缉姻啥抉冯尚扁映喷第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 删除后的连续调整删除后的连续调整n从被删除的结点向上查找到其祖父结点从被删除的结点向上查找到其祖父结点n然后开始单旋转或者双旋转操作然后开始单旋转或者双旋转操作 n旋转次数为旋转次数为O(log n)n连续调整连续调整n调整可能会导致它祖先结点发生新的不平衡调整可能会导致它祖先结点发生新的不平衡n这样的调整操作要一直进行下去，可能传递这样的调整操作要一直进行下去，可能传递到根结点为止到根结点为止 渝近殊坯捡抗弯可欠嘶奠巧疲贞符妒骇耻事腊俱匝螟摈蹿崔暮扫吊垒伍土第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树删除的例子树删除的例子洼琐腋酷趣滓恒甭蒲巾翅兆瑞厂晴一祟甭宅捌缴磨型稳逞歌渠衰太唬犊瘩第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树删除的例子树删除的例子垛疑梳朗螟棉鄂萎赤爪奴蒜叠曙瑶耿歼蝇瓤纹磋晦磨屿景瘴渐鸡鞍晦敝认第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树删除的例子树删除的例子送窖败盆宰贞绚珐瘩逻茬屎绢此鲍驹蛾芝堂箱杀氰囱更壮疟锄六膝恫浓挽第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树的高度树的高度n具有具有n个结点的个结点的AVL树的高度一定是树的高度一定是O(logn)nn个结点的个结点的AVL树的最大高度不超过树的最大高度不超过Klog2 nn这里这里K是一个小的常数是一个小的常数n最接近于不平衡的最接近于不平衡的AVL树树 n构造一系列构造一系列AVL树树T1，T2，T3，。n其中其中Ti的高度是的高度是in每棵具有高度每棵具有高度i的其它的其它AVL树都比树都比Ti的结点个数多的结点个数多n或者说，每棵这样的树都是具有同样的结点数目或者说，每棵这样的树都是具有同样的结点数目的所有的所有AVL树中最接近不平衡状态的，删除一个树中最接近不平衡状态的，删除一个结点都会不平衡结点都会不平衡综褒虑誉天演嗽蛤稿嘎佐酪谨舍气若冲考辨滋沸蔚酵廖奋默臃圈雇稍未离第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 根弃饿盐湾锻冻敷茂鸣廖醉纯舱此听滁捌晕蓟息堪伯婴荤糙涛惧这佯一炕第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 高度的证明（推理）高度的证明（推理）n可看出有下列关系成立：可看出有下列关系成立：nt(1)=2nt(2)=4nt(i)=t(i-1)+t(i-2)+1n对于于i2此关系很此关系很类似于定似于定义Fibonacci数的那些关系：数的那些关系：nF(0)=0nF(1)=1nF(i)=F(i-1)+F(i-2)氨砍缝帧汛登筹宵立涣揩毁然露释裂瑟遏吴淹夕涡靳瑟择里祝吁与泅藉久第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 高度的证明（推理续）高度的证明（推理续）n对于于il仅检查序列的前几序列的前几项就可有就可有nt(i)=F(i+3)-1nFibonacci数数满足足渐近公式近公式n由此可得近似公式由此可得近似公式污晓缩规鹅趴疥亨闪诫操馁腹做带掸糖湾遁馈蛇食弥片碰骸空槐窗仙怨确第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 高度的证明（高度的证明（结果结果）n解出高度解出高度i与结点个数与结点个数t(i)的关系的关系 n由由 换 底底 公公 式式 logX=log2X/log2和和log20.694我我们求出近似上限求出近似上限nt(i)=nn所以所以n个结点的个结点的AVL树的高度一定是树的高度一定是O(logn)送腮惨谩湛镀湛窜腆恋尸石丛取隐趁踩摹众并拦厂旷龟悲踏哑钦刑严韵而第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page AVL树的效率树的效率 nAVL树的检索、插入和删除效率都是树的检索、插入和删除效率都是O(1og2 n)，这是因为具有，这是因为具有n个结点的个结点的AVL树的高度一定树的高度一定是是O(logn) nAVL树适用于组织较小的、内存中的目录。而树适用于组织较小的、内存中的目录。而对于较大的、存放在外存储器上的文件，用二对于较大的、存放在外存储器上的文件，用二叉搜索树来组织索引就不合适了叉搜索树来组织索引就不合适了 n在文件索引中大量使用每个结点包括多个关键在文件索引中大量使用每个结点包括多个关键码的码的B-树，尤其是树，尤其是B+树树 所搬设味幸匀莹蛰注手倚正痢描贞镭终性月宦音妖酱乏骤舒窗貌埃管湖护第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 12.2.3伸展树伸展树 n伸展树不是一个新数据结构，而只伸展树不是一个新数据结构，而只是改进是改进BST性能的一组规则性能的一组规则n保证访问的总代价不高，达到最令人保证访问的总代价不高，达到最令人满意的性能满意的性能n不能保证最终树高平衡不能保证最终树高平衡纯量浩哇徒厅竖啥惺胁掂渺曹鹏摧打软尧务姓保阻乱摩竣蓄珐陨演痕绎莫第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 展开展开(splaying) n每当访问一个结点每当访问一个结点x时时(例如，当例如，当x被插入、删除被插入、删除或者是检索目标时或者是检索目标时)，伸展树就完成一次称为展，伸展树就完成一次称为展开开(splaying)的过程的过程 n展开处理把结点展开处理把结点x移到移到BST的根结点的根结点n当删除结点当删除结点x时，展开过程把结点时，展开过程把结点x的父结点移到根的父结点移到根结点结点 n像在像在AVL树中一样，结点树中一样，结点x的一次展开包括一的一次展开包括一组旋转组旋转(rotation)n一次旋转通过调整结点一次旋转通过调整结点x相对于其父结点和祖父结相对于其父结点和祖父结点的位置，把它移到树结构中的更高层点的位置，把它移到树结构中的更高层 佛抉弛蔓筛丢肃接次锚谢搜允帆遣顺聂融哆祖篷辐侦桶间拿狡击娥州谅舅第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 单旋转单旋转(singlerotation) n当被访问结点是根结点的子女时，完成单旋转当被访问结点是根结点的子女时，完成单旋转, ,它基本上在保持它基本上在保持BSTBST特性的情况下把结点特性的情况下把结点x x与它与它的父结点交换位置的父结点交换位置 汽请插克匿汽虫仟恕畜丝椰肉辆汤讲缅奎国粗渐役丫猩厚稚盼味此访沪捅第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 双旋转双旋转(doublerotation) n双旋转涉及到双旋转涉及到n结点结点xn结点结点x的父结点的父结点(称为称为y)n结点结点x的祖父结点的祖父结点(称为称为z)n双旋转的结果是把结点双旋转的结果是把结点x在树结构中向上在树结构中向上移两层移两层灸旅聚义苑跑露唤印柴亏散之谊捂换会禾阉曹状啪汁悟扼眉棒鲜退康桐职第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n双旋转分为两类双旋转分为两类n一字形旋转一字形旋转(zigzigrotation)n也称为同构调整（也称为同构调整（homogeneousconfiguration）；）；n之字形旋转之字形旋转(zigzagrotation)n也称为异构调整（也称为异构调整（heterogeneousconfiguration） 剑纵并缓今臆津哦奏捻爷规伍北幂错急晤篙菏卷叁冰打狼敌艰瘫戏占转镶第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 一字形旋转一字形旋转 n当出现以下两种情况之一时，就会发生一字形当出现以下两种情况之一时，就会发生一字形旋转：旋转：n1.结点结点x是结点是结点y的左子女，结点的左子女，结点y是结点是结点z的的左子女。左子女。n2.结点结点x是结点是结点y的右子女，结点的右子女，结点y是结点是结点z的的右子女。右子女。 指疥诸氯杖野靠诧俊弱过磺禹唐柴吁好锯淆恿璃咀避踩恐宴莽渣著盈肠鲸第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 一字形旋转图示一字形旋转图示袍赖专垄薛洁诺隅筒照环戮恨拓淤论绝萍册舰猎巾昧罢温嘿奇叹东掷掘捶第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 之字形旋转之字形旋转 n出现以下两种情况之一时，就会发生之字形旋出现以下两种情况之一时，就会发生之字形旋转：转：n1.结点结点x是结点是结点y的左子女，结点的左子女，结点y是结点是结点z的右子女。的右子女。n2.结点结点x是结点是结点y的右子女，结点的右子女，结点y是结点是结点z的左子女。的左子女。癌昧示逆饮肿贸倾彼继教柬馆扭榴懒痘感骸确催摘酝恿大票绎霸芜础衔弧第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 之字形旋转图示之字形旋转图示披樱致迸垂卤赦扛谓滋爱莱聊婉虫鼓嘶抱停沥氖傻孺竞栖侩搀财赔秦刹幻第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 两种旋转的不同作用两种旋转的不同作用n之字形旋转之字形旋转n使子树结构的高度减使子树结构的高度减1n趋向于使树结构更加平衡趋向于使树结构更加平衡n一字形提升一字形提升n一般不会降低树结构的高度一般不会降低树结构的高度n它只是把新访问的记录向根结点移动它只是把新访问的记录向根结点移动蠕假寿甩痒垫赃婿杀杏今槽阜爹廷手俩戈比影食屋赛老护瘫敝渔舍咳络筋第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 伸展树的调整过程伸展树的调整过程n一系列双旋转一系列双旋转n直到结点直到结点x到达根结点或者根结点的子女。到达根结点或者根结点的子女。n如果结点如果结点x到达根结点的子女到达根结点的子女n进行一次单旋转使结点进行一次单旋转使结点x成为根结点成为根结点n这个过程趋向于使树结构重新平衡这个过程趋向于使树结构重新平衡n都会使访问最频繁的结点靠近树结构的根层都会使访问最频繁的结点靠近树结构的根层n从而减少访问代价从而减少访问代价 赫柬陇哟晦赢成岸艳梳嘉尿诽盗蓖迢淫骏素备断优绥傻拾庆齿拈笔叁杂缝第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 伸展树的调整过程伸展树的调整过程出梦颂挚望涸汰翠莲朱伊牺菲湃舞突弛却糕胳格乎猜激铡嘴咎体敌患栽讫第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 伸展树的调整过程伸展树的调整过程拯化丙品惹彭黔妒婿黍遇卸邻胺抓桔吉零孟枫攘粪淬孵罕服揖预顶腿挚褐第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 伸展树与伸展树与AVL树的差别树的差别n伸展树与结点被访问（包括）的频伸展树与结点被访问（包括）的频率相关率相关n能够进行更加动态的调整能够进行更加动态的调整n而而AVL树的结构与插入、删除或者树的结构与插入、删除或者是检索的频率无关是检索的频率无关n只与插入、删除的顺序有关只与插入、删除的顺序有关庚芦碰腻园娶绸诊逞苗熙折则测丽舆换帅哟模霉粘裔杉铺钙岔妇别忿翼件第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 伸展树的效率伸展树的效率n对于一个包括对于一个包括n个结点的伸展树，进行一个结点的伸展树，进行一组组m次操作次操作(插入、删除、查找操作插入、删除、查找操作)，当，当mn时，总代价是时，总代价是O(m logn) n伸展树不能保证每一个单个操作是有效率的伸展树不能保证每一个单个操作是有效率的n即每次访问操作的平均代价为即每次访问操作的平均代价为O(logn)n证明伸展树确实能够保证证明伸展树确实能够保证O(mlogn)时时间超出了这本书的范围间超出了这本书的范围 葫挽夫蒸巴盒宙味硅碟滔韧裁饱榜多怔征诛粹木孔沏窘滁联誓婚礁晚氧盈第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 12.3 12.3 空间数据结构空间数据结构 n前面所讨论过的前面所讨论过的BST、AVL等搜索树都等搜索树都是针对一个一维的关键码进行的是针对一个一维的关键码进行的 n多维数据不能简简单单的看作是多个一多维数据不能简简单单的看作是多个一维数据的组合维数据的组合n尽管做勉强也可以尽管做勉强也可以 n所以我们下面介绍一些常用的多维数据所以我们下面介绍一些常用的多维数据结构结构甲啤叙号伤僚常樟奏证困罢石氢辰眼粮稽德枚衰恋挣司狡鞋责头啤竭褐涣第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 12.3.1k-d树树 nk-d树是早期发明的一种用于多维检索的树是早期发明的一种用于多维检索的树结构，它每一层都根据特定的关键码树结构，它每一层都根据特定的关键码将对象空间分解为两个将对象空间分解为两个 n顶层结点按一个维划分顶层结点按一个维划分n第二层结点按照另一维进行划分第二层结点按照另一维进行划分n以此类推在各个维之间反复进行划分以此类推在各个维之间反复进行划分 n最终当一个结点中的点数少于给点的最大点最终当一个结点中的点数少于给点的最大点数时，划分结束数时，划分结束 软逐旺杠告侥汝乳潞库缅素膜慨帮脂酮痊诊泼繁圆穆入空服焚殷疵解痞绕第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 识别器识别器(discriminator) n在每一层用来进行决策的关键码称为识在每一层用来进行决策的关键码称为识别器别器(discriminator) n对于对于k维关键码，在第维关键码，在第i层把识别器定义为层把识别器定义为imodkn例如，对一个三维的关键码做检索，例如，对一个三维的关键码做检索，3个关个关键码（键码（x，y，z）标号分别为）标号分别为0、1、2n第一层是第一层是0mod3=0，所以使用关键码，所以使用关键码x，n第二层是第二层是1mod3=1，所以使用关键码，所以使用关键码y系裳断衍獭慕醒朝磊翁牲寨圭白尿协菩兰酮审椭徊痴藏槐基化戊煌磺酶碉第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 结点的分配结点的分配n在结点分配的时候首先比较该层的识别在结点分配的时候首先比较该层的识别器器n如果关键码小于识别器的值就放到左子树中如果关键码小于识别器的值就放到左子树中n否则放到右子树否则放到右子树n然后在下一层使用新的识别器来判断每然后在下一层使用新的识别器来判断每个结点的归属个结点的归属n识别器的值应该尽量使得被划分的结点识别器的值应该尽量使得被划分的结点大约一半落在左子树，另一半落在右子大约一半落在左子树，另一半落在右子树树纺途搓辆罪挺随侧巳豢求亚挖案械课了颁绣孟望智菱丛蕾抬朱咕趴菩媳描第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page K-DK-D树示例树示例酶榷土饮侦擒陨驻锰训目跑羔断饵讨麓员搀效顽弹冠阔揭熬胶喊烃哎堵宣第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page K-DK-D树的空间分解树的空间分解n上图是一个二维的上图是一个二维的k-d树，我们限制其取值范树，我们限制其取值范围为围为100100之内之内nk-dk-d树的每个内部结点树的每个内部结点n把当前的空间划分为两块把当前的空间划分为两块n交替地对两个维进行划分交替地对两个维进行划分n根结点把空间划分成两部分根结点把空间划分成两部分n其子结点进一步把空间划分成更小的部分其子结点进一步把空间划分成更小的部分n子结点的划分线不会穿过根结点的划分线子结点的划分线不会穿过根结点的划分线 nk-d树中的这些结点最终把空间分解为矩形树中的这些结点最终把空间分解为矩形n这些矩形是结点可能落到的各子树范围这些矩形是结点可能落到的各子树范围尝垛捻舟砷络纺蕾沪盾制赋甄篓议优毡驳裸纫破酥闲卓侨潍繁纵消舞紧悟第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page K-D树的检索树的检索 n交替地用识别器与各个维进行比较交替地用识别器与各个维进行比较n不断地划分区间缩小范围不断地划分区间缩小范围n直到找到需要的点为止直到找到需要的点为止 莹孝疾抵萝仓剔渴维蒙瓣烽放料诛粪伸虽帖逼怀手慈汁凭椎靠要婴仰无熔第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n例如，在上图检索点例如，在上图检索点F(80，70)n在根结点在根结点A，先用，先用80与与A的的X维比较维比较n80大于大于50，所以，所以F应该在应该在A的右子树，到达了结点的右子树，到达了结点C(70，30)；n比较比较F与与C的的Y维大小维大小n70大大于于30，所所以以F应应该该在在C的的右右子子树树，然然后后到到达达结结点点F，即即完完成成搜搜索索n如如果果最最后后到到达达的的结结点点指指针针是是NULL，则则检检索索结结束束，该该结结点不存在点不存在亭集淬傲哩隶鸥添拾唯内恼伦丙厅鹿摈糊甥武筷捕歼梢墨身锯帆沛艘师赏第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page K-D树的搜索算法树的搜索算法KDNode*KDTree:KdFind(KDNode*n,Valueval,intlev,intdimension)/n:开始搜索的结点，开始搜索的结点，val:要搜索结点的多维值要搜索结点的多维值/lev:n处于的深度处于的深度，dimension:k-d树的维数树的维数if(n=NULL)returnNULL;/无法找到该结点无法找到该结点elseif(val=n-val)returnn;/n既是搜索的结点既是搜索的结点elseintk=levmoddimension;/求得识别器的编号求得识别器的编号if(ValofD(n-value,k)ValofD(val,k)returnKdFind(n-left,val,lev+1,dimension);/小于识别器，在左子树小于识别器，在左子树elsereturnKdFind(n-right,val,lev+1,dimension);/大于识别器，在右子树大于识别器，在右子树缕征粥挽畅俄弟疏良哲漾痪兆堰淡邵疲淬盲遏浅督鼎指卡绿妄闲篡峙学塌第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page K-D树的删除树的删除n如果删除一个没有子结点的结点，不用做任何如果删除一个没有子结点的结点，不用做任何的调整的调整 n如果删除了一个有子结点的结点如果删除了一个有子结点的结点n如果只有一个子结点并且子结点没有自己的如果只有一个子结点并且子结点没有自己的子结点，那么就可以用它来取代被删除结点子结点，那么就可以用它来取代被删除结点的位置的位置 n而如果子结点还有自己的子结点而如果子结点还有自己的子结点，那么就需，那么就需要进行选择要进行选择掠躬您浩单陛宵掉蓉互拾迂冠邱查毙拇眼序蜕楔结窄坍茅细羡患赊姻厩矫第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page K-D树的插入树的插入n首先也要使用上面的检索算法首先也要使用上面的检索算法n如果返回一个非如果返回一个非NULLNULL值，那么说明该结点已值，那么说明该结点已经在树中；经在树中；n否则，在否则，在NULLNULL指针所在位置新建一个结点，指针所在位置新建一个结点，存储插入的值。存储插入的值。 炔败租垛坤隋坪轨盅霖捷粤彤刘憾怖蹲拳省烹争谰疤乒敏飘趣迭恨羽换啦第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page K-D树的删除（结点的选择）树的删除（结点的选择）n删除一个结点后需要从它的左右子删除一个结点后需要从它的左右子树中选择一个合适的结点来替代它树中选择一个合适的结点来替代它n该结点最好能够保持原来的空间划分该结点最好能够保持原来的空间划分 n最好的选择是左子树中当前维中值最大的最好的选择是左子树中当前维中值最大的一个结点一个结点n或者右子树中当前维值最小的一个结点或者右子树中当前维值最小的一个结点 籽地笛叉茵棺汛瑟允奎诅条栽装帮撑望似矮胞饱历句律扮昨甭看逊素鹏蹋第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page K-D树的删除（重复调整）树的删除（重复调整）n删除过程也是一个循环的过程，因为选删除过程也是一个循环的过程，因为选择一个结点代替当前删除结点将意味着择一个结点代替当前删除结点将意味着那个结点在它原来的位置被删除，所以那个结点在它原来的位置被删除，所以它的子结点也要进行相关的动作，直到它的子结点也要进行相关的动作，直到没有结点移动为止没有结点移动为止 务洋鸥畴燎柱胯牟痴豆寻九俏崎寥镰寄费幼澡蚀论朗效绦命烫焚檬互丝荆第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page K-D树的删除图示树的删除图示组伞恰谎汕熔随篆市谗运礼纷笆获忱阉韶徐勉更浇抑澡炉勘菏匆块玄嘴龟第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page K-D树的删除图示树的删除图示萄绣化走打橇瞅羹呸鞠废镊谅冗因瓮麓幌搓毁凡宇圾妨褪轿稽频磅击爬逊第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page K-D树的范围查找树的范围查找n使用使用k-d树可以进行范围查找树可以进行范围查找n欧氏距离欧氏距离胶戏称今傲贴传棕使赚闽才浆筏淄土驮渍相师幸恩摊考铣戒耀既钙欲讣已第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n例如，在二维的情况下，可以查找例如，在二维的情况下，可以查找X在一定范在一定范围的结点围的结点n如果到达某个结点发现识别器的关键码大于这个范如果到达某个结点发现识别器的关键码大于这个范围了围了n那么该结点的右子树就不用搜索了那么该结点的右子树就不用搜索了n因为它们必然都大于这个范围因为它们必然都大于这个范围n同理，如果识别器的关键码小于这个范围了同理，如果识别器的关键码小于这个范围了n该结点的左子树都不用搜索了该结点的左子树都不用搜索了琢泣诗碟综逝官胶遣磕述太凛摇粹倪亩捷迂扰乌耳胯袜价邯婴脓商泞涵壹第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page K-D树的范围查找树的范围查找在上图中查找与（在上图中查找与（50，70）距离小于）距离小于20的点的点n根结点根结点A A（5050，5555）显然满足要求）显然满足要求n进入左子树，发现点进入左子树，发现点B B（30，50）不在范围里面）不在范围里面n但是这并不是说左子树应该被抛弃但是这并不是说左子树应该被抛弃n70-50=20，所以结点，所以结点B B（30，50）的左边子树应该抛弃，因为）的左边子树应该抛弃，因为左边子树的左边子树的y2070-3020n不需要进入不需要进入C C的左子树，因为左边子树的的左子树，因为左边子树的y2080-5020，不需要进入，不需要进入F F的右子树，因为右的右子树，因为右边子树的边子树的x80n进入进入F的左子树，子结点的左子树，子结点G（60，60）复合要求）复合要求洱尧恒俊脾嗓伍袜圆宋燎衔斯吧必第务掀藻蕾垢尿牢捡万揣聊溢改饥帖铸第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page K-D树的不足树的不足 n其结构与输入数据的顺序也是有关的其结构与输入数据的顺序也是有关的n有可能导致它每个子树的元素分配不均衡有可能导致它每个子树的元素分配不均衡nBentley和和Friedman发明了发明了adaptivek-d树，树，n类似于类似于BSTn所有的数据记录都存储在叶结点所有的数据记录都存储在叶结点n内部结点只是用来在各个维之间导航内部结点只是用来在各个维之间导航n每一个识别器的选择不再依赖于输入的数据每一个识别器的选择不再依赖于输入的数据n尽量选择让左右子树的记录数目相等的值尽量选择让左右子树的记录数目相等的值 畴猾铱忽万骂诱恤永湿掠秘会铝伦掘蹈癣仓钙晾瓢纫涂咸肃歇涝笺邪姻涟第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 12.3.2PR四分树四分树 nPR四分树，即点四分树，即点-区域四分树（区域四分树（Point-RegionQuadtree） ：n每个内部结点都恰好有四个子结点每个内部结点都恰好有四个子结点n每个内部结点将当前空间均等地划分为四个每个内部结点将当前空间均等地划分为四个区域区域nNWNW（西北）、（西北）、NENE（东北）、（东北）、SWSW（西南）和（西南）和SESE（东（东南）南）nPR四分树也是对对象空间的划分四分树也是对对象空间的划分n完全四叉树完全四叉树 米僳天丫锤虱捉骤汁脾逾菠鸭搪庭庞悠胜勋三膳普粱讫挺告饺混泡仙惩屁第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PRPR四分树对空间的划分四分树对空间的划分n每个内部结点将当前空间均等地划分为每个内部结点将当前空间均等地划分为四个区域四个区域n如果子区域包含的数据点数大于如果子区域包含的数据点数大于1，那么就，那么就把该区域继续均等地划分为四个区域把该区域继续均等地划分为四个区域n依次类推，直到每个区域所包含的数据点不依次类推，直到每个区域所包含的数据点不超过一个为止超过一个为止 太棺束责淖肯迪钦湾柔央吠打拇急盈型牙炳届得歌标胜狈搪殷锅澡码龄帕第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PR树的图示树的图示硕诉使逆宽仆粕亮诽定掠基辊篮旁救羊稠础侩厅芝介鞠将屈剖赢真羚曳葛第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PR树的划分树的划分n上图所表示的上图所表示的PR四分树，其对象空间为四分树，其对象空间为128 128 ，并且其中包含点并且其中包含点A、B、C、D、E、F和和G n根结点的四个子结点把整个空间平分为根结点的四个子结点把整个空间平分为四份大小为四份大小为64 64的子空间的子空间nNW，NE，SW，SE nNW（包含三个数据点）和（包含三个数据点）和SE(包含两个数包含两个数据点据点) 需要进一步分裂需要进一步分裂 镰摄桔共裁鞠聘人碰杖制移佐勇禽胀维瘸缔躲仪映才青迭根魂鹰悍糖汪壬第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PR树的检索树的检索检索的过程与划分过程类似检索的过程与划分过程类似n例如，检索数据点例如，检索数据点D，其坐标为（，其坐标为（40，85）。）。n在在根根结结点点，它它属属于于SW子子结结点点（范范围围为为(0-64，64-127)）n进进入入SW子子树树，其其四四个个子子树树的的范范围围是是（0-32，64-96） 、 （ 32-64， 64-96） 、 （ 0-32， 96-127） 和和（32-64，96-127），），D应该位于下一个应该位于下一个NE子树中子树中nNE子子树树只只有有一一个个叶叶结结点点代代表表数数据据点点D，所所以以返返回回D的值。的值。n如如果果已已经经到到达达叶叶结结点点却却没没有有找找到到该该数数据据点点，那那么返回错误么返回错误留褪汕剪畏圃眠假镜纲窿服拐挣甄铸咸尾虱卞士乏噶期垣惨省吧替俯萌铡第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PR树的插入树的插入首先通过检索确定其位置首先通过检索确定其位置n如果这个位置的叶结点没有包含其他的数据点如果这个位置的叶结点没有包含其他的数据点n那么我们就把记录插入这里；那么我们就把记录插入这里；n如果这个叶结点中已经包含如果这个叶结点中已经包含P了了(或者一个具有或者一个具有P的坐标的记录的坐标的记录)n那么就报告记录重复；那么就报告记录重复；n如果叶结点已经包含另一条记录如果叶结点已经包含另一条记录Xn那么就必须继续分解这个结点，直到已存在的记录那么就必须继续分解这个结点，直到已存在的记录X和和P分别进入不同的结点为止分别进入不同的结点为止 褐停赢盏废斋鞋误熬钻耸茧吕瞒曾狗勘限纫剃讹桨掺荣至嘲连碱果普耍脊第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PR树的删除树的删除n删除纪录删除纪录n首先检索到首先检索到P所在的结点所在的结点Nn将结点将结点N所包含的记录改为空所包含的记录改为空n调整调整n查看它周围的三个兄弟结点的子树查看它周围的三个兄弟结点的子树n如果只有一个兄弟记录（不可能少于一个记录，否则就没有必如果只有一个兄弟记录（不可能少于一个记录，否则就没有必要分裂为四个子结点）要分裂为四个子结点）n把这四个结点的子树合并为一个结点把这四个结点的子树合并为一个结点N，代替它们的父结点，代替它们的父结点n这种合并会产生连锁反应这种合并会产生连锁反应n在上一层也可能需要相似的合并在上一层也可能需要相似的合并n直到到达某一层，该层至少有两个记录分别包含在结点直到到达某一层，该层至少有两个记录分别包含在结点N以及以及N的某个兄弟结点子树中，合并结束的某个兄弟结点子树中，合并结束轰蛙将晃却黍疮椭舔种学瞎寅垒织串魔粤饵厚糙品滤酞过秧叉辣蕴闻誊乃第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PR树的删除产生的合并树的删除产生的合并删除结点删除结点D导致的区域合并导致的区域合并囱饯古犁泉枚恼先菇傈技酬舒菱阁瞪倡碟脆茵签耕钩事事灯冈淀林肯帚佩第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PR树的区域查询树的区域查询 检索以某个点为中心、半径为检索以某个点为中心、半径为r的范围内所的范围内所有的点有的点n根结点为空根结点为空n查询失败查询失败n如果根结点是包含一个数据记录的叶结如果根结点是包含一个数据记录的叶结点点n检查这个数据点的位置，确定它是否在范围检查这个数据点的位置，确定它是否在范围内内枝灯榴颊林慷倡潘波别顽冈捉挠幻域磐氨补皂必洲鄂炭兵馏蒜壮炎廓疥骇第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n如果根结点是一个内部结点如果根结点是一个内部结点n在根结点确定包含该范围的子树在根结点确定包含该范围的子树n然后进入符合这种条件的子树然后进入符合这种条件的子树n递归地继续这样的过程递归地继续这样的过程n直到找不到这样的子树或者到达叶结点为止直到找不到这样的子树或者到达叶结点为止n当到达叶结点时当到达叶结点时n如果不包含任何的记录如果不包含任何的记录n则直接返回；则直接返回；n如果包含一个数据记录如果包含一个数据记录n则检查这个数据记录是否在范围之内，如果在就则检查这个数据记录是否在范围之内，如果在就返回该数据返回该数据 英乎捉伪烯共遇泊债吮莽杜哎芬榔曰挥啄盖忧带宦颠壹吉舱宏庙洋峪蹈文第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 12.3.3R*树树 nR*树是一种用于处理多维数据的数据结构树是一种用于处理多维数据的数据结构n用来访问二维或者更高维区域对象组成的空间数据用来访问二维或者更高维区域对象组成的空间数据n1990年由年由N.Bechmann，H.Kriegel，R.Schneider和和B.Seeger提出提出nR*树是对树是对R树的结构的改进树的结构的改进搜粟绰快洞挟险卡炔拿铡佛蚂轿秧鹿剪周釜膏袍吞玉阑妨陌乎掂斤到磅掷第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R树树nR树的结构类似于树的结构类似于B+树树n它可以用来存储多维的矩形它可以用来存储多维的矩形n每个非叶结点都存储着每个非叶结点都存储着(cp，rectangle)这种形这种形式的实体式的实体ncp表示指向子结点的指针表示指向子结点的指针nrectangle表示这个结点所代表的矩形表示这个结点所代表的矩形n该矩形是包括所有子结点的最小矩形该矩形是包括所有子结点的最小矩形n其实其实R树可以用来存储多维数据，矩形只是二树可以用来存储多维数据，矩形只是二维的情况维的情况陀婿氰倚诸丫诲众骏幌季灼渭寂嘱受逝土毙松摸匪愁抠右渣忍叭破督峦钮第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n每个叶结点一般存储形式为（每个叶结点一般存储形式为（Oid，rectangle）的实体）的实体nOid一般表示一个存储在数据库里面的空间一般表示一个存储在数据库里面的空间对象对象n而而rectangle表示能够包含这个空间对象的最表示能够包含这个空间对象的最小的矩形小的矩形 符恿脏籽杭吃晤豪孵附嚼把辈评您获饿栋涎寇匆键铁保日投蓖别置绘催本第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R树的图示树的图示左边图的矩形和右边的编号对应，而点则表示数据对象；右边是构建左边图的矩形和右边的编号对应，而点则表示数据对象；右边是构建好的一棵好的一棵R树，根结点包含两个（指针，矩形）的实体，叶结点包含指树，根结点包含两个（指针，矩形）的实体，叶结点包含指向数据的指针和矩形编号向数据的指针和矩形编号 恫婶鬃求掘熬从进逾氖纵背窘宪九住炉呼堆群榨儒裸饥捕犁知蚕端拟轩柠第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R树的性质树的性质假设假设m是是R树中一个结点所包含的最少实体个数，而树中一个结点所包含的最少实体个数，而M是是R树中结点可以包含的最多实体个数树中结点可以包含的最多实体个数nR R树应该满足下面的条件：树应该满足下面的条件：n1.1.根结点如果不是叶结点，那么应该至少有根结点如果不是叶结点，那么应该至少有2 2个子结点；个子结点；n2.2.每每个个既既不不是是叶叶结结点点也也不不是是根根结结点点的的内内部部结结点点所所具具有有的的子子结点数在结点数在m m至至M M之间；之间；n3.3.每个叶结点有每个叶结点有m m至至M M个实体，除非它是根结点个实体，除非它是根结点n4.4.所有的叶结点都处在同一层所有的叶结点都处在同一层印饮核文撤鸣步袜祖片椎甭酬弯镑隆呸咽蚜挖拢叔痊榴田耍酒总窒椅踏勘第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 矩形重叠覆盖矩形重叠覆盖nR树的主要问题就是矩形重叠覆盖树的主要问题就是矩形重叠覆盖nR树要支持数据库中的各种复杂查询树要支持数据库中的各种复杂查询n如果一个查询所需要的结果都在一个矩形区如果一个查询所需要的结果都在一个矩形区域里面那么速度将是最快的域里面那么速度将是最快的n很难找到一种合适的方法来确定单个矩很难找到一种合适的方法来确定单个矩形的大小形的大小n各个矩形之间复杂的关系各个矩形之间复杂的关系n调整一个矩形的大小必然会影响到很多与它调整一个矩形的大小必然会影响到很多与它相关的其他矩形相关的其他矩形衔榔陆演丙竖平忘襟鞍溉森税铝鹿由晌汁胎壳唉啄停脆析娥按致鸭碳盐烽第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R树中的矩阵重叠树中的矩阵重叠扯绩沮夯泌栋练哭察侵搐郎呢蝗姜且拥夹挞籍沈救搽遮缨梗于圣洋畦金峙第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 影响影响R树性能的因素树性能的因素n覆盖某个区域的矩形应该最小化覆盖某个区域的矩形应该最小化n矩形之间的重叠应该最小化矩形之间的重叠应该最小化n进行检索的时候能够减少需要搜索的路径进行检索的时候能够减少需要搜索的路径n矩形的周长应该尽可能的小矩形的周长应该尽可能的小臂淮贼榨盟斩数垮枢墓艺珊殴署抡须札可腻恕当攀耸筐蔑侈结耐注兽俯趋第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R树的动态插入算法树的动态插入算法 n基本的思想基本的思想n先选择一个合适的结点先选择一个合适的结点n如果该结点还有空位置就把数据的实体插入如果该结点还有空位置就把数据的实体插入其中其中n否则要分裂这个结点，将所有实体重新分配否则要分裂这个结点，将所有实体重新分配给分裂后的两个新结点给分裂后的两个新结点n选择算法和分裂算法是整个插入的关键选择算法和分裂算法是整个插入的关键僧坚腮根孜滇按谦语桔炉露脉孪玻悉芹嫌点拐券薯祁麻猎夏忘挛拴羔缅寅第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R树的选择算法树的选择算法 ChooseSubtree:1.将根结点赋予将根结点赋予N；2.ifN是叶结点是叶结点 返回返回N；else(1)选选择择N中中子子结结点点所所代代表表矩矩形形中中只只需需要要最最小小的扩充就可以包含插入数据的；的扩充就可以包含插入数据的；(2)对选中子结点递归调用对选中子结点递归调用ChooseSubtree；返回第返回第2步得到的结点。步得到的结点。泰雌昆装请熬幂瘦箩惨呵慧毒窑迷掺讳赐胎九瀑消之驻乐轨柿探衔供幅摔第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R树的分裂算法树的分裂算法 SplitNode/将将包包含含M+1个个实实体体的的结结点点分分裂裂为为2个个结结点点，并并且且重重新新分分配配实实体体1. 1. 调用调用PickSeed方法选择每个新结点的第一个实体；方法选择每个新结点的第一个实体；2.Repeat 调用调用DistributeEntry来给来给2个结点分配实体；个结点分配实体；Until实体已经被全部分配或者一个实体包含结点实体已经被全部分配或者一个实体包含结点M-m3. 3. 如果还有实体剩余，全部分配给另一个结点。如果还有实体剩余，全部分配给另一个结点。态伴懦郧坚洲壤剩碱洒焦国办朔泻杠早桂炊枚身命骏颂汛下奸烫缨五尼钎第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R树的分裂算法树的分裂算法n对于一个已经满了的结点，即具对于一个已经满了的结点，即具有有M个实体的结点个实体的结点nSplit算法将原来算法将原来M个实体和个实体和1新个新个实体分裂成实体分裂成m和和M-m+1两组两组n分配给两个新的结点分配给两个新的结点 每万稠冤脚貉瞎汽档磊灭籍标芝麻帖甘莽检尽尖兵贸塑碾冉积栖百芽荫日第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page nPickSeed方法方法n在全部在全部M+1个实体中，找到距离个实体中，找到距离最远的两个实体作为两个组的第最远的两个实体作为两个组的第一个实体一个实体n这样分裂出来的两个结点之间的这样分裂出来的两个结点之间的重叠覆盖将是最小重叠覆盖将是最小 暗框湿凄淖讽堡些狄铁弗嗅揖盖篙乃摸治票狙哀烫环绪拼秦支雏棱袄赢麦第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R树的分裂算法树的分裂算法(PickSeed)PickSeed1对对于于每每一一对对实实体体E1，E2，构构建建一一个个包包含含E1的矩形和的矩形和E2的矩形的最小矩形的矩形的最小矩形R；2D=面面积积（R）-面面积积(E1的的矩矩形形)-面面积积(E2矩形矩形)；返回返回D值最小的实体对。值最小的实体对。示焕挝士移检心绅晨裴肚朔玉测驻凳程翰粤遥祷馏淑熊铸挂槛抗丧迈聋巾第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R树的分裂算法树的分裂算法(DistributeEntry ) DistributeEntry1.调调用用PickNext方方法法选选择择下下一一个个需需要要分分配配的实体；的实体；2.2.计算为了包括该实体，每组实体需要扩计算为了包括该实体，每组实体需要扩大的面积，选择扩大较少的那个。如果大的面积，选择扩大较少的那个。如果两组所需要面积一样，那么依次按照优两组所需要面积一样，那么依次按照优先级选择面积较小的一组，实体少的一先级选择面积较小的一组，实体少的一组，两个组都加入。组，两个组都加入。 候搪刺甄滦企朱骗比威雄疮猖膨欲前哲软碧南餐差狙碱每尧咐踪驼滑鸳蚁第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R树的分裂算法（树的分裂算法（PickNext）PickNext1.对对于于每每一一个个还还没没有有被被分分组组的的实实体体，计计算算为为了了包包括该实体，每组实体需要扩大的面积括该实体，每组实体需要扩大的面积d1和和d2。2.选择选择|d1-d2|最大的实体最大的实体nPickNext方方法法每每次次选选择择一一个个最最容容易易区区分分属属于于那那组组的的实实体体，这这样样的的选选择择使使得得分分组组比比较较合合理理，也也避免了组内实体互相重叠。避免了组内实体互相重叠。云湛风匙臃樟平显虽恐醋遮升餐菲驱戎渣屈慑负袋哭呈五脸私靠戮顺僳老第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R树的缺陷树的缺陷R树的分裂策略会导致很坏的分裂出现树的分裂策略会导致很坏的分裂出现n考虑一种比较极端的情况，如果有一个实体和考虑一种比较极端的情况，如果有一个实体和另外另外n-1个距离很远，而那个距离很远，而那n-1个实体之间距离个实体之间距离很近很近n那么根据算法，我们选择这个实体与那那么根据算法，我们选择这个实体与那n-1个实体中个实体中的一个作为的一个作为Seed生成两个组生成两个组G1和和G2n然后向这两个组加入实体，每次都是加入到然后向这两个组加入实体，每次都是加入到G2中，中，直到直到G2中的实体到达中的实体到达M-m+1n剩下的实体必然都加入到剩下的实体必然都加入到G1中，导致中，导致G1的面积迅的面积迅速扩大速扩大nG1和和G2之间的交迭非常严重。这样分裂出来的结之间的交迭非常严重。这样分裂出来的结构使得查询效率很低构使得查询效率很低墅妄款咒厕金蔓羹咱趟峙冀坟暮皇辟役忌元产香矗钟椅翅户扎呕适想坚儡第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R树的改进树的改进R*树树 n在在R树中的分裂主要考虑的是矩形面积的树中的分裂主要考虑的是矩形面积的因素因素nR*树的插入算法，综合考虑树的插入算法，综合考虑n矩形面积矩形面积n空白区域空白区域n重叠重叠孺嘴孰畴歧使夯捷亭囤迭琐长翁脊嫂幌赖脾呀切陌还澳串补捻棉钵哇佰眉第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 重叠（重叠（overlap） n一一个个实实体体的的重重叠叠是是其其矩矩形形与与同同结结点点其其他他实体矩形的面积之交的和实体矩形的面积之交的和：醋族蝇充蛤拜滦娠捌颈概峭扮断捍稽按层桓谬猜草叙氛流熔航充靶维肿痢第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R*树的选择算法树的选择算法n与与R树的选择算法相比，树的选择算法相比，R*算法主要增算法主要增加了一个减少叶结点覆盖的步骤加了一个减少叶结点覆盖的步骤n增加检索的效率增加检索的效率n但试验证明提高的并不是很明显但试验证明提高的并不是很明显 好疯见求满敷忘塔迭钟遭伟领爷辽譬乘嚏碌非烁掉佛奏罗人山耪龋夹橙立第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R*树的选择算法树的选择算法Choose SubtreeChoose Subtree1 1将根结点赋给将根结点赋给N N；2 2if Nif N是叶结点是叶结点 Return N Return N； if if N N的的子子结结点点指指针针指指向向叶叶结结点点（即即N N的的子子结结点存储的实体是包含对象的矩形）点存储的实体是包含对象的矩形）（1 1）计计算算N N中中实实体体为为包包括括新新数数据据而而将将增增加加的的重重叠；叠；（2 2）选择重叠增加最小的实体；）选择重叠增加最小的实体；牵雀流盆阅答靳石曝擦沁啼戳岁妹巴豫碴锅囱攫挑贩咖亿颇莫厉减旦归挥第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R*树的选择算法树的选择算法（3 3）在在最最小小重重叠叠的的实实体体中中选选择择面面积积增增加加最最小的实体；小的实体；if Nif N的子结点并不是指向叶结点的的子结点并不是指向叶结点的（1 1）计计算算N N中中实实体体为为包包括括新新数数据据而而将将增增加加的的面面积积（2 2）选择面积最小的实体）选择面积最小的实体把选择的实体所指向的子结点赋予把选择的实体所指向的子结点赋予N N，循环执行，循环执行2 2 据占芋哲略卒疹捏周阵休朱森吕希毁票恼哗伏索渣摧滋抗簇哑弯水社镭咽第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R*树的分裂策略树的分裂策略n首首先先把把待待分分裂裂结结点点的的实实体体在在各各个个维维按按照照从从小小到到大大的的顺顺序序排排列列，再再按按照照从从大大到到小小的顺序排列。的顺序排列。n对对每每个个排排列列进进行行下下面面的的分分裂裂：把把所所有有M+1M+1个个实实体体在在k k处处（ ）分分成成两两个组个组n一组为（一组为（m-1m-1）+ k+ k个个n其他的放入另外一组其他的放入另外一组n然后给每种分裂策略评分然后给每种分裂策略评分 阔匣壶坯嫌艳企仲邪屉血玛辕瞪脏己鞋茅测裂脆施卖板蹭锁誊方剩揩汐艾第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R*树的分裂评分树的分裂评分1.Area-value:第第一一组组所所有有的的实实体体矩矩形形面面积积和和第二组所有的实体矩形面积和；第二组所有的实体矩形面积和；2.Margin-value:第第一一组组所所有有的的实实体体矩矩形形边边长长和和第二组所有的实体矩形边长和；第二组所有的实体矩形边长和；3.Overlap-value：第第一一组组所所有有的的实实体体矩矩形形面面积积与第二组所有的实体矩形面积的交与第二组所有的实体矩形面积的交钢咽荔努滩睡谅饥等境茁撇毡粒祭威视音仓急吨敢栅医搪置晚叼拜亩卵吓第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n这些方法也可以综合使用这些方法也可以综合使用n可以选择某个维某种排列方式中评分最低的可以选择某个维某种排列方式中评分最低的n也可以计算出来所有维上所有排列方式的评也可以计算出来所有维上所有排列方式的评分最低的分最低的n也可以也可以 选择总和中评分最低的选择总和中评分最低的 叉讥怖披冻之铰累募尧谗蒙印柴筏神蕊坑砧训受凌代丧荒奄皇循刽锭亨犀第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R*的分裂算法的分裂算法SplitNode1.调调用用ChooseSplitAxis来来决决定定在在哪哪一一个个维维上上进进行行分裂分裂2.调调用用ChooseSplitIndex来来选选择择最最好好的的分分裂裂方方式式（找到合适的（找到合适的K）3.将实体分配到两个组中将实体分配到两个组中 骡闽蒙肿床鼻钉乎棘见久桂浚胰博娃巷卜霹谢颗赫湘它抠钥凤皑螺乃圃蘑第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R*的分裂算法的分裂算法 (ChooseSplitAxis )n对于每一维对于每一维n计算按照升序排列的计算按照升序排列的Margin-valuen计算按照降序排列的计算按照降序排列的Margin-valuen选选择择所所有有维维中中Margin-value较较小的作为分裂用的维小的作为分裂用的维旅煽帧灸讥屈瘁策锦疤肚蛮玄萧谅甜腋慈绰澳褂爱氦族邱崔磨薛葬狞竿争第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R*分裂算法分裂算法(ChooseSplitIndex)(ChooseSplitIndex)n在分裂的维上在分裂的维上nfor(k=1;k=M-2m+2;k+)n计计算算分分裂裂的的Overlap-value的的值值，选选择择最最 小的小的Overlap-value的的k值值n如果有相同的值出现，那么计算如果有相同的值出现，那么计算Area-value，选择产生最小值的，选择产生最小值的kn实验证明当实验证明当m的大小是的大小是M的的2/5时，上面时，上面的算法得到最好的效率的算法得到最好的效率兼瘩擒讫虞杠靠岁阿恢恭碱昆娜窑堕千醒斋伏棘误汛守揍执纺烁阑乱喘叼第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 删除和重插入删除和重插入 nR树和树和R*树都是动态生成的，它们的树树都是动态生成的，它们的树结构与插入数据的顺序相关结构与插入数据的顺序相关n在在R树中可能存在不合适的结点，它们被过树中可能存在不合适的结点，它们被过早地插入而影响了现在的效率早地插入而影响了现在的效率n每次的分裂也都是在当前状态下做出的，也每次的分裂也都是在当前状态下做出的，也许这样的分裂并不适合后来的情况许这样的分裂并不适合后来的情况n删除当前不合适的结点并且进行重新插删除当前不合适的结点并且进行重新插入入n实验证明这种方法可以大大提高效率实验证明这种方法可以大大提高效率 盟本谋氧锌含忌撞盔连锄堑恐侈兽野昨磕堵愁应狂粗铸桓恫獭斡翌争巢拱第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R*树的树的 完整插入算法完整插入算法插入算法插入算法Insert1调调用用ChooseSubtree选选择择插插入入实实体体E的的合合适适位位置：结点置：结点N；2如果如果N的实体数目小于的实体数目小于M，插入，插入E； 如如 果果 N的的 实实 体体 数数 目目 等等 于于 M， 调调 用用OverflowTreatment(L)处理重新插入的情况处理重新插入的情况 其中其中L是是N所在的层数；所在的层数；陋的壁保掩梗奇挫全厩倪慢恶睦喇豌械俊林锗脯僵捂脂汰禁酗熟莎共炽肉第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R*树的树的 完整插入算法完整插入算法3如如果果OverflowTreatment被被调调用用，并并且且分分裂裂已已经经进进行行，那那么么如如果果上上一一层层也也出出现现实实体体数数目目等等于于M的情况，传递的情况，传递OverflowTreatment； 如如果果分分裂裂是是针针对对根根结结点点的的，那那么么需需要要新新建建一一个根结点；个根结点；4调调整整在在插插入入结结点点到到根根结结点点路路径径上上所所有有的的实实体体矩形，让它们是包含子结点矩形的最小矩形矩形，让它们是包含子结点矩形的最小矩形矣噶精兢夺放济溉悠然嘘育谱净借切霓狗袍乌渭檄珊煤枕尖忱舀识详通巳第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 溢出处理：溢出处理：OverflowTreatmentif非非根根结结点点and这这是是在在给给定定层层次次的的插插入入过程中的第一次调用过程中的第一次调用 调用调用reinsert方法；方法；else调用调用split方法方法 瘁舆迭庸散囊足窘唱接麦辣袭墙妖裔饶冰宽迭豫波辛出椅溯彤值恒誉孔擂第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 重插入算法：重插入算法：Reinsert n计算结点计算结点N的的M+1个实体矩形的中心和代表个实体矩形的中心和代表N的矩形（包含的矩形（包含M个实体的矩形）的中心之间的个实体的矩形）的中心之间的距离距离 n按照距离的降序给实体排序按照距离的降序给实体排序 n删除前删除前p个实体，调整个实体，调整N的矩形大小的矩形大小 n调用调用insert重新插入被删除的重新插入被删除的p个实体，插入可个实体，插入可以按照递增或者递减的顺序以按照递增或者递减的顺序 注注释：p是一个常数，试验证明是一个常数，试验证明p取取M的的3/10最好最好 殿遮糖约置惹蚜缴册撩级账理肃原橇善政牢吠婆拭旁盔舅这单诀油铬头攫第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入时的重构插入时的重构n每一层的第一次每一层的第一次overflow的处理将导致的处理将导致p个实体个实体被重新分配被重新分配n它们如果再次被分配到同一个实体可能导致这它们如果再次被分配到同一个实体可能导致这个实体的分裂个实体的分裂n它们也可能被分配到不同的实体，这也许还会它们也可能被分配到不同的实体，这也许还会导致分裂，但是大多数情况下不会出现分裂导致分裂，但是大多数情况下不会出现分裂 竿渔总呈菇表恕劫薯岿需楷朵蹲乾下尝珠袍剪攻蛙绎法谊腿肆刻抽乒醚椰第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page R*的使用的使用nN.Bechmann，H.Kriegel，R.Schneider和和B.Seeger对对R*树做了树做了很多的试验很多的试验nR*树代价仅仅稍微高于树代价仅仅稍微高于R树树nR*树可以同时支持点和其他空间数据树可以同时支持点和其他空间数据n所以所以R*树应用非常广泛树应用非常广泛 魏仙缆爸名削谱则犁继孵纷雹殆患涂邦枪吸摹聊覆故窘爬谬挣鼠吵科恭怀第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 树形结构的应用树形结构的应用n树形结构是一种应用非常广泛的结构。树形结构是一种应用非常广泛的结构。除利用树形结构建立索引外（例如除利用树形结构建立索引外（例如BST树、树、B+树），在许多算法中常常利用树树），在许多算法中常常利用树形结构作为中间结构来表达问题空间，形结构作为中间结构来表达问题空间，以求解问题、确定对策等。以求解问题、确定对策等。n这里将介绍树形结构的两个有趣应用这里将介绍树形结构的两个有趣应用决策树和博弈树决策树和博弈树 钙丧箔捐茬斌恩讹拳骂浅链劲惯纲氛玛沏颖择殃戳栽误泳瞧撒涪丈甩鱼潘第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 12.4.1决策树决策树 n决策问题就是要求根据一些给定条件来确定应决策问题就是要求根据一些给定条件来确定应采取什么决策行动采取什么决策行动 n例如，在保险公司的业务中，当一个顾客申请例如，在保险公司的业务中，当一个顾客申请汽车保险时，公司按如下规则根据顾客的条件汽车保险时，公司按如下规则根据顾客的条件决定是否接受他的申请，以及向他收多少保险决定是否接受他的申请，以及向他收多少保险费费 ：仆疗咎杖官诅唱混好硝半赵朴翁灭之惯鲜得娜景盯丈震掉涎暂灵朋杨涛漳第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n如如果果一一个个顾顾客客年年龄龄不不超超过过25岁岁，并并且且在在过过去去3年年中中出出过过两两次次或或两两次次以以上上交交通通事事故故，则则不不接接受受他的申请。他的申请。n如如果果一一个个顾顾客客已已婚婚或或年年龄龄超超过过25岁岁，并并且且在在过过去去3年年中中出出过过两两次次以以下下交交通通事事故故，则则向向他他收收基基本保险费。本保险费。n如如果果一一个个顾顾客客年年龄龄超超过过25岁岁，但但在在过过去去3年年中中出出过过两两次次或或两两次次以以上上的的交交通通事事故故；或或年年龄龄不不超超过过25岁岁且且未未婚婚，但但在在过过去去3年年中中出出过过两两次次以以下下的的交交通通事事故故，则则除除向向他他收收基基本本保保险险费费外外，还还要要加收加收50的附加保险费。的附加保险费。娠迫拣属颐篷慎拳撒假彩肛涪愿裴腆闺咯已募个收醋帝恒鸽独讲赛方丈景第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 决策表决策表 赊娠乓憨浚凯限幂一钻馒条虏敏降娟菩蕴纸叉镰拉詹利谜赁烈啼斟韭蹦伟第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 决决策策表表转转换换成成二二叉叉树树形形式式决决策策树树 n二二叉叉决决策策树树中中的的分分支支结结点点代代表表条条件件测测试试，测测试试结结果果确确定定下下面面的的测测试试在在哪哪棵棵子子树树上上进进行行，二二叉叉决决策树的树叶代表选定的规则。策树的树叶代表选定的规则。n转转换换的的方方法法是是反反复复地地把把原原来来的的问问题题分分解解为为两两个个较较小小的的子子问问题题。令令C是是决决策策表表中中几几个个条条件件项项构构成成的矩阵，选择某个条件项的矩阵，选择某个条件项Ci，将，将C中满足条件中满足条件nCi，j=Y或或Ci，j=的的那那些些列列j构构成成CY(去去掉第掉第i行行)，n将将C中中满满足足条条件件Ci，j=N或或Ci，j=的的那那些列构成些列构成CN(去掉第去掉第i行行)速呛廷酥阜靠抛蘸窝块镶剑谐哦珍帅慷铝拳肝玉脸赌仿溪且座奎涸略盟上第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n然后用条件测试然后用条件测试Ci作为根结点，并把作为根结点，并把CY和和CN作为根作为根Ci的两个子结点。的两个子结点。n继续构造继续构造CY和和CN的决策子树，如此进行的决策子树，如此进行下去，直至下去，直至CY或或CN中只有一行时就可作中只有一行时就可作出最后的决定，用树叶代表规则出最后的决定，用树叶代表规则 沤占促受荐喻寒由氨令蛋撑盐厂蔬灼跟蜀吏贡六抚程太圣啪绊灸刚凛呢周第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 将上面的决策表变为决策树的过程将上面的决策表变为决策树的过程酝探茫矮蘸砍眨慌锡扣滇狼呛沈霖署重钝吻容比惧涟敛害右仿亩步痰慨柿第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 由上面的决策表最后得到的决策树由上面的决策表最后得到的决策树扔嘎亦陕剧卿坚稚烟桥坍授橱扑饲乎停吊炸钾酪端详彰郊诀偶商淤胡床墅第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 去掉多余的比较步骤去掉多余的比较步骤绵只屁描丁殖执呀壮登绷咎苦袄新梅掖知休懈汹我绞绵晰瞩哺窄夹芋伯侦第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 根据决策树写出解决决策问题的根据决策树写出解决决策问题的算法算法 *算法算法12-6保险公司的决策算法保险公司的决策算法*struct/顾客信息记录类型定义顾客信息记录类型定义char*name;/顾客姓名顾客姓名boolmarried; /是否已婚是否已婚intage;/年龄年龄intaccident_count;/交通事故次数交通事故次数CustomerRecord;voidJudge(CustomerRecordcustomer)/决策决策过程算法程算法coutcustomer.name=2)/先判断先判断C3匿借瑰寐矿热秋碟妨岂控粉伙辖硒忿墅摆村沥纶谋尚莆岿虽迁励陪们詹忍第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page if(customer.age=25)/C2cout”R1”;elsecout”R3”;elseif(customer.age=25)/C2if(customer.married)/C1cout”R5”;elsecout”R2”;塌污醒烟砸筷场祖痪枕雇匙浓城工郴挨免网蜀捶啸塑岩外窜弘沟颖叉辽蛤第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page elseif(customer.married)/C1cout”R5”;elsecout75”，如果是，则以，如果是，则以81为分界点，否则以为分界点，否则以67为分界为分界点，类似地进行下去，直到得出最后的四分制点，类似地进行下去，直到得出最后的四分制GPA成绩成绩 嗓帚谰笔哦噎蔑抵他笺酪月宗每歧状欢扭获聋揣揭酗赂苦葡店将蹿烷绣译第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 馆压猾火帕抢放漂斗贼肺逞由脏颠蹬酚化壮旨裤朱服枣沧亲旋氰瓶抉汾恬第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 决策树应用于数据挖掘（决策树应用于数据挖掘（DataMining） n这里主要介绍在数据挖掘中如何基于决策树来这里主要介绍在数据挖掘中如何基于决策树来进行分类进行分类 n分分类类要要解解决决的的问问题题是是为为一一个个事事件件或或对对象象归归类类。一一般般是是在在已已有有数数据据的的基基础础上上，用用机机器器学学习习的的方方法法训训练练出出个个分分类类函函数数或或构构造造出出一一个个分分类类模模型型，即即我我们通常所说的分类器们通常所说的分类器(Classifier)。n该该函函数数或或模模型型能能够够把把数数据据库库中中的的数数据据纪纪录录映映射射到到给给定定类类别别中中的的某某一一个个，从从而而可可以以应应用用于于数数据据预预测。测。反缔雌尔很奈暮锦谋仍仓谴找沁耀抽转赛液赊儡及毛菇咨剑装宪萨套邢窗第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n要要构构造造分分类类器器，需需要要有有一一个个训训练练样样本本数数据集作为输入。据集作为输入。n训训练练集集(Training (Training set) set) 由由一一组组数数据据库库记记录录构构成成，每每个个记记录录是是一一个个由由有有关关字字段段值值组组成成的的特特征征向向量量，我我们们把把这这些些字字段段称称做做属属性性(Attribute)(Attribute)，把把用用于于分分类类的的属属性性叫叫做做标标签签(Label)(Label)，标标签签属属性性也也就就是是训训练练集集的类别标记。的类别标记。佩们事狈披瓷喝惋缓逝围晤键进痞养女如蕊绍廓茫绷敬敷辉唁课粥翅艾宋第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n一一个个具具体体的的样样本本的的形形式式可可以以表表示示为为(v(v1 1, , v v2 2，. . ，v vn n；c), c), 其其中中v vi i 表表示示字字段段值值，c c 表表示示类类别别。训训练练集集是是构构造造分分类类器器的的基基础础。标标签签属属性性的的类类型型必必须须是是离离散散的的，且且标标签签属属性性的的可可能能值值的的数数目目越越少少越越好好（最最好好是是两两三三个个值值）。标标签签值值的的数数目目越越少少，构造出来的分类器的错误率越低。构造出来的分类器的错误率越低。党袁旋甘嗓综擎吸犬歪魏愁铜嚣晰燃窿玉粮看蜀噪湾拥荧瞅傀万敞窟坊肃第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 使用决策树分类的过程使用决策树分类的过程n将连续型属性值将连续型属性值“离散化离散化” n利利用用几几个个变变量量（每每个个变变量量对对应应一一个个问问题题）来来判判断所属的类别，最后每个叶子都对应一个类别。断所属的类别，最后每个叶子都对应一个类别。n在每个结点都会遇到一个问题，对每个结点上在每个结点都会遇到一个问题，对每个结点上问题的不同回答导致不同的分支，最后会到达一问题的不同回答导致不同的分支，最后会到达一个叶子结点。个叶子结点。棱关吟琶脱宾窘尝棺陛予允海温义懊斗郡木军卿打猪碾琢邻工限想硷栋芒第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 12.4.2 12.4.2 博弈树博弈树 n博弈树（博弈树（gametree）最初主要应用在人）最初主要应用在人机对弈的棋类程序中机对弈的棋类程序中 ntic-tac-toe的的游游戏戏规规则则：从从一一个个空空的的棋棋盘盘开开始始，甲甲乙乙二二人人轮轮流流往往棋棋盘盘上上的的空空格格子子中中放放棋棋子子。判判定定胜胜负负的的方方法法是是：若若某某一一方方者者有有三三枚枚棋棋子子连连成成一一横横行行，或或一一竖竖列列，或或一一对对角角线线，则则该该方方获获胜胜；若若直直至至整整个个棋盘被占满还没有一方获胜，则为平局。棋盘被占满还没有一方获胜，则为平局。倪瞳豫镍抚舶桑盟柠拘黄惮铃广紫星釜炯才淫倚勘周拌俭即玄酞袍什徐这第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 恨沼食粳橙孰苞淀涛开纲榷亢退提单沏跃送超牟茨进匙埋戮里眠便杜流狼第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n上图描述了初始状态上图描述了初始状态 作为树根，这作为树根，这时轮到甲放置棋子。甲放置完棋子后的时轮到甲放置棋子。甲放置完棋子后的所有可能的棋盘状态，都作为根的子结所有可能的棋盘状态，都作为根的子结点出现在树的第一层。点出现在树的第一层。n第二层的结点是轮到乙放置棋子时的棋第二层的结点是轮到乙放置棋子时的棋盘状态，乙从第一层的某个结点出发，盘状态，乙从第一层的某个结点出发，选择某个方格放置棋子后的所有可能棋选择某个方格放置棋子后的所有可能棋盘状态都作为该结点的子结点出现在第盘状态都作为该结点的子结点出现在第二层二层(由于版面限制，第二层的结点未全由于版面限制，第二层的结点未全部画出部画出) 悔菇憋捶亢龋梅邮钒最割慑狗积笺首香村屉泡投援顾缝袖富沼匪淄踌骗蔗第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n上图就称为上图就称为“博弈树博弈树” n这棵树的第二层并不是游戏终止时的棋盘状态。这棵树的第二层并不是游戏终止时的棋盘状态。我们还可以画出第三层，第四层我们还可以画出第三层，第四层的结点。但的结点。但一般情况下，由于计算机存储器大小和运算速一般情况下，由于计算机存储器大小和运算速度的限制，不能把博弈树一直构造到游戏终止度的限制，不能把博弈树一直构造到游戏终止时的棋盘状态，而只能构造到一定深度。时的棋盘状态，而只能构造到一定深度。n上图是一棵深度为上图是一棵深度为2的的tic-tac-toe游戏博弈树游戏博弈树 龋硅蛋团衫谍晕瞄餐敦门筛霓痛替弛欢糯溉瘦钻哨赖判敖通至反魁何酪术第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 根据博弈树找到最佳行为根据博弈树找到最佳行为n假设计算机作为游戏者甲，与他的对手游戏者假设计算机作为游戏者甲，与他的对手游戏者乙进行乙进行tic-tac-toe游戏。游戏。n下棋者总是希望赢棋的，计算机面对上图博弈下棋者总是希望赢棋的，计算机面对上图博弈树的树根所代表的棋盘状态，有树的树根所代表的棋盘状态，有7种可能的下种可能的下法，它当然愿意选择对它最有利，也就是使它法，它当然愿意选择对它最有利，也就是使它获胜的可能性最大的那种下法。获胜的可能性最大的那种下法。n设计一个估值函数设计一个估值函数E(x)，此函数以棋盘状态，此函数以棋盘状态x为为自变量，给出一个函数值，代表此棋盘状态对自变量，给出一个函数值，代表此棋盘状态对计算机有利的程度。一个棋盘状态对计算机越计算机有利的程度。一个棋盘状态对计算机越有利，其有利，其E(x)值越高。计算机获胜的终局棋盘值越高。计算机获胜的终局棋盘状态状态E(x)取最高值。取最高值。 挂肃栈栖弦沁廷呀捶溉住戍崩械恫竿剁爵膨棋同簧斡履碟静脊苑溢少铝沦第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 估值函数估值函数 n估值函数的好坏是下棋程序是否成功的一个关键。估值函数的好坏是下棋程序是否成功的一个关键。n对于对于tic-tac-toe游戏我们可以确定这样的估值函数：游戏我们可以确定这样的估值函数：n其其中中RCDC表表示示计计算算机机还还有有可可能能占占据据的的行行、列列、对对角角线线数数之之和和，RCDO表表示示对对方方还还有有可可能能占占据据的的行行、列列、对角线之和。对角线之和。辑凝甥畏释蓑潭废疑车肖吊熏瓣果号梳篡蓖捅翻酿皮泡飘亭悍虾字笛筑般第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 带有估值得博弈树带有估值得博弈树讣袱粗屡缩贬沤届敲供苟瓷语缮降共挫珊严劈死矫藩袜焕载硒谬逢岛栅餐第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 博弈树博弈树的一般形式的一般形式n在一个假想的二人游戏上（不局限于在一个假想的二人游戏上（不局限于tic-tac-toe游戏）进行。假设游戏）进行。假设该假想游戏的一棵深度为该假想游戏的一棵深度为4的博弈树如下：的博弈树如下：署棋圣知迅吏隅闺雏二惠敛嫁肠竞陛或塘泞暗绢涡淖成屏伏应罚滥愧嘱驼第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n其中方形结点表示计算机面对的棋盘状态；圆形结点其中方形结点表示计算机面对的棋盘状态；圆形结点表示对方面对的棋盘状态；树叶结点中标出的是结点表示对方面对的棋盘状态；树叶结点中标出的是结点的的E(x)值值 n在在此此博博弈弈树树中中，棋棋盘盘状状态态x对对计计算算机机有有利利的的程程度度V(x)这这样样估估算算：设设分分支支结结点点x在在博博弈弈树树中中有有d个个子子结结点点c1，c2，cd，则，则V(x)定义为定义为歌龋斌酣狰赏喻舒七摹厂味肃寨叁禾渤昏支苦唱柄零敌踢录挎庐澳矫知满第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n定义定义V(x)的理由很简单的理由很简单n如果游戏进行到方形结点代表的棋盘状态，则轮到如果游戏进行到方形结点代表的棋盘状态，则轮到计算机选择下一步的走法，因为计算机想获胜，它计算机选择下一步的走法，因为计算机想获胜，它当然从所有可能的下一步状态中选择对于它最有利当然从所有可能的下一步状态中选择对于它最有利的状态，也就是的状态，也就是V(ci)最大的状态最大的状态n如果游戏进行到圆形结点代表的状态，则轮到对方如果游戏进行到圆形结点代表的状态，则轮到对方选择下一步的走法，因为对方想获胜，它当然从所选择下一步的走法，因为对方想获胜，它当然从所有可能的下一个状态中选择对计算机最不利的状态，有可能的下一个状态中选择对计算机最不利的状态，也就是也就是V(ci)最小的状态。最小的状态。 n上图分支结点中给出的值就是用最大最小过程上图分支结点中给出的值就是用最大最小过程确定的确定的 拾泪撒挝伙轧表宵湃六劈怖童呜廷烃骚还妓屿育爸淹巢锹延室泪揣痔侗秃第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page V(x)的计算的计算n下棋程序的关键部分是计算下棋程序的关键部分是计算V(x)值为了写出计算值为了写出计算V(x)的的简单的递归程序，我们将简单的递归程序，我们将V(x)的定义改写成如下形式的定义改写成如下形式 n与公式与公式(12.10)对照可知：对于方形结点对照可知：对于方形结点nV(x)=V(x)对于圆形结点对于圆形结点nV(x)=-V(x)戴军庞施妮痹窒母仓澳凡将守斗蒙射规脉船圣绥阿抿藤其控睹橱枪践可签第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 博弈树算法博弈树算法n计计算算V(x)值值和和确确定定下下一一步步走走法法的的算算法法intValueOf(node*x,intplayer,intdepth,node*best)，其其中中node是是代代表表棋棋盘盘状状态态的的博博弈弈树树结结点点的的类类型型，例例如如，tic-tac-toe游游戏戏的的棋棋盘盘状状态态可可以以用用包包括括9个个元元素素的的数数组组来来表表示示，每每个个元元素素对对应应一一个个方方格格，可可取取值值1、-1、0，表表示示对对应应的的方方格格由由计计算算机机占占据、对方占据、或尚未被占。据、对方占据、或尚未被占。n算法的输入参数算法的输入参数x是当前出发点的棋盘状态；是当前出发点的棋盘状态；player指出该谁走下一步棋；指出该谁走下一步棋；depth指出希望产生深度为多少的指出希望产生深度为多少的博弈树。函数返回博弈树。函数返回V(x)的值，的值，best指针指向应该选择的下指针指向应该选择的下一个棋盘状态。一个棋盘状态。n由于算法太复杂这里就不列出请参考教科书由于算法太复杂这里就不列出请参考教科书翱挤辟爹扎松肪申釉书饱膨捎捡袖矢恩爱莆汽翘实诉秃捎差晤产纤切换荡第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 剪裁剪裁 n在在上上述述算算法法中中，实实际际上上用用的的是是穷穷举举法法的的思思想想。由由于于是是33的的棋棋盘盘，因因此此每每次次放放棋棋子子之之前前，平平均均有有5个个空空格格位位置置可可以以下下棋棋，如如果果博博弈弈树树深深度度为为4，则则需需要要搜搜索索625（5的的4次次方方）个个位位置置。可可以以看看出出，需需要要搜搜索索的的位位置置数数是是呈呈指指数数级级增增长长的的。这这将将导导致致构构造造整整棵棵博博弈弈树树的的计计算算量量大大得得令令计计算算机无法承受。机无法承受。n事实上并不需要搜索所有的位置才能找到最佳事实上并不需要搜索所有的位置才能找到最佳下棋位置下棋位置采用采用 剪裁的技术剪裁的技术，从而大大减少从而大大减少计算量计算量 簧焊嘉钙奏纷坷伏悉购署每姚精应思酵崭课之歼靴赏剖痕谈柴剖怔扛传镍第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 剪裁（剪裁（prune）n一个最大层结点的一个最大层结点的值定义为该结点的最小可值定义为该结点的最小可能值，如果已经确定一个最小层结点的能值，如果已经确定一个最小层结点的值小值小于或等于其父母结点的值，则可以停止产生这于或等于其父母结点的值，则可以停止产生这个最小层结点的其它子结点。按此规则终止结个最小层结点的其它子结点。按此规则终止结点的产生称作点的产生称作剪裁（剪裁（ prune） 滨滚厉墙波铸笆似螟押绞雇晕际村贝饿板惯绷鼻伏哉料糊尾悍秦书昨拳妨第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 剪裁（剪裁（prune） n一个最小层结点的一个最小层结点的值定义为该结点的值定义为该结点的最大可能值，如果已经确定一个最大层结最大可能值，如果已经确定一个最大层结点的值大于或等于其父母结点的点的值大于或等于其父母结点的值，则值，则可以停止产生这个最大层结点的其余子结可以停止产生这个最大层结点的其余子结点。点。 n剪裁和剪裁和剪裁的规则结合起称作剪裁的规则结合起称作-剪裁。剪裁。叉雪傈额酉郭汉坡差番逐征缴菜尸王革园屠不轩婚踪狡杠谊炸看婿锡凿甸第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n把把-剪剪裁裁用用于于前前面面的的假假想想图图上上，事事实实上上整整个个以以p26为为根根的的子子树树都都不不必必产产生生。这这是是因因为为当当V(p12)确确定定为为3时时，p01的的值值成成为为3，V(p25)小小于于p01的的值值，确确定定p13的的值值小小于于p01的的值，于是进行了值，于是进行了剪裁。剪裁。n需需要要强强调调的的是是：结结点点的的值值和和值值是是动动态态的的，它它们们依依赖赖于当前哪些结点的值已被计算出来了。于当前哪些结点的值已被计算出来了。n要要用用-剪剪裁裁的的技技术术来来改改进进算算法法ValueOf，重重新新叙叙述述-剪剪裁裁的的规规则则如如下下：一一个个结结点点的的B值值是是该该结结点点的的最最小小可可能能值值。对对于于任任何何结结点点x，令令B是是其其父父母母结结点点的的B值值，并并且且令令d=-B，则则当当x的的值值已已经经确确定定了了大大于于或或等等于于d时时；就就可可以停止产生结点以停止产生结点x的其余子结点。的其余子结点。卫蜕酒射西迹票遭催工蝴汁裸绢签京涎斑怎表爱埃下售爪痈毛碾举踪膘颠第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page *算法算法12-8应用应用-剪裁技术的博弈树结点求值剪裁技术的博弈树结点求值*constintMAX=10000;/代表代表+constintMIN=-10000;/代表代表-constintSIZE=3;structnodeintgridSIZESIZE;intValueofb(node*x,intplayer,intdepth,intd,node*best)intvalue,Evalue;intcount;糯工豆洗壬鲍争京叉蜒脯揉暗唤掌未奥轮蹿落亨去城焉后墙舟律钦冰窒坏第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page node*p;node*bes;Evalue=E(x);if(Evalue=MAX)|(Evalue=MIN)|(depth=0)/x是是代代表表终局状态的结点或终局状态的结点或1=0for(inti=0;iSize;i+)/best为空棋盘状态为空棋盘状态for(intj=0;jgridij=0;if(player=1)returnEvalue;/返回返回E(x)elsereturn(-Evalue);/返回返回-E(x)暑簇玛质含阂弥荣掘饱烟鼓鹰子且伍狼扛还滞原憋均眨稚篇炼坎清巳星溢第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page p=generate(x,player,count);/产生下一步所有可能状态产生下一步所有可能状态value=MIN;/准备执行最大最小过程准备执行最大最小过程best=p;for(i=0;(icount)&(valued);i+)val=Valueofb(p,-player,depth-1,-value,bes);if(value-val)value=-val;best=p;p+;疚旦堵极又碘燎苞代券诌急按手圃氏夯敏叙屹邓阁斥伪顽拣香镶耳雏随屏第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 学期总结学期总结n大家辛苦了！大家辛苦了！n天道酬勤天道酬勤n纪律问题纪律问题n行政？旷课行政？旷课1/3以上取消资格以上取消资格n情商情商n参与、合作、沟通参与、合作、沟通n纪律纪律n审稿审稿n最迟最迟1月月2号考试时带过来号考试时带过来nThanks and Good Luck!篇判煮随淋救面践荆齐福票肮互汝铸丫发垃橙栓哆城尚谴硕逮杂怕勉禽缔第十二章高级树结构第十二章高级树结构北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page