《高级树结构》.ppt

单击此处编辑母版标题样式单击此处编辑母版副标题样式.1第十二章 高级树结构 n任课教员：张 铭nhttp:/ 12.1 Trie和Patricia 结构n 12.2 改进的BSTn 最佳二叉搜索树n AVL树n 伸展树n 12.3 空间树结构n 12.4 决策树和博弈树12.1Trie结构和Patricia树nBST（二叉搜索树）不是一棵平衡的树，它的树结构与输入数据的顺序有很大的关系 对象空间(objectspace)分解nBST是一种组织上基于对象空间(objectspace)分解的数据结构n空间分解是存储在树中的对象（关键码值）决定n最简单的方法就是对对象（这里是关键码）的范围进行划分n平均划分n按照某种方式不平均划分 n假设划分因子为2n每次仅把当前范围分为两部分（对应于二叉树）n在进行插入的时候，只要是小于结点的关键码的都在左子树中n只要是大于结点的关键码的都在右子树中 关键码空间（keyspace）分解 n不依赖于关键码的插入顺序n树的深度受到关键码精度的影响n最坏的情况下，深度等于存储关键码所需要的位数 n例如，如果关键码是0到255之间的整数，那么关键码的精度就是8个二进制位。

n如果有两个关键码：10000010和10000011，它们的前面7位都是相同的n所以直到第8次划分才能将这两个关键码分开n这样的搜索树深度也为8，但这是最坏的情况 n基于关键码范围的分解n保证平衡吗？n显然是不行的n如果关键码的分布得很不均衡，将导致树的结构失衡 n一种极端的情况，导致所有的关键码都小于根结点，那么以该结点为根的子树的右子树将没有任何的元素 Trie结构 n基于关键码分解的数据结构，叫作Trie结构 n“trie”这个词来源于“retrieval”n主要应用n信息检索（informationretrieval） n用来存储英文字符串，尤其大规模的英文词典n自然语言理解系统中经常用到 Trie结构的适用情况nTrie结构主要基于两个原则n有一个固定的关键码集合 n对于结点的分层标记 n如果所有的元素都可以使用数字或者字母等来标记，那么就可以考虑使用Trie结构 n例如，元素可以用0-9的数字来标记n在根结点的地方，它分出10个子结点，分别标记0-9n然后每个子结点又可以分出10个结点n如此下去直到所有的元素都能够被区分开Trie结构特点n与B+树一样，基于关键码空间分解的树结构，其内部结点仅作为占位符引导检索过程，数据纪录只存储在叶结点中 nHuffman编码树(Huffmancodingtree)也是一种二叉Trie树 Trie结构示意图Trie结构 应用：“字符树” n存储字典里面的单词n英文的单词是有26个字母组成的（简单起见，我们忽略大小写），n英文字符树每一个内部结点都有26个子结点n树的高度为最长字符串长度英文字符树 n一棵子树代表具有相同前缀的关键码的集合。

例如“an”子树代表具有相同前缀an-的关键码集合and，ant 字符树的改进 n由于单词可能不等长 ，所以更好的存储是其内部结点不存储单词信息，只有叶结点才存储单词信息 字符树的改进（续）n观察上图中的bad和bee两个单词，它们的父结点都只有一个儿子就是它们自己，也就是说，实际上它们在父结点的时候就已经被区分开了n因为我们真正想做的是要检索每一个单词，不需要在已经能够区分每个单词的情况下继续进行分裂结点的动作 字符树的改进（续）字符树中的检索 n首先用待查关键码的第一个字符与树林的各个根的字符相比较 n然后下一步的检索在前次比较相等的那棵树上进行其中，用待查关键码的第二个字符与选定的这棵树的根的各个子结点进行比较，n接着再沿着前次比较相等的分支进行进一步的检索n. n直到进行到某一层，该层所有结点的字符都与待查关键码相应位置的字符不同，这说明此关键码在树目录里没有出现；n若检索一直进行到树叶，那么就在树目录里找到了给定的关键码Trie字符树的缺陷nTrie结构显然也不是平衡的n在它存取英文单词的时候，显然t子树下的分支比z子树下的分支多很多（以t开头的单词比以z开头的单词多很多） n而且，每次有26个分支因子使得树的结构过于庞大，给检索也带来了不便 n字母在计算机中是以二进制ASCII码的形式存储的n使用每个字母的二进制编码来代表这个字母n关键码就只有编码0和1n而不是a到z的26个字母n二叉Trie树 Trie树的插入nTrie树的插入 n首先根据插入纪录的关键码找到需要插入的结点位置 n如果该结点是叶结点，那么就将为其分裂出两个子结点，分别存储这个纪录和以前的那个纪录 n如果是内部结点，则在那个分支上应该是空的，所以直接为该分支建立一个新的叶结点即可 Trie树的删除nTrie树的删除n根据插入纪录的关键码找到需要删除的结点位置 n如果一个被删除结点的父结点没有其他的儿子，那么就需要合并 n否则只需要将此分支设置为空即可 PATRICIA 结构n为了得到更加平衡的结构，D.Morrision发明了Trie结构的一种变体PATRICIA n“PracticalAlgorithmToRetrieveInformationCodedInAlphanumeric”n它不是对整个关键码大小范围的划分n而是根据关键码每一个二进制位的编码来划分n因为每一位要么是0，要么是1，所以分支因子是2，n生成的树是二叉树 PATRICIA 结构图PATRICIA 结构图（续）n上图因为最大的数是63，用6位二进制表示即可n每一个结点都有一个标号，表示它是在比较第几位，然后根据那一位是0还是1来划分左右两个子树n标号为2的结点的右子树一定是编码形式为xx1xxx （x表示该位或0或1，标号为2说明比较第2位）n在图中检索5的话，5的编码为000101 n首先我们比较第0位，从而进入左子树n然后在第1位仍然是0，还是进入左子树n在第2位还是0，仍进入左子树n第3位变成了1，从而进入右子树，就找到了位于叶结点的数字5 PATRICIA 结构图改进n观察PATRICIA的图发现有与Trie图类似的情况n在区分2和5、41和45的时候，在第三个二进制位的比较是不能区别它们的 n可以将它省略，得到一棵更为简洁的树 PATRICIA 结构图改进（续）PATRICIA的特点n每个内部结点都代表一个位的比较，必然产生两个子结点n所以它是一个满二叉树n进行一次检索，最多只需要关键码位数次的比较即可 12.2二叉树结构的改进 n平衡的二叉搜索树、伸展树和最佳二叉排序树，它们都是对二叉树的结构或者操作规则做部分的改进以使树保持在一种类似于平衡的状态，从而达到较好的效率 12.2.1最佳二叉搜索树 n根据前面章节的二叉树介绍我们知道对应于关键码集合K:K=xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon,xem,wul,zom的二叉排序树 二叉搜索树的多样性n同一个关键码集合，其关键码插入二叉搜索树的次序不同，就构成不同的二叉搜索树。

n包括n个关键码的集合中，关键码可以有n!种不同的排列法，因此可以构成n!个二叉搜索树(其中有相同的) n可以用检索效率来衡量二叉搜索树 n如果只计算不同的搜索树，则排列2，1，3的顺序插入关键码与按照排列2，3，1的顺序插入所构成的二叉搜索树完全相同 n这种非前序排列的序列，总是可以找到与其相对应的一个合法前序排列n这n!种排列中，只有 n就是说n个结点可以构造 称为Catalan函数 扩充的二叉树n第4章讨论过扩充的二叉树的概念扩充的二叉树是满二叉树，新增加的空树叶(以下称为外部结点)的个数等于原来二叉树的结点(以下称为内部结点)个数加1 n在扩充的二叉搜索树里，关键码值最小的内部结点的左子女(外部结点)代表了值小于该内部结点的可能关键码的集合；关键码值最大的内部结点的右子女(外部结点)代表了值大于该内部结点的可能关键码的集合n除此之外，每个外部结点代表其值处于原来二叉搜索树的两个相邻结点的关键码值之间的可能关键码的集合路径长度n外部路径长度E定义为从扩充的二叉树的根到每个外部结点的路径长度之和n内部路径长度I定义为扩充的二叉树里从根到每个内部结点的路径长度之和 二叉搜索树里检索算法n在二叉搜索树里检索算法十分简单：首先用待查的关键码与二叉搜索树的根结点进行比较，若比较相等，则找到了要检索的关键码；n若比较不等，具待查关键码值小于根结点的关键码值，则下一次与根的左子树的根比较；否则与根的右子树的根比较。

n如此递归地进行下去，直到某一次比较相等，检索成功；或一直比较到树叶都不相等，检索失败 检索一个关键码的比较次数 n在检索过程中，每进行一次比较，就进入下面一层因此，对于成功的检索，比较的次数就是关键码所在的层数加1对于不成功的检索，被检索的关键码属于哪个外部结点代表的可能关键码集合，比较次数就等于此外部结点的层数 n在二叉搜索树里，检索一个关键码的平均比较次数为参数意义n其中1i，是第i个内部结点的层数，是第i个外部结点的层数，npi是检索第i个内部结点所代表的关键码的频率nqi是被检索的关键码属于第i个外部结点代表的可能关键码集合(即处于第i个和第i+1个内部结点之间)的频率pi，qi也叫做结点的权 n 最佳二叉搜索树定义n是检索第i个内部结点所代表的关键码的概率， 是被检索的关键码属于第i个外部结点代表的可能关键码集合的概率n我们把检索中平均比较次数最小，也就是ASL(n)最小的二叉搜索树称作最佳二叉搜索树 什么样的二叉搜索树是最佳的 ？n检索所有结点的概率都相等，即所有结点的权都相等：n因此，要平均比较次数ASL(n)最小，就是要内部路径长度I最小 n在一棵二叉树里，路径长度为0的结点仅有一个，路径长度为1的结点至多有两个，路径长度为2的结点至多有四个，等等。

因此，有n个结点的二叉树其内部路径长度I至少等于序列:0，1，1，2，2，2，2，3，3，3，3，3，3，3，4，4，的前n项和这个和写成:n可以证明： n这种二叉树的特点是只有最下面的两层结点的度数可以小于2，其它结点度数必须等于2在所有结点的权相等的情况下，这样的二叉搜索树是最佳二叉搜索树，对它进行检索的平均比较次数为n这个ASL(n)是O(log2n)量级的最佳二叉搜索树构造举例n首先将集合K里的关键码排序wan，wen，wil，wim，wul，xal，xem，xul，yo，yon，yum，zi，zol，zomn然后用二分法依次检索这些关键码，并把在检索中遇到的在二叉搜索树里还没有的关键码依次插入二叉搜索树中n首先检索序列中的第一个关键码wan，用二分法检索wan的过程中会依次遇到关键码xem，wil，wan，这就是最先插入二叉搜索树的三个关键码最佳二叉搜索树构造举例n然后检索序列中的第二个关键码wen，用二分法检索wen的过程中会依次遇到关键码xem，wil，wan，wen，其中只有 wen是二叉搜索树中还没有的，因此第四个插入到二叉搜索树中的关键码是wenn再检索序列中的第三个关键码wil，如此进行下去，直到所有的关键码都已插入到二叉搜索树中，这样可得到最佳二叉搜索树。

二叉搜索树的效率n反过来，如果关键码按值递增的顺序依次插入到二叉搜索树中，则将得到退化为线性的二叉搜索树平均比较次数为O(n) n按任意的顺序把关键码插入到二叉搜索树中，它的检索效率如何呢？平均比较次数是接近最坏的情况O(n)呢，还是接近最好的情况O(1og2n)?可以证明，对n!种二叉搜索树进行平均，得到的平均检索次数仍是O(1og2n) 检索各结点的概率不相等的情况 n检索各结点的概率不相等的情况，即在具有不等权结点的二叉搜索树里进行检索 n现在的问题是给了一个排好序的关键码集合keyl，key2，keyn，和权的集合p1，p2，pn，q0，q1，qn，要找使得ASL(n)为最小的最佳二叉排序树，也就是要找使得 为最小 ，上式也称为二叉排序树的开销 最佳二叉搜索树的构造方法n最佳二叉搜索树有个特点：它的任何子树都是最佳二叉搜索树n这一事实引导我。