《算法与数据结构(c语言)_第7章_高级字典结构》由会员分享，可在线阅读，更多相关《算法与数据结构(c语言)_第7章_高级字典结构（110页珍藏版）》请在金锄头文库上搜索。
1、第七章高级字典结构本章首先论述了字典与索引字典与索引的关系;然后进一步讨论字典的其它实现:以字符为结点的字符树字符树表示;以关键码为结点的二叉排序树二叉排序树（包括静态的最佳二叉排序树最佳二叉排序树和保持动态平衡的二叉排序树平衡的二叉排序树）;多级索引结构（包括静态的多分树多分树和动态的B树、树、B+树树）。本章的内容是第6章关于字典实现的继续；也是关于索引方法的系统讨论；同时还可以看成是第5章关于树型结构的具体应用。目录7.1 字典与索引字典与索引 7.1.1字典的索引字典的索引 7.1.2索引的抽象索引的抽象7.2 字符树字符树 7.2.1双链树表示双链树表示 7.2.2多链表示多链表示7
2、.3 二叉排序树二叉排序树 7.3.1二叉排序树二叉排序树 7.3.2二叉排序树的检索二叉排序树的检索 7.3.3二叉排序树的插入二叉排序树的插入和构造和构造 7.3.4二叉排序树的删除二叉排序树的删除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字典的索引不等长结点的问题
3、在上一章关于字典的讨论中，将所有元素关键码的类型KeyType和值的类型DataType都定义为int类型。但是实际应用时，关键码可以为其它类型，值同样可以出现为多种形式。不同的值需要的空间大小不同，这样的字典就难以采用上一章介绍的顺序存储或者散列存储实现。索引的引入所谓索引索引实际上就是一个从关键码到地址的转换关系。引入索引就可以将包含大量属性信息并且不等长元素的字典的处理，转换成对仅仅包含关键码到地址对应关系（简单类型并且等长的元素）的索引结构的处理。举例在上一章中介绍了字典的顺序表示，如果这个字典中，元素的值需要空间的长度不等，可以另外建立一个字典的索引通常称为目录表目录表。增加了目录表
4、后，图右边的字典可以是顺序存储，也可以用其它方式存储。索引的作用在检索一个元素时，只要在目录表中找到对应的关键码，马上可以得到对应结点的存储位置；而在排序过程中，只要完成目录表中元素（又称索引项索引项）的排序，而不需要移动字典本身的任何结点。7.1.2索引的抽象索引与散列索引与散列一样，都是给出一种从关键码到存储地址的映射方法。不不同同的的是是，散散列列法法的的映映射射是是通通过过函函数数定定义义；而而索索引引法是通过建立辅助的索引表解决。法是通过建立辅助的索引表解决。密集索引与稀疏索引密集索引与稀疏索引前面提到的每个索引项都是对应字典中一个元素，这种索引称为密密集集索索引引；反之，如果每个索
5、引项对应字典中一组元素，这种索引称为稀疏索引稀疏索引。索引索引索引索引是索引项的集合，一个索引项索引项是由一个结点的关键码和该结点的存储位置组成的关联。索引的实质还是字典，而且是元素类型相同的等长结点的字典。所有关于字典的讨论都适合于索引；所有字典的实现也可以用来组织索引。索引的索引对于大型字典，它的索引也很大。所谓索引的索引就是给庞大的（通常是密集的）索引，建立另外一个辅助（通常是稀疏）的索引结构，以达到加快查找字典中特定结点的目的。7.2字符树字符树与树目录 字符树字符树:每个结点表示关键码中的一个字符的树。字符树中从根出发的每个路径上，所对应的字符连接起来，就得到一个字符串。一个字典的所
6、有关键码，可以用一个字符树（林）中从根到其它结点路径对应字符串的集合表示。如果在每个构成关键码的结点中，增加一个指向该关键码对应元素的位置指针，这个字符树（林）就表示了这个字典的一个树目录树目录。举例假设规定某字典中，所有关键码由1至3个字符组成：第一个字符可以是w，x，y，z之一，第二个字符可以是a，e，i，o，u之一，第三个字符可以是l，m，n之一。K=xal，wan，wil，zol，yo，xul，yum，wen，wim，zi，yon，xem，wul，zom使用字符树（林）表示的树目录如图7.2所示。其中所有以*标记的结点为父结点代表的关键码对应的字典元素。在这个字符树林中，它们可以看成是
7、扩充的外部结点。外部结点的个数，就是字典中元素的个数。字符树索引在字符树里检索给定关键码的过程7.2.1双链树表示把字符树（林）转换为对应的二叉树并用llink-link法进行存储，通常称作双链树双链树。例如，图7.2的字符树林转换成的双链树如图7.3所示，其中用*作为标记的结点的左指针给出对应元素的位置。双链树表示7.2.2多链表示如果将字符树（林）中所有字符的信息全部隐藏起来，使用代表各种字符出现的指针指向不同的子字符树，整个字符树（林）变换成一颗以指针数组为结点的树通常称为多链表示多链表示又叫trie结构结构。图7.4是从图7.2的字符树林转换成的trie结构。图中用*标记的箭头指向对应
8、字典元素的位置。多链表示多链表示7.3二叉排序树7.3.1概念及存储二叉排序树二叉排序树也称为二叉搜索树二叉搜索树，它是以关键码为结点的二叉树关键码为结点的二叉树，并且具有以下性质如果任一结点的左子树非空，则左子树中的所有结点的关键码都小于根结点的关键码；如果任一结点的右子树非空，则右子树中的所有结点的关键码都大于根结点的关键码。二二叉叉排排序序树树可可以以表表示示一一个个字字典典的的索索引引，只只要要在在它它的的结结点中增加一个与关键码对应的字典元素的指针；点中增加一个与关键码对应的字典元素的指针；二二叉叉排排序序树树也也可可以以理理解解为为就就是是字字典典的的一一种种二二叉叉树树表表示示，
9、只只要要在在它它的的结结点点中中增增加加一一个个与与关关键键码码对对应应的的属属性性字字段段（如果所有属性占用等长的不大的空间）。（如果所有属性占用等长的不大的空间）。为为了了重重点点研研究究二二叉叉排排序序树树本本身身的的结结构构，下下面面我我们们忽忽略略了了关关键键码码以以外外的的属属性性或或者者指指针针；在在讨讨论论中中也也不不再再区区分分是是字字典典的的二二叉叉排排序序树树索索引引还还是是字字典典的的二二叉叉排排序序树树表表示示，一概以二叉排序树以代之。一概以二叉排序树以代之。存储结构二叉排序树通常采用一般二叉树的llink-rlink法表示，其存储结构定义如下structBinSea
10、rchNode;typedefstructBinSearchNode*PBinSearchNode;structBinSearchNodeKeyTypekey;/*结点的关键码字段*/PBinSearchNodellink,rlink;/*二叉树的左、右指针*/;typedefstructBinSearchNode*BinSearchTree/*二叉排序树*/typedefBinSearchTree*PBinSearchTree;7.2.2二叉排序树的检索在下面给出的检索算法中，设在二叉排序树上查找关键码为key的结点，算法结束时返回检索成功或失败的标志。并且检索成功时，position指向查
11、找到的结点指针；检索失败时，position指向该结点应插入位置的父结点。int search(PBinSearchTree ptree,KeyTypekey,PBinSearchNode*position)7.3.3二叉排序树的插入和构造为了要保证插入后仍满足二叉排序树的定义。插入新结点的方法是 如果二叉排序树为空，则新结点作为根结点。如果二叉排序树非空，则将新结点的关键码与根结点的关键码比较，若相等表示该结点已在二叉排序树中；若小于根结点的关键码，则将新结点插入到根结点的左子树中；否则，插入到右子树中。子树中的插入过程和树中的插入过程相同，如此进行下去，直到找到该结点，或者直到左或右子树为
12、空二叉树，新结点插入成为叶子结点为止。程序实现：int insert(PBinSearchTree ptree,KeyType key)构造算法对于给定字典构造其二叉排序树，可以从一个空二叉排序树开始，将元素（关键码）逐个插入二叉排序树。下面给出二叉排序树的构造算法。假设字典dic按顺序方法存放，算法依次将字典的关键码插入到二叉排序树中。intcreatSearchTree(PBinSearchTreeptree,SeqDictionary*dic)7.3.4二叉排序树的删除为了删除一个二叉树中的结点，必须首先找到这个结点，然后选择下面给出两种方法删除之，以保证删除后仍满足二叉排序树的定义。第
13、一种方法第一种方法 (1)如果被删除结点p没有左子树，则用p的右子女代替p即可。(2)否则，在p的左子树中，找出关键码最大的一个结点r(r处于p的左子树中最右下角的位置，r一定无右子女)，将r的右指针指向p的右子女，用p的左子女代替p结点。第二种方法第二种方法 (1)同第一种方法的(1)。(2)同第一种方法找到r结点，用r结点代替被删除的结点p，p原来的左右子女不变。并且用原来r的左子女代替原来的r结点。二叉排序树的删除算法intdelete(PBinSearchTreeptree,KeyTypekey)在二叉排序树中删除关键码为key的结点。算法首先要找到被删除的结点，但是并没有调用算法7.
14、1。原因是在算法7.1中，检索成功时只提供了该结点的位置，但不知道其父结点的位置，难以完成该结点的删除。7.4最佳二叉排序树7.4.1基本概念对于同一关键码集合，由于结点插入的先后次序不同，所构成的二叉排序树的形态和高度是不同的。n个结点按不同的次序插入到二叉排序树中，可能得到n!棵二叉排序树(其中有的形态相同)，如何评价这些二叉排序树，什么形状的二叉排序树执行检索的效率最好?由同一组关键码构成的两棵形态不同的二叉排序树为了讨论二叉排序树的检索效率，首先引入“扩充二叉排序树”，在扩充二叉排序树中定义“平均比较次数”的概念，然后用平均比较次数讨论什么是一棵“最佳二叉排序树”。扩充的二叉排序树扩充
15、的二叉排序树把扩充二叉树的概念推广到二叉排序树就得到扩充的二叉排序树扩充的二叉排序树。外部结点代表（按对称序）位与其相邻的两个内部结点关键码之间的所有不属于当前字典的关键码集合。最佳二叉排序树最佳二叉排序树在扩充二叉排序树里，检索一个关键码的平均比较次数平均比较次数为：检索中平均比较次数最小，即E(n)最小的二叉排序树称作最佳二叉排序树最佳二叉排序树。7.4.2等概率的检索假设字典元素的关键码满足：key1key2key3key4keyn检索所有结点的概率都相等，即所有结点的权相等，亦即：设IPL为二叉排序树的内部路径长度，EPL为外部路径长度，5.1节中给出了IPL和EPL之间的关系为EPL
16、=IPL+2n。这时因此，若内部路径长度IPL最小，则平均比较次数E(n)最小。要使得E(n)最小，则二叉树需满足除最下层的叶结点度数均为0外，只有倒数第二层结点的度数可以小于2，其它结点度数必须等于2。这样的二叉排序树检索的平均比较次数为：这个E(n)是O(log2n)量级的。最佳二叉排序树的构造 (1)先将字典元素关键码排序。(2)对每个关键码按二分法在排序关键码序列中执行检索，将检索中遇到的还未在二叉排序树中的关键码插入二叉排序树中。举例对于K=27,73,10,5,18,41,99,51,25，构造最佳二叉排序树的过程如下：首先将它们排序为：5，10，18，25，27，41，51，73，99，然后从空二叉树出发，在排序的关键码序列中用二分法检索5，检索中遇到的结点为27,10,5，将这三个结点插入二叉排序树。再检索第二个结点10，遇到的结点为27,10，二叉排序树中已经有这两个结点。再检索第三个结点18，。得到的插入次序为27，10，5，18，25，51，41，73，99，相应的最佳二叉排序树如图7.10所示。7.4.3不等概率的检索给定排序的关键码集合key1,keyn，和权
