您的位置毕业设计论文网 , 信息管理系统毕业设计,智轩软件源码网>Android>Android>数据结构学习(C++)续——查找(搜索)【2】>

数据结构学习(C++)续——查找(搜索)【2】

发布时间:2009-4-4浏览:

核心提示:数据结构学习(C++)续——查找(搜索)【2】

树型查找

折半查找所需要的,有序的、可以随机存取的、顺序结构的限制,导致了排序的额外负担(如果是逐个添加,主要的负担是移动数据,此时是折半插入排序)。通过观察折半查找的过程,发现实际上mid是从判定树的根走到了叶子节点,而这棵判定树和有相同节点的完全二叉树的高度是相同的。链式结构的好处就是不用大量移动数据,自然的用链树来做查找结构应该是个好选择。

在前面我们曾经写过一个BSTree类,这个类大致上能满足我们的要求。而为了在不同的输入情况下,使得树的高度尽可能的小,平衡树的概念被提出来了,例如前面的AVLTree类。所谓的平衡,现在更多意义上是指和完全m叉树高度的比值是小于某个常数的树,也就是高度≤klogmn的树,k为一个定常数。注意到AVL树的定义实际上太苛刻,就很容易理解为什么要放宽要求。而实际能应用的平衡树,都是为了满足这个要求而自己定一套规则,比如B-树,这个后面会讲到。

索引

有些字典会提供一个目录,大部分情况是这样的A……xx;B……xx;……。这样就能迅速翻到开头字母对应的页数(实际上也知道了开头字母结束的地方),并且每个页的左右上角的单词也说明了本页的单词范围(可以判断所查单词在不在此页)。这些就是索引。

使用索引能够快速的定位查找范围,从我们查字典的经验看来,这也应该是能提高查找效率的方法。注意到目录的作用,它使得我们所需的字典空间分布,在一页(或者几页)的空间上迅速的被我们得到——类比来看,如果数据太多以至内存装不下,我们也可以弄个“目录”,使得可以将数据分块的读入内存查找。

B-树

当数据膨胀到一个可怕的程度时,连索引都不能被全部装入内存——见过印刷版的EI检索都有这个感觉,光一个检索目录都比我们用的字典厚。我们的办法就是索引再索引,显而易见的,每个索引块都应该尽可能的大,以帮助我们获得尽可能多的信息,而避免再次的查索引(此时一般都会涉及外存的存取)。AVL树此时便力不从心了,我们需要一种新的结构。

相信每个学到这里的人都对B-树的定义深恶痛绝,这个的责任应该由写书的人来负,虽然定义、概念是人认知的重要工具和途径,但在这里是适得其反的。原因就是B-树根本不存在概念意义上的“概念”,它只是一个描述型的“概念”,是B-树能够运行从而表现出来的一种现象。不管怎么说,先看一下现有的书上的定义(省略了“或者为空树”这句话):

严蔚敏、吴伟民《数据结构(C语言版)》

1.         每个节点至多有m棵子树

2.         若根不是叶子节点,至少有两棵子树

3.         除根以外的所有非终端节点至少有ém/2ù棵子树

4.         所有非终端节点包含下列信息数据(n,A0,K1,A1,K2,A2……,Kn,An),其中,Ki为关键字,且Ki<Ki+1(i=1,2,……,n-1);Ai(i=0,……,n)为指向子树根节点的指针,且指针Ai-1所指子树中所有节点的关键字均小于Ki(i=1,……,n),An所指子树中所有的节点的关键字均大于Kn,n(ém/2ù-1£ n £ m-1)为关键字的个数(或n+1为子树个数)。

5.         所有的叶子节点都出现在同一层次上,并不带信息(可以看作是外部节点或查找失败的节点,实际上这些节点不存在,指向这些节点的指针为空)。

殷人昆等《数据结构(用面向对象方法与C++描述)》

1.         m路搜索树(实际上是上面第1、4条的内容)

2.         根节点至少有两个子女

3.         除根节点以外的所有节点(不包括失败节点)至少有ém/2ù个子女

4.         所有的失败节点都位于同一层。事实上,这些节点都是作为外部节点存在,不是树上的节点。

非常莫名其妙的定义——凭什么根至少有两个子女,而其他的至少ém/2ù个子女?跟AVL树的定义比较一下就能看出这个定义的不合理处——AVL树只是给出了平衡的定义“左右子树高度差不超过1”,至于什么平衡因子、旋转,根本就没有提及,那只是为了保证平衡的手段。显然,现在的B-树的定义,把为了保证平衡而采取措施的结果包括在定义之中了,而这必将导致人的认知上的迷惑,因此这样的定义是不合格的。或许,一个不和现在定义矛盾的合理的定义应该是这样:采用如下办法达到“平衡”的m路搜索树……,当然,我们首先要解决什么叫“平衡”,而这个直觉上的定义前面已经提到了。

接下来,让我们看看保持平衡的“如下办法”是什么。回忆一下AVL树,那时的旋转确实是很精妙的方法——保持中序有序的情况下改变子树高度差,我也耗费了不少脑细胞把AVL树的讲解从书上的莫名其妙变成了按部就班,这是本人到目前为止最为得意的一件事情,到大家能看到这篇文字的时候,应该也能看见我写的AVL树的讲解了。

两个叉的AVL树能旋转,m个叉的树怎么转?看来得换个思路,前人已经为我们做到了,就是节点的分裂和合并。

Ø         分裂

节点装不下的时候就分裂,也就是说对于一个节点,当第m个元素进来的时候,就要分裂。怎么分裂?以中间元素为轴,左右两部分各形成一个节点,作为中间元素的左右孩子——这里还是借用了二叉树的概念,而事实上,m叉搜索树就是多个二叉搜索树拼合的产物——这样还是中序有序的(或许不该说“中序”,大家结合二叉树自己理解吧),中间元素带着这两个孩子插入到原来节点的父节点,当然,父节点满的时候同样要分裂,这样一层层直到根节点(或者不用分裂)。

纵观分裂的过程,我们才能明白前面的定义是怎么回事。如果采用如上的分裂方法,对于根节点来说,要么没有子女,要么一分裂就两个子女。而对于非根节点,只有当节点满的时候才会分裂,那自然最少有ém/2ù个子女。

而“所有的失败节点都位于同一层”是B-树的“平衡准则”,很容易就能看出这样的树是“平衡”的。

所以,关于B-树的定义实际上是B-树维持平衡的外在表现,它不应该作为B-树的定义,而只能是一种描述。

Ø         合并

和二叉搜索树一样,删除都归结成在叶子节点的删除,如果不在叶子节点,就拿叶子节点中的覆盖掉,转化成在叶子节点的删除。同样的,当不平衡出现时(即不满足上面B-树的描述),需要平衡化。

我们看到,父节点中的元素和左右两个孩子原来可能是一个节点的,或者可以说他们可以合并成一个节点。这样一来,如果他们的元素总和大于m-1,那么就从多的向少的拨一个元素——想想电视里老和尚手里的念珠,元素的移动过程是这样的:元素多的节点——父节点(手里的珠子)——元素少的节点。如果他们的元素总和小于等于m-1,那么就把他们合并成一个节点,这样一来,父节点就会少一个元素,如果也出现了不平衡,也同样处理。

观看分裂合并的过程,就会发现插入删除的起点都在叶子节点,出现不平衡后,无论分裂还是合并,都会把多了(或者少了)一个元素的变化传递到父节点,从而导致对父节点的再度平衡化。和AVL树的调整简直是如出一辙,不同的是,AVL树不可能分裂合并,因此采取的是旋转的办法;或者可以说B-树不能旋转,因此采取了分裂合并。而两种调整方法都是在保持有序的情况下,使树高(差)发生了变化。

当树的叉多起来的时候,操作起来都会觉得不便,因此B-树更应该是为了减少内外存交换开销而提出来的,和外排一样,对一般的应用意义不大,不做系统级别的应用(或者是为了考试)很少会用到,就不再具体讲解了。

而如果仅是在内存中,叉的数目少一点会比较好,比如3叉(因为这样的树每个节点有2或3个叉,又叫2-3树),而实际上,AVL树(或者红黑树)已经做得很好了,没必要费心在多叉搜索树上。

B+树

想想人们还真烦,B-树都有人认为是Binary树了,又来一个B+树,看来老外还真是该打,Binary和Balance缩写也不多保留几个字母,都是B。

B+树更是为了外存而提出来的,同样的,一般用途不大,一般人不必费心了(考试的例外)。注意的是和B-树的几点差别:B+树的非叶子节点都是索引,因此当删除关键码的时候,有些情况不必改动索引,查到了关键字也要一直走到叶子节点;另外所有的叶子节点都是链接在一起的,从头到尾可以顺序遍历——和线索二叉树很像不是吗?

严版的和殷版的在B+树的定义(更准确的说是描述)上有一个很大的分歧(节点中几个元素几个子树),从教学的目的上,我同意殷版的描述,因为这样的描述能更直接的表达B+树是如何从B-树演化来的,严版的引入了额外的区分,分散了读者的注意力。

散列(哈希表)

我更觉得哈希表是因为目前的储存结构而诞生的。想想我们的储存器(RAM),每个单元对应一个地址,对于数组来说,当知道首地址后,可以马上计算出第N个元素的地址,因此可以马上读取。反过来说,却不能由内容来确定元素的地址,想知道含某个内容的单元的地址,就必须挨个查看,或者在有序的情况下折半查找。

而当我们的储存器能够支持按内容存取的话,那我们前面介绍的一切查找方法都会变得黯淡无光——想找15,马上就能定位到15的位置,这样O(1)的方法简直是人们梦寐以求的。不知是幸运(前面查找的方法还是大有用武之地)还是不幸(直接的O(1)查找不可能容易的实现),我们想要的那种类型的储存器(相联存储器)贵的要命(也可能容量根本做不大)。

既然硬件不支持,就从软件下手吧,前面费了点口舌,是为了使大家明白现有的方法是建立在现有的结构上的,而当现有体系发生改变的时候,方法也会跟着改变。

显然,只要我们能在内容和序号之间建立一种函数关系,在现有储存结构上就能实现按内容存取了——内容→函数变换→序号。

实际上,任何可列的内容都是可以和整数一一对应的(我们总能找到这样的法则),但是,一一对应的代价很可能是整数的范围很广,结果使得空间的浪费很大。打个比方,一张1901~2000年事件索引表,只需要一个100大小的数组,0元素代表1901,99元素代表2000——这里也回答了很多人疑惑的问题,2000年究竟是不是21世纪,这么一对照就会发现这是个历史遗留问题,公元元年是公元1年而不是公元0年才会导致这样的问题,历法几千年来修订了好几回,我们也不要对这个问题太较真了,一句话,随大流。然而我们如果做一个人类历史的索引表,上下五千年(把古代人算上就是多少万年了),但却不是每年都有事发生(应该说是值得我们注意的事),更有甚者是确切的年份都不知道,显然前面的做法就不太合理了,绝大多数空间都是空闲的。

因此,实际上采用的函数变换都是带有压缩性质的,即输出的值域都是有限的一个范围,典型的就是0~表长。就像我们的日常经验一样,一压缩,就会有些元素被挤到一起,“你我不分”了。因此,还必须有合理处理“冲突”的办法。函数变换加上“冲突”处理方法,就构成了散列这种查找方法。

具体的散列函数和冲突处理,请阅读教科书,我不再详细说明了。

键树(Trie树)与基数排序

这其实都是建立在散列的思想上的,在他们身上,很容易就能发现链散列的影子,而Trie树更像是静态的基数排序。Trie树用来组织内存中的数据也是很好用的,并非是只适用于外存。那么一本厚书也仅仅是一两页,我这几十页的有这么一段也差不多了,^_^。具体请阅读教科书,一般读者可跳过。


 


前一篇:定做程序设计
后一篇:串口通信
分享到: