《高级树结构》ppt课件

《《高级树结构》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、ctspace)分解BST是一种组织上基于对象空间(objectspace)分解的数据结构空间分解是存储在树中的对象（关键码值）决定最简单的方法就是对对象（这里是关键码）的范围进行划分平均划分按照某种方式不平均划分北京大学信息学院版权所有，转载或翻印必究Page假设划分因子为2每次仅把当前范围分为两部分（对应于二叉树）在进行插入的时候，只要是小于结点的关键码的都在左子树中只要是大于结点的关键码的都在右子树中北京大学信息学院版权所有，转载或翻印必究Page关键码空间（keyspace）分解不依赖于关键码的插入顺序树的深度受到关键码精度的影响最坏的情况下，深度等于存储

3、关键码所需要的位数例如，如果关键码是0到255之间的整数，那么关键码的精度就是8个二进制位。如果有两个关键码：10000010和10000011，它们的前面7位都是相同的所以直到第8次划分才能将这两个关键码分开这样的搜索树深度也为8，但这是最坏的情况北京大学信息学院版权所有，转载或翻印必究Page基于关键码范围的分解保证平衡吗？显然是不行的如果关键码的分布得很不均衡，将导致树的结构失衡一种极端的情况，导致所有的关键码都小于根结点，那么以该结点为根的子树的右子树将没有任何的元素北京大学信息学院版权所有，转载或翻印必究PageTrie结构基于关键码分解的数据结构，叫作

4、Trie结构“trie”这个词来源于“retrieval”主要应用信息检索（informationretrieval）用来存储英文字符串，尤其大规模的英文词典自然语言理解系统中经常用到北京大学信息学院版权所有，转载或翻印必究PageTrie结构的适用情况Trie结构主要基于两个原则有一个固定的关键码集合对于结点的分层标记如果所有的元素都可以使用数字或者字母等来标记，那么就可以考虑使用Trie结构例如，元素可以用0-9的数字来标记在根结点的地方，它分出10个子结点，分别标记0-9然后每个子结点又可以分出10个结点如此下去直到所有的元素都能够被区分开北京大学信息学院版

5、权所有，转载或翻印必究PageTrie结构特点与B+树一样，基于关键码空间分解的树结构，其内部结点仅作为占位符引导检索过程，数据纪录只存储在叶结点中Huffman编码树(Huffmancodingtree)也是一种二叉Trie树北京大学信息学院版权所有，转载或翻印必究PageTrie结构示意图北京大学信息学院版权所有，转载或翻印必究PageTrie结构应用：“字符树”存储字典里面的单词英文的单词是有26个字母组成的（简单起见，我们忽略大小写），英文字符树每一个内部结点都有26个子结点树的高度为最长字符串长度北京大学信息学院版权所有，转载或翻印必究Page英文字符

6、树一棵子树代表具有相同前缀的关键码的集合。例如“an”子树代表具有相同前缀an-的关键码集合{and，ant}北京大学信息学院版权所有，转载或翻印必究Page字符树的改进由于单词可能不等长，所以更好的存储是其内部结点不存储单词信息，只有叶结点才存储单词信息北京大学信息学院版权所有，转载或翻印必究Page字符树的改进（续）观察上图中的bad和bee两个单词，它们的父结点都只有一个儿子就是它们自己，也就是说，实际上它们在父结点的时候就已经被区分开了因为我们真正想做的是要检索每一个单词，不需要在已经能够区分每个单词的情况下继续进行分裂结点的动作北京大学信息学院版权所有

7、，转载或翻印必究Page字符树的改进（续）北京大学信息学院版权所有，转载或翻印必究Page字符树中的检索首先用待查关键码的第一个字符与树林的各个根的字符相比较然后下一步的检索在前次比较相等的那棵树上进行其中，用待查关键码的第二个字符与选定的这棵树的根的各个子结点进行比较，接着再沿着前次比较相等的分支进行进一步的检索...直到进行到某一层，该层所有结点的字符都与待查关键码相应位置的字符不同，这说明此关键码在树目录里没有出现；若检索一直进行到树叶，那么就在树目录里找到了给定的关键码北京大学信息学院版权所有，转载或翻印必究PageTrie字符树的缺陷T