数据结构与算法17558

《数据结构与算法17558》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主要内容数据结构与算法¢12.1Trie和Patricia结构第十二章高级树结构¢12.2改进的BST¢最佳二叉搜索树张铭赵海燕王腾蛟¢AVL树http://db.pku.edu.cn/mzhang/DS/¢伸展树北京大学信息科学与技术学院¢12.3空间树结构“数据结构与算法”教学小组¢12.4决策树和博弈树©版权所有，转载或翻印必究北京大学信息学院©版权所有，转载或翻印必究Page212.1Trie结构和Patricia树对象空间(objectspace)分解¢BST（二叉搜索树）不是一棵平衡的树，它的树结构¢BST是一种组织上基于对象空间与输入数据的顺序

2、有很大的关系(objectspace)分解的数据结构输入顺序为4、5、6、7、8输入顺序为7、5、4、6、8¢空间分解是存储在树中的对象（关键4码值）决定7¢最简单的方法就是对对象（这里是558关键码）的范围进行划分646¢平均划分7¢按照某种方式不平均划分8北京大学信息学院©版权所有，转载或翻印必究Page3北京大学信息学院©版权所有，转载或翻印必究Page4Trie结构Trie结构示意图元素为2、5、9、17、41、45、63¢基于关键码分解的数据结构，叫作Trie结构0(<32)1(>32)¢“trie”这个词来源于“retrieval”¢主要应用0(

3、<16)1(>16)1(>48)0(<48)¢信息检索（informationretrieval）0(<8)1(>8)1(>40)¢用来存储英文字符串，尤其大规模的1763英文词典0(<4)1(>4)0(<44)1(>44)¢自然语言理解系统中经常用到9254145北京大学信息学院©版权所有，转载或翻印必究Page5北京大学信息学院©版权所有，转载或翻印必究Page61英文字符树字符树的改进（续）存储单词and、ant、bad、bee存储单词an、and、ant、bad、beeababnaedtdeaenandantbadbee*tdbadbee¢一棵子树代

4、表具有相同前缀的关键码的集合。例如“an”子树代表具有相同前缀an-的关键码集合{and，anandantant}北京大学信息学院©版权所有，转载或翻印必究Page7北京大学信息学院©版权所有，转载或翻印必究Page8Trie字符树的缺陷PATRICIA结构¢Trie结构显然也不是平衡的¢为了得到更加平衡的结构，D.Morrision发明了¢在它存取英文单词的时候，显然t子树下的分支比z子树下的分支多很多（以t开头的单词比以z开头的单词多很多）Trie结构的一种变体PATRICIA¢而且，每次有26个分支因子使得树的结构过于庞大，给检索¢“Practical

5、AlgorithmToRetrieveInformation也带来了不便CodedInAlphanumeric”¢字母在计算机中是以二进制ASCII码的形式存储的¢使用每个字母的二进制编码来代表这个字母¢它不是对整个关键码大小范围的划分¢关键码就只有编码0和1¢而是根据关键码每一个二进制位的编码来划分¢而不是a到z的26个字母¢因为每一位要么是0，要么是1，所以分支因子是2，¢二叉Trie树¢生成的树是二叉树北京大学信息学院©版权所有，转载或翻印必究Page9北京大学信息学院©版权所有，转载或翻印必究Page10PATRICIA结构图PATRICIA结构图改

6、进（续）00xxxxx1xxxxx00xxxxx1xxxxx1100xxxx101xxxx10xxxx111xxxx00xxxx01xxxx10xxxx11xxxx22217363000xxx1763000xxx1011xx001xxx101xxx001xxx3331010xx91010xx1011xx0000xx0001xx941450000xx0001xx41452525编码：2：0000105：0001019：001001编码：2：0000105：0001019：00100117：01000141：10100145：10110163：11111117：

7、01000141：10100145：10110163：111111北京大学信息学院©版权所有，转载或翻印必究Page11北京大学信息学院©版权所有，转载或翻印必究Page122PATRICIA的特点12.2二叉树结构的改进¢每个内部结点都代表一个位的比较，必¢最佳二叉排序树然产生两个子结点¢平衡的二叉搜索树¢所以它是满二叉树¢进行一次检索，最多只需要关键码位数¢伸展树次的比较即可北京大学信息学院©版权所有，转载或翻印必究Page13北京大学信息学院©版权所有，转载或翻印必究Page14检索一个关键码的比较次数最佳二叉搜索树的动态规划¢在检索过程中，每进行一次

8、比较，就进入下面¢最佳子结构、重复子结构一层。因此，