北大数据结构与算法课件12高级树结构

数据结构与算法第十二章高级树结构信息科学与技术学院网络与信息系统研究所北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2主要内容„12.1Trie和Patricia结构„12.2改进的BST„最佳二叉搜索树„AVL树„伸展树„12.3空间树结构„12.4决策树和博弈树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page312.1Trie结构和Patricia树„引子：BST（二叉搜索树）不是平衡的树„树结构与输入数据的顺序有很大的关系4567875846输入顺序:4、5、6、7、8输入顺序:7、5、4、6、8北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4Trie结构„关键码对象空间分解„“trie”这个词来源于“retrieval”„主要应用„信息检索（informationretrieval）„自然语言大规模的英文词典„二叉Trie树„用每个字母的二进制编码来代表„编码只有0和1北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5二叉Trie结构元素为2、5、9、17、41、45、630(32)1(32)0(16)1(16)0(8)0(4)1(48)1(8)1(4)2591741631(40)450(44)1(44)0(48)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6英文字符树——26叉Trie„一棵子树代表具有相同前缀的关键码的集合存单词and、ant、bad、beeandtbadeeandantbadbee“an”子树代表具有相同前缀an-的关键码集合{and，ant}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7字符树的改进（续）存储单词an、and、ant、bad、beeandtbaeandantbadbeean*北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8Trie字符树的特点„Trie结构也不是平衡的„t子树下的分支比z子树下的多„26个分支因子——庞大的26叉树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page9PATRICIA结构„“PracticalAlgorithmToRetrieveInformationCodedInAlphanumeric”„D.Morrision发明的Trie结构变体„根据关键码二进制位的编码来划分„二叉Trie树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10PATRICIA结构图101xxx10xxxx0000xx001xxx0001xx编码：2：0000105：0001019：00100117：01000141：10100145：10110163：1111110112230xxxxx1xxxxx00xxxx01xxxx11xxxx000xxx25917416331010xx1011xx45北京大学信息学院张铭编写©版权所有，转载或翻印必究Page11压缩PATRICIA结构1710xxxx01xxxx001xxx0001xx0000xx编码：2：0000105：0001019：00100117：01000141：10100145：10110163：1111110112330xxxxx1xxxxx00xxxx11xxxx2594163451011xx1010xx000xxx北京大学信息学院张铭编写©版权所有，转载或翻印必究Page12PATRICIA的特点„改进后的压缩PATRICIA树是满二叉树„每个内部结点都代表一个位的比较„必然产生两个子结点„一次检索不超过关键码的位个数北京大学信息学院张铭编写©版权所有，转载或翻印必究Page13后缀树(SuffixTree)„后缀树是表示一个字符串S所有后缀串的树„结点表示开始的字符(或压缩字符串)„边标注为子串——该字符串在原串中的起止位置„边表示不同字符分支„所有根到树叶结点的路径，可以表示串S的所有后缀串„通俗地说：„一个字符串的所有后缀„这些后缀组成Trie„压缩Trie，得到字符串的后缀树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14MALAYALAM$的后缀„MALAYALAM„ALAYALAM„LAYALAM„AYALAM„YALAM„ALAM„LAM„AM„M„$北京大学信息学院张铭编写©版权所有，转载或翻印必究Page15对后缀串排序„ALAM„ALAYALAM„AM„AYALAM„LAM„LAYALAM„MALAYALAM„M„YALAM„$北京大学信息学院张铭编写©版权所有，转载或翻印必究Page16S=MALAYALAM$12345678910$YALAM$M$ALAYALAM$$MYALAM$$MYALAM$$MYALAM$AALLA62847319510后缀树„ALAM„ALAYALAM„AM„AYALAM„LAM„LAYALAM„MALAYALAM„M„YALAM„$北京大学信息学院张铭编写©版权所有，转载或翻印必究Page17(10,10)(5,10)(1,1)(10,10)(2,10)(3,4)(5,10)(9,10)(2,2)(5,10)(9,10)(3,4)(9,10)(5,10)62847319510边信息S=MALAYALAM$12345678910北京大学信息学院张铭编写©版权所有，转载或翻印必究Page18建树算法„对于长度为n的语料建立后缀树，直接的方法时间复杂度为O（n*n）„1973年Weiner提出线性时间算法„1976年McCreigh提出更节约内存的算法„1995年Ukkonen提出线性时间建树算法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page19z对于长度为n的字符串建立后缀树，直接的方法时间复杂度为O（n*n）z1973年Weiner提出线性时间算法z1976年McCreigh提出更节约内存的算法z1995年Ukkonen提出线性时间建树算法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page20GST——通用后缀树(Generalized)$ONDWI$OGD$OGIOW$$OGND$OGIOW$$OGIOW$$W$INDOW$$(2,3)(1,4)(2,5)(2,4)(2,1)(1,2)(2,2)(1,3)(1,5)(2,6)(1,6)(1,1)(1,7)(2,7)WINDOW$INDIGO$12345671234567北京大学信息学院张铭编写©版权所有，转载或翻印必究Page21单词粒度的后缀树z“Iknowyouknow$”北京大学信息学院张铭编写©版权所有，转载或翻印必究Page22后缀树的应用„查找字符串中的子串„统计S中出现T的次数„找出S中昀长的重复子串„出现了两次以上的子串„两个字符串的公共子串„昀长共同前缀(LCP)„回文串北京大学信息学院张铭编写©版权所有，转载或翻印必究Page23后缀树的应用„中文切词„关联分析„发现经常共同出现的短语„频繁模式挖掘„STC聚类„基因/蛋白序列对比/分类„……北京大学信息学院张铭编写©版权所有，转载或翻印必究Page24后缀数组„字符串S的后缀数组SA„对S的所有后缀的指针排序„即后缀树叶结点的字典序„后缀树ST=后缀数组SA+LCP数组北京大学信息学院张铭编写©版权所有，转载或翻印必究Page25数组(SuffixArray)$10YALAM$5M$9MALAYALAM$1LAYALAM$3LAM$7AYALAM$4AM$8ALAYALAM$2ALAM$6MALAYALAM$1234567891010591374826后缀数组-001020113昀长公共前缀数组后缀6和2共享“ALA”后缀2和8共享“A”LCP总是相邻的北京大学信息学院张铭编写©版权所有，转载或翻印必究Page26代价分析„目标长n=|S|，模式长m=|P|m=|P|))„空间代价„ST20n„SA4n„建数据结构时间代价„STO(n)„SAO(nlogn)„查找子串时间代价„STO(m)•SAO(mlogn)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page27后缀树小结„后缀树和后缀数组提供了很好的全索引结构„适合于各种字符串算法„大量后缀树的变种„尽力减少其空间消耗北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2812.2二叉树结构的改进„昀佳二叉排序树„平衡的二叉搜索树„伸展树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page29B1543FH21543D1101()(11)nniiiiiASLnpqlW==⎡⎤′=++⎢⎥⎣⎦∑∑北京大学信息学院张铭编写©版权所有，转载或翻印必究Page30昀佳二叉搜索树的动态规划„昀佳子结构、重复子结构„任何子树都是昀佳二叉搜索树„动态规划过程„第一步：构造包含1个结点的昀佳二叉搜索树„找t(0，1)，t(1，2)，…，t(n-1，n)„第二步构造包含2个结点的昀佳二叉搜索树„找t(0，2)，t(1，3)，…，t(n-2，n)„再构造包含3，4，…个结点的昀佳二叉搜索树„昀后构造t(0，n)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page31昀佳二叉搜索树t(i，j)„包含关键码keyi+1，keyi+2，…，keyj为内部结点(0≤i≤j≤n)„结点的权为(qi，pi+1，qi+1，…，pj，qj)，„根为r(i，j)„开销为C(i，j)，即„权的总和为W(i，j)=pi+1+…+pj+qi+qi+1+…+qj1(11)jjxxxxxixipql=+=′++∑∑北京大学信息学院张铭编写©版权所有，转载或翻印必究Page32„以keyk为根„左子树包含keyi+1，…，keyk-1„C(i，k-1)„右子树包含keyk+l，keyk+2，…，keyj„C(k，j)已求出„C(i，j)=W(i，j)+(C(i，k-1)+C(k，j))jkimin≤北京大学信息学院张铭编写©版权所有，转载或翻印必究Page33ji0123401234012220223033040r(i,j)ji012340123401028435701227400919060C(i,j)ji01234012345101821284121822393361W(i,j)B第一步花费总权1541010D5431212F43299H32166北京大学信息学院张铭编写©版权所有，转载或翻印必究Page34B15543D53154第二步开销总权30182818D54432F4254327183018DBFDF433213143219132213HFH第三步花费总权B15544D515424F32432BDF4324F13512D54B5224D54443F41434122H21321DFH4022H34541D32F4924第153451北京大学信息学院张铭编写©版权所有，转载或翻印必究Page35第四步花费总权B1543F51546828H2143BDF5728351D543D321H451332DFH154B62284F32154BH7128北京大学信息学院张铭编写©版权所有，转载或翻印必究Page36voidOptimalBST(inta[],intb[],intn,intc[N+1][N+1],intr[N+1][N+1],intw[N+1][N+1]){for(inti=0;i=n;i++)for(intj=0;j=n;j++){//初始化c[i][j]=0;r[i][j]=0;w[i][j]=0;}for(i=0;i=n;i++){w[i][i]=b[i];for(intj=i+1;j=n;j++)//求出权和w[i.j]w[i][j]=w[i][j-1]+a[j]+b[j];}for(intj=1;j=n;j++){//确定一个结点的BestBSTc[j-1][j]=w[j-1][j];r[j-1][j]=j;}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page37intm,k0,k;for(int