张乃孝全套配套课件算法与数据结构 第7章 高级字典结构.ppt

《张乃孝全套配套课件算法与数据结构 第7章 高级字典结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章高级字典结构本章首先论述了字典与索引的关系;然后进一步讨论字典的其它实现:以字符为结点的字符树表示;以关键码为结点的二叉排序树（包括静态的最佳二叉排序树和保持动态平衡的二叉排序树）;多级索引结构（包括静态的多分树和动态的B树、B+树）。本章的内容是第6章关于字典实现的继续；也是关于索引方法的系统讨论；同时还可以看成是第5章关于树型结构的具体应用。目录7.1字典与索引7.1.1字典的索引7.1.2索引的抽象7.2字符树7.2.1双链树表示7.2.2多链表示7.3二叉排序树7.3.1二叉排序树7.3.2二叉排序树的检索7.3.3二叉排序树的插入和构造7.3.4二叉排序树的删除

2、7.4最佳二叉排序树7.4.1基本概念7.4.2等概率的检索7.4.3不等概的情况7.5平衡二叉排序树7.5.1基本概念7.5.2调整平衡的模式7.5.3实现7.6索引文件7.6.1多分树7.6.2B树7.6.3B+树7.1字典与索引7.1.1字典的索引不等长结点的问题在上一章关于字典的讨论中，将所有元素关键码的类型KeyType和值的类型DataType都定义为int类型。但是实际应用时，关键码可以为其它类型，值同样可以出现为多种形式。不同的值需要的空间大小不同，这样的字典就难以采用上一章介绍的顺序存储或者散列存储实现。索引的引入所谓索引实际上就是一个从关键码到地址的转换关系

3、。引入索引就可以将包含大量属性信息并且不等长元素的字典的处理，转换成对仅仅包含关键码到地址对应关系（简单类型并且等长的元素）的索引结构的处理。举例在上一章中介绍了字典的顺序表示，如果这个字典中，元素的值需要空间的长度不等，可以另外建立一个字典的索引——通常称为目录表。增加了目录表后，图右边的字典可以是顺序存储，也可以用其它方式存储。索引的作用在检索一个元素时，只要在目录表中找到对应的关键码，马上可以得到对应结点的存储位置；而在排序过程中，只要完成目录表中元素（又称索引项）的排序，而不需要移动字典本身的任何结点。7.1.2索引的抽象索引与散列索引与散列一样，都是给出一种从关键码到

4、存储地址的映射方法。不同的是，散列法的映射是通过函数定义；而索引法是通过建立辅助的索引表解决。密集索引与稀疏索引前面提到的每个索引项都是对应字典中一个元素，这种索引称为密集索引；反之，如果每个索引项对应字典中一组元素，这种索引称为稀疏索引。索引索引是索引项的集合，一个索引项是由一个结点的关键码和该结点的存储位置组成的关联。索引的实质还是字典，而且是元素类型相同的等长结点的字典。所有关于字典的讨论都适合于索引；所有字典的实现也可以用来组织索引。索引的索引对于大型字典，它的索引也很大。所谓索引的索引就是给庞大的（通常是密集的）索引，建立另外一个辅助（通常是稀疏）的索引结构，以达到加

5、快查找字典中特定结点的目的。7.2字符树字符树与树目录字符树:每个结点表示关键码中的一个字符的树。字符树中从根出发的每个路径上，所对应的字符连接起来，就得到一个字符串。一个字典的所有关键码，可以用一个字符树（林）中从根到其它结点路径对应字符串的集合表示。如果在每个构成关键码的结点中，增加一个指向该关键码对应元素的位置指针，这个字符树（林）就表示了这个字典的一个树目录。举例假设规定某字典中，所有关键码由1至3个字符组成：第一个字符可以是w，x，y，z之一，第二个字符可以是a，e，i，o，u之一，第三个字符可以是l，m，n之一。K={xal，wan，wil，zol，yo，xul，y

6、um，wen，wim，zi，yon，xem，wul，zom}．使用字符树（林）表示的树目录如图7.2所示。其中所有以*标记的结点为父结点代表的关键码对应的字典元素。在这个字符树林中，它们可以看成是扩充的外部结点。外部结点的个数，就是字典中元素的个数。字符树索引在字符树里检索给定关键码的过程7.2.1双链树表示把字符树（林）转换为对应的二叉树并用llink-link法进行存储，通常称作双链树。例如，图7.2的字符树林转换成的双链树如图7.3所示，其中用*作为标记的结点的左指针给出对应元素的位置。双链树表示7.2.2多链表示如果将字符树（林）中所有字符的信息全部隐藏起来，使用代表各

7、种字符出现的指针指向不同的子字符树，整个字符树（林）变换成一颗以指针数组为结点的树——通常称为多链表示又叫trie结构。图7.4是从图7.2的字符树林转换成的trie结构。图中用*标记的箭头指向对应字典元素的位置。多链表示7.3二叉排序树7.3.1概念及存储二叉排序树也称为二叉搜索树，它是以关键码为结点的二叉树，并且具有以下性质∶如果任一结点的左子树非空，则左子树中的所有结点的关键码都小于根结点的关键码；如果任一结点的右子树非空，则右子树中的所有结点的关键码都大于根结点的关键码。二叉排序树可