树的四种分类
Searchtrees:实例--二叉搜索树
什么是二叉搜索树
二叉搜索树(BinarySearchTree)是一棵有序的二叉树,所以我们也可以称它为二叉排序树(不知道二叉树的童鞋,先看看二叉树:传送门)。
具有以下性质的二叉树我们称之为二叉搜索树:若它的左子树不为空,那么左子树上的所有值均小于它的根节点;若它的右子树不为空,那么右子树上所有值均大于它的根节点。它的左子树和右子树分别也为二叉搜索树。
2、二叉搜索树的结构
二叉搜索树能够高效的进行一下操作:①插入一个数值②查询是否包含某个数值③删除某个数值
根据实现的不同,还可以实现其他各种操作,这是一种使用性很高的数据结构。我们来看一个例子:
这就是二叉搜索树的存储结构,所有的节点,都满足左子树上的比自己小,而右子树上的所有节点比自己大。二叉搜索树因为其有序性,所以它能够高效的管理数的集合
(1)查询
我们查找是否存在17:
根节点是7,因为小于17,所以去右子树查找
走到节点12,还是小于17,所以继续往右子树找
走到节点17,此时找到17。
(2)插入
我们使用查找的方式进行插入,以数字6为例,如图所示:
(3)删除
删除操作相对之前的其他两种操作,就略显复杂一些。一般来说我们可以分为三种情况:
需要删除的节点没有左儿子,那么就把右儿子提上去
需要删除的节点的左儿子没有右儿子,那么就把左儿子提上去
不满足上述的两种情况的话,就把左子树中最大的节点放到要删除的节点上。
3、二叉搜索树的复杂度
无论我们执行哪一个操作,其所花的时间都和树的高度成正比。我们不难得知,二叉搜索树的平均复杂度为O(logn)。
4、二叉搜索树的实现
通过上述的了解,我们大致已经知道二叉搜索树的工作原理。所以现在我们就来简单的实现二叉搜索树基本的增删查的功能,代码如下:[cpp]viewplaincopy1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.//表示节点的结构体structnode{intval;node*lch,*rch;};//插入整数xnode*insert(node*p,intx){if(p==NULL){node*newNode=newnode;newNode->val=x;newNode->lch=newNode->rch=NULL;p=newNode;}else{if(x
val)p->lch=insert(p->lch,x);elsep->rch=insert(p->rch,x);}returnp;}//查找整数xboolfind(node*p,intx){if(p==NULL)returnfalse;elseif(p->val==x)returntrue;elseif(p->val>x)returnfind(p->lch,x);elsereturnfind(p->rch,x);}//删除整数xnode*remove(node*p,intx){if(p==NULL)returnNULL;elseif(x
val)p->lch=remove(p->lch,x);elseif(x>p->val)p->rch=remove(p->rch,x);//情况elseif(p->lch==NULL){node*q=p->rch;deletep;returnq;}//情况elseif(p->lch->rch==NULL){
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.}node*q=p->lch;q->rch=p->rch;deletep;returnq;}//情况else{node*q;for(q=p->lch;q->rch->rch!=NULL;q=q->rch);node*r=q->rch;q->rch=r->lch;r->lch=p->lch;r->rch=p->rch;deletep;returnr;}returnp;
Heaps;实例--斐波那契堆
斐波纳契堆(FibonacciHeap)于1984年由MichaelL.Fredman与RobertE.Tarjan提出,1987年公开发表,名字来源于运行时分析所使用的斐波那契数。
斐波那契堆同二项堆(BinomialHeap)一样,也是一种可合并堆(MergeableHeap)。与二项堆一样,斐波那契堆是由一组最小堆有序树构成,但堆中的树并不一定是二项树。与二项堆中树都是有序的不同,斐波那契堆中的树都是有根而无序的。
特点:不涉及删除元素的操作有O(1)的平摊时间。Extract-Min和Delete的数目和其它相比较小时效率更佳。关键思想在于尽量延迟对堆的维护
稠密图每次Decrease-key只要O(1)的平摊时间,和二项堆的O(lgn)相比是巨大的改进。
斐波那契堆的结构较二项堆更松散。因此对结构的维护可以到方便时再做。
斐波那契堆中的树是有根而无序的。每个节点包含一个指向其父节点的指针p[x],以及一个指向其任一子女的指针child[x](指向子女双链表)。
每个孩子有left[x]和right[x]。(意义:在O(1)的时间内去掉一个节点,或者在O(1)的时间内合并双链表。)其它域:degree[x]存储子女个数。mark[x]指示自从x上一次成为另一节点的子女以来,它是否失掉一个孩子。
一个给定的斐波那契堆可以通过一个指向其含有最小关键字树的指针来访问。
斐波那契堆的关键思想在于尽量延迟对堆的维护。创建一个新的斐波那契堆:
MAKE_Fib_Heap有O(1)的代价。
插入一个节点:分三步进行:1,为新的节点置p,child,left,right,mark等域。时间消耗:O(1)。2,将包含x的根表和根表H连接。时间消耗:O(1)。3,在O(1)的时间内调整指向该堆的指针min[x]时间消耗:O(1)。以节点数表示势。势的增加为1,实际代价为O(1)。所以平摊代价为O(1)。
寻找最小节点:min[x]指向的节点即为最小节点。因为势没有变化,所以这个操作的平摊代价为O(1)。
合并两个斐波那契堆:分为3步:1。合并根表2。设置新的min[h]3。重置n[x]。抽取最小节点:这是最复杂的工作。被延迟的对根表的调整工作最终由这个操作进行。
1。去掉最小值,将其每个孩子都加入根表。2。将相同度数树的合并。
调整根表的步骤1。在根表中找出两个具有相同度数的根x和y,且key[x]《key[y]2。将y与x连接。将y从根表里去掉,成为x一个孩子,并增加degree[x]。
减小一个节点的权1。若此减小不影响堆序,不作调整。2。若影响堆序,则从堆中删除该节点,将其加入根表。并检查其父亲的mark位。
若为false,则停止,并将其置为true。若为true,则删除其父亲,继续递归向上执行。直到一个
节点mark域为false或该节点为根节点为止。
删除一个节点:1。将该节点权调整至最小2。抽取最小值。
证明最大度数界:证明删除或extract-min的平摊时间为O(lgn)。引理1:设x为斐波那契堆中任一节点,并假设degree[x]=k。设y1,y2,。。。yk表示按与x链接的次序排列的x的子女,从最早的到最迟的,则对i=2,3,...,k,有degree[y1]>=0且
degree[yi]>=i-2证明:显然degree[y1]》=0对i>=2,注意到y1被链接到x上时,y1,y2,。。yi-1都是x的子女,故我们必有degree[x]>=i-1又仅当degree[x]=degree[yi]时,才将yi链接到x上。故此时必有degree[yi>=i-1,在此之后,节点yi至多失去一个孩子,因为失去两个就被切断了。所以degree[yi]>=i-2
引理2:对所有的整数k>=0,Fk+2=1+sum(Fi)[0=G^k,其中G为黄金分割率。
(1+5^0.5)/2=1.161803...
引理3:设x为斐波那契堆中任一节点,并设k=degree[x],那么,size(x)>=Fk+2>=G^k。推论:在一个包含n个节点的斐波那契堆中节点的最大度数为O(lgn)。
对于斐波那契堆上的各种可合并操作,关键思想是尽可能久地将工作推后。例如,当向斐波那契堆中插入新结点或合并两个斐波那契堆时,并不去合并树,而是将这个工作留给EXTRACT-MIN操作
Spatialdatapartitioningtrees:实例--Burkhard-Keller树
BK树或者称为Burkhard-Keller树,是一种基于树的数据结构,被设计于快速查找近似字符串匹配,比方说拼写检查器,或模糊查找,当搜索”aeek”时能返回”seek”和”peek”。为何BK-Trees这么酷,因为除了穷举搜索,没有其他显而易见的解决方法,并且它能以简单和优雅的方法大幅度提升搜索速度。。
在定义BK树之前,我们需要预先定义一些操作。为了索引和搜索字典,我们需要一种比较字符串的方法。编辑距离(LevenshteinDistance)是一种标准的方法,它用来表示经过插入、删除和替换操作从一个字符串转换到另外一个字符串的最小操作步数。其它字符串函数也同样可接受(比如将调换作为原子操作),只要能满足以下一些条件。
除了字符串匹配、查找回文串、查找重复子串等经典问题以外,日常生活中我们还会遇到其它一些怪异的字符串问题。比如,有时我们需要知道给定的两个字符串“有多像”,换句话说两个字符串的相似度是多少。1965年,俄国科学家VladimirLevenshtein给字符
串相似度做出了一个明确的定义叫做Levenshtein距离,我们通常叫它“编辑距离”。字符串A到B的编辑距离是指,只用插入、删除和替换三种操作,最少需要多少步可以把A变成B。例如,从FAME到GATE需要两步(两次替换),从GAME到ACM则需要三步(删除G和E再添加C)。Levenshtein给出了编辑距离的一般求法,就是大家都非常熟悉的经典动态规划问题。
在自然语言处理中,这个概念非常重要,例如我们可以根据这个定义开发出一套半自动的校对系统:查找出一篇文章里所有不在字典里的单词,然后对于每个单词,列出字典里与它的Levenshtein距离小于某个数n的单词,让用户选择正确的那一个。n通常取到2或者3,或者更好地,取该单词长度的1/4等等。这个想法倒不错,但算法的效率成了新的难题:查字典好办,建一个Trie树即可;但怎样才能快速在字典里找出最相近的单词呢?这个问题难就难在,Levenshtein的定义可以是单词任意位置上的操作,似乎不遍历字典是不可能完成的。现在很多软件都有拼写检查的功能,提出更正建议的速度是很快的。它们到底是怎么做的呢?1973年,Burkhard和Keller提出的BK树有效地解决了这个问题。这个数据结构强就强在,它初步解决了一个看似不可能的问题,而其原理非常简单。
首先,我们观察Levenshtein距离的性质。令d(x,y)表示字符串x到y的Levenshtein距离,那么显然:
1.d(x,y)=0当且仅当x=y(Levenshtein距离为0字符串相等)
2.d(x,y)=d(y,x)(从x变到y的最少步数就是从y变到x的最少步数)
3.d(x,y)+d(y,z)>=d(x,z)(从x变到z所需的步数不会超过x先变成y再变成z的步数)
最后这一个性质叫做三角形不等式。就好像一个三角形一样,两边之和必然大于第三边。给某个集合内的元素定义一个二元的“距离函数”,如果这个距离函数同时满足上面说的三个性质,我们就称它为“度量空间”。我们的三维空间就是一个典型的度量空间,它的距离函数就是点对的直线距离。度量空间还有很多,比如Manhattan距离,图论中的最短路,当然还有这里提到的Levenshtein距离。就好像并查集对所有等价关系都适用一样,BK树可以用于任何一个度量空间。
建树的过程有些类似于Trie。首先我们随便找一个单词作为根(比如GAME)。以后插入一个单词时首先计算单词与根的Levenshtein距离:如果这个距离值是该节点处头一次出现,建立一个新的儿子节点;否则沿着对应的边递归下去。例如,我们插入单词FAME,它与GAME的距离为1,于是新建一个儿子,连一条标号为1的边;下一次插入GAIN,算得它与GAME的距离为2,于是放在编号为2的边下。再下次我们插入GATE,它与GAME距离为1,于是沿着那条编号为1的边下去,递归地插入到FAME所在子树;GATE与FAME的距离为2,于是把GATE放在FAME节点下,边的编号为2。
查询操作异常方便。如果我们需要返回与错误单词距离不超过n的单词,这个错误单词与树根所对应的单词距离为d,那么接下来我们只需要递归地考虑编号在d-n到d+n范围内的边所连接的子树。由于n通常很小,因此每次与某个节点进行比较时都可以排除很多子树。
举个例子,假如我们输入一个GAIE,程序发现它不在字典中。现在,我们想返回字典中所有与GAIE距离为1的单词。我们首先将GAIE与树根进行比较,得到的距离d=1。由于Levenshtein距离满足三角形不等式,因此现在所有离GAME距离超过2的单词全部可以排除了。比如,以AIM为根的子树到GAME的距离都是3,而GAME和GAIE之间的距离是1,那么AIM及其子树到GAIE的距离至少都是2。于是,现在程序只需要沿着标号范围在1-1到1+1里的边继续走下去。我们继续计算GAIE和FAME的距离,发现它为2,于是继续沿标号在1和3之间的边前进。遍历结束后回到GAME的第二个节点,发现GAIE和GAIN距离为1,输出GAIN并继续沿编号为1或2的边递归下去(那条编号为4的边连接的子树又被排除掉了)……
实践表明,一次查询所遍历的节点不会超过所有节点的5%到8%,两次查询则一般不会17-25%,效率远远超过暴力枚举。适当进行缓存,减小Levenshtein距离常数n可以使算法效率更高。
Tries;实例--散列
Hash表数据结构常识:
一、哈希表基于数组。
二、缺点:基于数组的,数组创建后难以扩展。某些哈希表被基本填满时,性能下降得非常严重。
三、没有一种简便得方法可以以任何一种顺序遍历表中数据项。
四、如果不需要有序遍历数据,并且可以提前预测数据量的大小,那么哈希表在速度和易用性方面是无与伦比的。
*若结构中存在和关键字K相等的记录,则必定在f(K)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hashfunction),按这个事先建立的表为散列表。
*对不同的关键字可能得到同一散列地址,即key1≠key2,而f(key1)=f(key2),这种现象称碰撞。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“象”作为记录在表中的存储位置,这种表便称为散列表,这一映象过程称为散列造表或散列,所得的存储位置称散列地址。
*若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(UniformHashfunction),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。
性质所有散列函数都有如下一个基本特性:如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面,散列函数的输入和输出不是一一对应的,如果两个散列值相同,两个输入值很可能是相同的,但并不能绝对肯定二者一定相等。输入一些数据计算出散列值,然后部分改变输入值,一个具有强混淆特性的散列函数会产生一个完全不同的散列值。
典型的散列函数都有无限定义域,比如任意长度的字节字符串,和有限的值域,比如固定长度的比特串。在某些情况下,散列函数可以设计成具有相同大小的定义域和值域间的一一对应。一一对应的散列函数也称为排列。可逆性可以通过使用一系列的对于输入值的可逆“混合”运算而得到。
常用HASH函数
·直接取余法:f(x):=xmodmaxM;maxM一般是不太接近2^t的一个质数。·乘法取整法:f(x):=trunc((x/maxX)*maxlongit)modmaxM,主要用于实数。
·平方取中法:f(x):=(x*xdiv1000)mod1000000);平方后取中间的,每位包含信息比较多。
构造方法散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快地定位。
(详细构造方法可以参考hash函数中的【哈希表的构造方法】)
1.直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key)=a·key+b,其中a和b为常数(这种散列函数叫做自身函数)
2.数字分析法
3.平方取中法
4.折叠法
5.随机数法
6.除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即H(key)=keyMODp,p
1.开放寻址法;Hi=(H(key)+di)MODm,i=1,2,…,k(k
1).di=1,2,3,…,m-1,称线性探测再散列;
2).di=1^2,(-1)^2,2^2,(-2)^2,(3)^2,…,±(k)^2,(k
3).di=伪随机数序列,称伪随机探测再散列。
2.再散列法:Hi=RHi(key),i=1,2,…,kRHi均是不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间。
3.链地址法(拉链法)
4.建立一个公共溢出区
查找性能分析散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到,另一些关键码在散列函数得到的地址上产生了冲突,需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中,产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以,对散列表查找效率的量度,依然用平均查找长度来衡量。
查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:
1.散列函数是否均匀;
2.处理冲突的方法;
3.散列表的装填因子。
散列表的装填因子定义为:α=填入表中的元素个数/散列表的长度
α是散列表装满程度的标志因子。由于表长是定值,α与“填入表中的元素个数”成正比,所以,α越大,填入表中的元素较多,产生冲突的可能性就越大;α越小,填入表中的元素较少,产生冲突的可能性就越小。
实际上,散列表的平均查找长度是装填因子α的函数,只是不同处理冲突的方法有不同的函数。
散列(Hash)同顺序、链式和索引存储结构一样,是存储线性表的又一种方法。散列存储的基本思想是:以线性表中的每个元素的关键字key为自变量,通过一种函数H(key)计算出函数值,把这个函数值解释为一块连续存储空间的单元地址(即下标),将该元素存储到这个单元中。散列存储中使用的函数H(key)称为散列函数或哈希函数,它实现关键字到存储地址的映射(或称转换),H(key)的值称为散列地址或哈希地址;使用的数组空间是线性表进行散列存储的地址空间,所以被称之为散列表或哈希表。当在散列表上进行查找时,首先根据给定的关键字key,用与散列存储时使用的同一散列函数H(key)计算出散列地址,然后按此地址从散列表中取对应的元素。
例如,有个线性表A=(31,62,74,36,49,77),其中每个整数可以是元素本身,也可以仅是元素的关键字,为了散列存储该线性表,假设选取的散列函数为:
H(key)=key%m
即用元素的关键字key整除m,取其余数作为存储该元素的散列地址,m一般取小于或等于散列表长的最大素数,在这里取m=11,表长也为11,因此可得到每个元素的的散列地
址:
H(31)=31%11=9;H(62)=62%11=7;
H(74)=74%11=8;H(36)=36%11=3;
H(49)=49%11=5;H(77)=77%11=0;
如果根据散列地址把上述元素存储到散列表HT[m]中,则存储结构为:
散列的基本概念
从散列表中查找元素与插入元素一样简单,如从HT中查找关键字为36的元素时,只要利用上述散列函数H(key)计算出key=36时的散列地址3,则从下标为3的单元中取出该元素即可。
在上面的散列表上插入时根据元素的关键字计算出的散列地址,其对应的存储单元都是空闲的,没有出现该单元已被其它元素占的情况。在实际应用中这种理想的情况是很少见的,例如,要在上面的散列表中插入一个关键字为19的元素时,计算出其散列地址为8,而8号单元已被关键字为74的元素所占用,通常我们把这种现象称为冲突。具相同散列地址的关键字称为同义词。因此,在设计散列函数时,要尽量减少或没有冲突存在,但少量的冲突往往是不可避免的。这样就存在如何解决冲突的问题。冲突的频度除了与散列函数H相关外,还与散列表的填满程度相关。因此,如何尽量避免冲突和冲突发生后如何解决冲突就成了散列存储的两个关键问题。
构造散列函数的目标是使散列地址尽可能均匀分布在散列空间上,同时使计算尽可能简单。构造散列函数的方法很多,常用的构造散列函数的方法有如下几种。
1.直接地址法
直接地址法是以关键字key本身或关键字加上某个常量C作为散列地址的方法。对应的散列函数H(key)为:
H(key)=key+c
在使用时,为了使散列地址与存储空间吻合,可以调整c。这种方法计算简单,并且没有冲突。它适合于关键字的分布基本连续的情况,若关键字分布不连续,空号较多,将会造成较的空间浪费。
2.数字分析法
数字分析法是假设有一组关键字,每个关键字由n位数字组成,如k1,k2…kn。数字选择法是从中提取数字分布比较均匀的若干位作为散列地址。
例如,有一组有6位数字组成的关键字,如下表左边一列表示:
关键字散列地址(0..99)
散列的基本概念
分析这一组关键字会发现,第1、3、5和6位数字分布不均匀,第1位数字全是9或8,第3位基本上都是2,第5、6两位上也都基本上是5和6,故这4位不可取。而第2、4两位数字分布比较均匀,因此可取关键字中第2、4两位的组合作为散列地址,如上表的右边一列所示。
3.除余数法
除余数法是选择一个适当的p(p≤散列表长m)去除关键字k,所得余数作为散列地址的方法。对应的散列函数H(k)为:
H(k)=k%p
其中p最好选取小于或等于表长m的最大素数。如表长为20,那么p选19,若表长为25,则p可选23,…。表长m与模p的关系可按下表对应:
m=8,16,32,64,128,256,512,1024,…
p=7,13,31,61,127,251,503,1019,…
这是一种最简单,也是最常用的一种散列函数构造方法。在上一节中我们已经使用过。
4.平方取中法
平方取中法是取关键字平方的中间几位作为散列地址的方法,因为一个乘积的中间几位和乘数的每一位都相关,故由此产生的散列地址较为均匀,具体取多少位视实际情况而定。例如有一组关键字集合(0100,0110,0111,1001,1010,1110),平方之后得到新的数据集合(0010000,0012100,0012321,1002001,1020100,123210),那么,若表长为1000,则可取其中第3、4和5位作为对应的散列地址为(100,121,123,020,201,321)。
(5)折叠法
折叠法是首先把关键字分割成位数相同的几段(最后一段的位数可少一些),段的位数取决于散列地址的位数,由实际情况而定,然后将它们的叠加和(舍去最高进位)作为散列地址的方法。
折叠法又分移位叠加和边界叠加。移位叠加是将各段的最低位对齐,然后相加;边界叠加则是将两个相邻的段沿边界来回折叠,然后对齐相加。
例如,关键字k=98123658,散列地址为3位,则将关键字从左到右每三位一段进行划分,得到的三个段为981、236和58,叠加后值为1275,取低3位275作为关键字98123658的元素的散列地址;如若用边界叠加,即为981、632和58叠加后其值为1671,取低3位得671作为散列地址。
散列法构造表可通过散列函数的选取来减少冲突,但冲突一般不可避免,为此,需要有解决冲突的方法,常用的解决冲突的方法有两大类,即开放定址法和链地址法。
1.开放定址法
开放定址法又分为线性探插法、二次探查法和双重散列法。开放定址法解决冲突的基本思想是:使用某种方法在散列表中形成一个探查序列,沿着次序列逐个单元进行查找,直到
找到一个空闲的单元时将新结点存入其中。假设散列表空间为T[0..m-1],散列函数H(key),开放定址法的一般形式为:hi=(H(key)+di)%m0≤i≤m-1
其中di为增量序列,m为散列表长。h0=H(key)为初始探查地址(假d0=0),后续的探查地址依次是h1,h2,…,hm-1。
(1)线性探查法
线性探查法的基本思想是:将散列表T[0..m-1]看成一个循环向量,若初始探查的地址为d(即H(key)=d),那么,后续探查地址的序列为:d+1,d+2,…,m-1,0,1,…,d-1。也就是说,探查时从地址d开始,首先探查T[d],然后依次探查T[d+1],…,T[m-1],此后又循环到T[0],T[1],…,T[d-1]。分两种情况分析,一种运算是插入:若当前探查单元为空,则将关键字key写入空单元,若不空则继续后序地址探查,直到遇到空单元插入关键字,若探查到T[d-1]时仍未发现空单元,则插入失败(表满);另一种运算是查找,若当前探查单元关键字值等于key,则表示查找成功,若不等于,则继续后序地址探查,若遇到单元关键字值等于key时,查找成功,若探查T[d-1]时仍未发现关键字值等于key,则查找失败。
(2)二次探查法
二次探查法的探查序列是:hi=(H(key)+i2)%m0≤i≤m-1
即探查序列为:d=H(key),d+12,d+22,…,等。也就是说,探查从地址d开始,先探查T[d],然后在依次探查T[d+12],T[d+22],…。
(3)双重散列法
双重散列法是几种方法中最好的方法,它的探查序列为:
hi=(H(key)+i*H1(key))%m0≤i≤m-1
即探查序列为:d=H(key),(d+1*H1(key))%m,(d+2*H1(key))%m,…,等。
【例9.4】设散列函数为h(key)=key%11;散列地址表空间为0~10,对关键字序列{27,13,55,32,18,49,24,38,43},利用线性探测法解决冲突,构造散列表。
解:首先根据散列函数计算散列地址:
h(27)=5;h(13)=2;
h(55)=0;h(32)=10;
h(18)=7;h(49)=5;
h(24)=2;h(38)=5;
h(43)=10;
(散列表各元素查找比较次数标注在结点的上方或下方)
根据散列函数计算得到的散列地址可知,关键字27、13、55、32、18插入的地址均为开放地址,将它们直接插入到T[5],T[2],T[0],T[10],T[7]中。当插入关键字49时,散列地址5已被同义词27占用,因此探查h1=(5+1)%11=6,此地址为开放地址,因此可将49插入到T[6]中;当插入关键字24时,其散列地址2已被同义词13占用,故探测地址
h1=(2+1)%11=3,此地址为开放地址,因此可将24插入到T[3]中;当关键字38插入时,散列地址5已被同义词27占用,探查h1=(5+1)%11=6,也被同义词49占用,再探查
h2=(5+2)=7,地址7已被非同义词占用,因此需要再探查h3=(5+3)%11=8,此地址为开放
地址,因此可将38插入到T[8]中;当插入关键字43时,计算得到散列地址10已被关键字32占用,需要探查h1=(10+1)%11=0,此地址已被占用,探查h2=(10+1)%11=1为开放地址,因此可将43插入到T[1]中;由此构造的散列表如图9.13所示。
散列的基本概念
2.拉链法(链地址法)
当存储结构是链表时,多采用拉链法,用拉链法处理冲突的办法是:把具有相同散列地址的关键字(同义词)值放在同一个单链表中,称为同义词链表。有m个散列地址就有m个链表,同时用指针数组T[0..m-1]存放各个链表的头指针,凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。T中各分量的初值应为空指针。
例如,按上面例9.4所给的关键字序列,用拉链法构造散列表如图9.14所示。散列的基本概念
用拉链法处理冲突,虽然比开放定址法多占用一些存储空间用做链接指针,但它可以减少在插入和查找过程中同关键字平均比较次数(平均查找长度),这是因为,在拉链法中待比较的结点都是同义词结点,而在开放定址法中,待比较的结点不仅包含有同义词结点,而且包含有非同义词结点,往往非同义词结点比同义词结点还要多。
如前面介绍的例9.4中,用线性探测法构造散列表的过程,我们知道,对前5个关键字的查找,每一个仅需要比较一次,对关键字49和24的查找,则需要比较2次,对关键字38的查找则需要比较4次,而对43的查找则需要比较3次。因此,对用线性探测法构造的散列表的平均查找长度为:
ASL=(1×5+2×2+3×1+4×1)/9≈1.78
而用拉链法构造的散列表上查找成功的平均查找长度为:
ASL=(1×5+2×3+3×1)/9≈1.55
显然,开放定址法处理冲突的的平均查找长度要高于拉链法处理冲突的平均查找长度。但它们都比前面介绍的其它查找方法的平均查找长度要短。