彩色PDF讲义(12)

《彩色PDF讲义(12)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构与算法第十二章高级树结构任课教员：张铭http://db.pku.edu.cn/mzhang/DS/mzhang@db.pku.edu.cn北京大学信息科学与技术学院网络与信息系统研究所©版权所有，转载或翻印必究主要内容¢12.1Trie和Patricia结构¢12.2改进的BST¢最佳二叉搜索树¢AVL树¢伸展树¢12.3空间树结构¢12.4决策树和博弈树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page212.1Trie结构和Patricia树¢引子：BST（二叉搜索树）不是平衡的树¢树结构与输入数据的顺序有很大的关系475586467输入顺

2、序:7、5、4、6、88输入顺序:4、5、6、7、8北京大学信息学院张铭编写©版权所有，转载或翻印必究Page3Trie结构¢关键码对象空间分解¢“trie”这个词来源于“retrieval”¢主要应用¢信息检索（informationretrieval）¢自然语言大规模的英文词典¢二叉Trie树¢用每个字母的二进制编码来代表¢编码只有0和1北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4二叉Trie结构元素为2、5、9、17、41、45、630(<32)1(>32)0(<16)1(>16)1(>48)0(<48)0(<8)1(>8)171(>40)

3、630(<4)1(>4)0(<44)1(>44)9254145北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5英文字符树——26叉Trie存单词and、ant、bad、bee“an”子树代表具有相同前缀an-的关ab键码集合{and，ant}naedtdeandantbadbee¢一棵子树代表具有相同前缀的关键码的集合北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6字符树的改进（续）存储单词an、and、ant、bad、beeabaen*tdbadbeeanandant北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7Trie字

4、符树的特点¢Trie结构也不是平衡的¢t子树下的分支比z子树下的多¢26个分支因子——庞大的26叉树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8PATRICIA结构¢“PracticalAlgorithmToRetrieveInformationCodedInAlphanumeric”¢D.Morrision发明的Trie结构变体¢根据关键码二进制位的编码来划分¢二叉Trie树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page9PATRICIA结构图00xxxxx1xxxxx1100xxxx01xxxx10xxxx11xxxx22000x

5、xx1763001xxx101xxx3391010xx1011xx0000xx0001xx414525编码：2：0000105：0001019：00100117：01000141：10100145：10110163：111111北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10压缩PATRICIA结构00xxxxx1xxxxx1100xxxx01xxxx10xxxx11xxxx217363000xxx1011xx001xxx31010xx0000xx0001xx9414525编码：2：0000105：0001019：00100117：01000141

6、：10100145：10110163：111111北京大学信息学院张铭编写©版权所有，转载或翻印必究Page11PATRICIA的特点¢改进后的压缩PATRICIA树是满二叉树¢每个内部结点都代表一个位的比较¢必然产生两个子结点¢一次检索不超过关键码的位个数北京大学信息学院张铭编写©版权所有，转载或翻印必究Page12后缀树(SuffixTree)¢后缀树是表示一个字符串S所有后缀串的树¢结点表示开始的字符(或压缩字符串)¢边标注为子串——该字符串在原串中的起止位置¢边表示不同字符分支¢所有根到树叶结点的路径，可以表示串S的所有后缀串¢通俗地说：¢一个字符串的所

7、有后缀¢这些后缀组成Trie¢压缩Trie，得到字符串的后缀树北京大学信息学院张铭编写©版权所有，转载或翻印必究Page13MALAYALAM$的后缀¢MALAYALAM¢ALAYALAM¢LAYALAM¢AYALAM¢YALAM¢ALAM¢LAM¢AM¢M¢$北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14对后缀串排序¢ALAM¢ALAYALAM¢AM¢AYALAM¢LAM¢LAYALAM¢MALAYALAM¢M¢YALAM¢$北京大学信息学院张铭编写©版权所有，转载或翻印必究Page15后缀树S=MALAYALAM$12345678910¢AL

8、AM¢ALAYALAM¢