第九章查找表.ppt

1、2009-2,计算机与信息学院数据结构,第1页,第九章 查找表,何谓查找表 ？,查找表是由同一类型的数据元素(或记录)构成的集合。,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。,2009-2,计算机与信息学院数据结构,第2页,对查找表经常进行的操作:,1）查询某个“特定的”数据元素是否在查找表中； 2）检索某个“特定的”数据元素的各种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素。,2009-2,计算机与信息学院数据结构,第3页,仅作查询和检索操作的查找表。,静态查找表,有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素

2、插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。,动态查找表,查找表可分为两类:,2009-2,计算机与信息学院数据结构,第4页,是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。,关键字,若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。,若此关键字能识别若干记录，则称之谓“次关键字”。,2009-2,计算机与信息学院数据结构,第5页,根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）,查找,若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置； 否则称

3、“查找不成功”，查找结果：给出 “空记录”或“空指针”。,2009-2,计算机与信息学院数据结构,第6页,由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系，即用另外一种结构来表示查找表。,如何进行查找？,查找的方法取决于查找表的结构。,2009-2,计算机与信息学院数据结构,第7页,9.1 静态查找表,9.2 动态查找表,9.3 哈希表,2009-2,计算机与信息学院数据结构,第8页,9.1 静 态 查 找 表,数据对象D：,数据关系R：,D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字

4、，可唯一标识数据元素。,数据元素同属一个集合。,ADT StaticSearchTable ,抽象数据类型静态查找表的定义,2009-2,计算机与信息学院数据结构,第9页,Create(,Destroy(,Search(ST, key);,Traverse(ST, Visit();,基本操作 P：, ADT StaticSearchTable,/构造一个含 n 个数据元素的静态查找表ST。,/销毁已存在静态查找表ST。,/若 ST 中存在其关键字等于 key 的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。,/按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Vi

5、sit()失败，则操作失败。,2009-2,计算机与信息学院数据结构,第10页,假设静态查找表的顺序存储结构为,typedef struct ElemType *elem; / 数据元素存储空间基址，建表时按实际长度分配，0号单元留空 int length; / 表的长度 SSTable;,数据元素类型的定义为:,typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ;,2009-2,计算机与信息学院数据结构,第11页,一、顺序查找表(以顺序表或线性链表表示静态查找表),ST.elem,回顾顺序表的查找过程：,假设给定值 e = 64, 要求

6、ST.elemi = e, 问: i = ?,66,基本思想：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。,2009-2,计算机与信息学院数据结构,第12页,int location( SqList L, ElemType e, Status (*compare)(ElemType, ElemType) i = 1; p = L.elem; while ( i=L.length /location,i=L.length,2009-2,计算机与信息学院数据结构,第13页,ST

7、.elem,ST.elem,60,key = 64,key = 60,64,基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。,改进的顺序查找,2009-2,计算机与信息学院数据结构,第14页,int Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 ST.elem0.key = key; / 设置“哨兵” for (i=ST.length; -i); / 从后往前找

8、 return i; / 找不到时，i为0 / Search_Seq,ST.elemi.key!=key;,2009-2,计算机与信息学院数据结构,第15页,2009-2,计算机与信息学院数据结构,第16页,顺序表查找的平均查找长度为：,对顺序表而言，Ci = n-i+1,ASL = nP1 +(n-1)P2 + +2Pn-1+Pn,在等概率查找的情况下，,2009-2,计算机与信息学院数据结构,第17页,若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。,在不等概率查找的情况下，ASLss 在 PnPn-1P2P1 时取极小值,200

9、9-2,计算机与信息学院数据结构,第18页,平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。,顺序查找的缺点：,算法简单而且使用面广。 对表中记录的存储没有任何要求，顺序存储和链接存储均可； 对表中记录的有序性也没有要求，无论记录是否按关键码有序均可。,顺序查找的优点：,2009-2,计算机与信息学院数据结构,第19页,上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。,二、有序表的查找,若以有序表表示静态查找表，则查找过程可以基于“折半”进行。即先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。,2009-2,计算机

10、与信息学院数据结构,第20页,折半查找,使用条件： 线性表中的记录必须按关键码有序； 必须采用顺序存储。,基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。,2009-2,计算机与信息学院数据结构,第21页,ST.elem,ST.length,例如: key = 64 的查找过程如下,low,high,mid,low,mid,high,mid,low 指示查找区间的下界;

11、high 指示查找区间的上界; mid = (low+high)/2。,2009-2,计算机与信息学院数据结构,第22页,int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值 while (low = high) mid = (low + high) / 2; if （key = ST.elemmid.key ) return mid; / 找到待查元素 else if ( key ST.elemmid.key) ) high = mid - 1; / 继续在前半区间进行查找 else low

12、 = mid + 1; / 继续在后半区间进行查找 return 0; / 顺序表中不存在待查元素 / Search_Bin,2009-2,计算机与信息学院数据结构,第23页,先看一个具体的情况，假设：n=11,分析折半查找的平均查找长度,6,3,9,1,4,2,5,7,8,10,11,判定树,1,2,2,3,3,3,3,4,4,4,4,2009-2,计算机与信息学院数据结构,第24页,假设 n=2h-1 并且查找概率相等则,一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。,在 n50 时，可得近似结果,2009-2,计算机与信息学院数据结构,第25页

13、,分块查找又称为索引查找，它是一种性能介于顺 序查找和二分查找之间的查找算法。 分块查找要求将被查找表分成块，建立块索引。 每一块中的关键字不一定有序，但前一块中的最 大关键字必须小于后一块中的最小关键字，即要 “分块有序”。 抽取各块中的最大关键字及其起始位置构成一个 索引表。由于被查找表是分块有序的，所以索引表是一个递增有序表。,三、索引顺序表（分块查找）,2009-2,计算机与信息学院数据结构,第26页,13,3,9,20,33,42,44,38,60,80,74,49,86,53,22,12,0,6,12,22,48,86,24,48,0 1 2 3 4 5 6 7 8 9 10 11

14、 12 13 14 15 16 17,分块查找的基本思想：首先，查找索引表，因为索引表是有序表，故可采用二分查找，也可以采用顺序查找，以确定待查的结点在哪一块；然后在以确定的那一块中顺序查找。,2009-2,计算机与信息学院数据结构,第27页,算法分析,由于分块查找实际上是两次查找过程，故整个算法的平均查找长度应该是两次查找的平均查找长度之和。若以二分查找来确定块，则分块查找的平均查找长度约为：,若以顺序查找来确定块，则分块查找的平均查找长度约为：,对于后一种情况，当 时，平均查找长度为极小值。在实用中，可根据表的具体情况进行分块。,2009-2,计算机与信息学院数据结构,第28页,分块查找的

15、性能介于顺序查找和二分查找之间的，例如，对长度为10000的线性表，它们的平均查找长度分别是：,顺序查找：约5000 分块查找：约100 二分查找：约14,2009-2,计算机与信息学院数据结构,第29页,9.2 动 态 查 找 表,动态查找表的特点：表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。,2009-2,计算机与信息学院数据结构,第30页,ADT DynamicSearchTable ,抽象数据类型动态查找表的定义如下：,数据对象D： 数据关系R：,数据元素同属一个集合。,D是具有相同特性的数

16、据元素的集合。 每个数据元素含有类型相同的关键字， 可唯一标识数据元素。,2009-2,计算机与信息学院数据结构,第31页,InitDSTable(,InsertDSTable(,DeleteDSTable(,TraverseDSTable(DT, Visit();,ADT DynamicSearchTable,2009-2,计算机与信息学院数据结构,第32页,一、二叉排序树（二叉查找树）,1定义,2查找算法,3插入算法,4删除算法,5查找性能的分析,2009-2,计算机与信息学院数据结构,第33页,（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；,1定义：,二叉排序树或者是一

17、棵空树；或者是具有如下特性的二叉树：,（3）它的左、右子树也都分别是二叉排序树。,（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；,2009-2,计算机与信息学院数据结构,第34页,例如:,是二叉排序树。,不,2009-2,计算机与信息学院数据结构,第35页,通常，取二叉链表作为二叉排序树的存储结构,typedef struct BiTNode / 结点结构 struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,TElemType data;,2009-2,计算机与信息学院数据结构,第36页,2二叉排序树的查找算

18、法：,1）若给定值等于根结点的关键字，则查找成功； 2）若给定值小于根结点的关键字，则继续在左子树上进行查找； 3）若给定值大于根结点的关键字，则继续在右子树上进行查找。,若二叉排序树为空，则查找不成功；否则,2009-2,计算机与信息学院数据结构,第37页,例如:,二叉排序树,查找关键字,= 50 ,50,50,35 ,50,30,40,35,50,90 ,50,80,90,95 ,2009-2,计算机与信息学院数据结构,第38页,从上述查找过程可见，,在查找过程中，生成了一条查找路径:,从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;,或者,从根结点出发，沿着左分支或右

19、分支逐层向下直至指针指向空树为止。,查找成功,查找不成功,2009-2,计算机与信息学院数据结构,第39页,算法描述如下：,Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree 否则表明查找不成功，返回 / 指针 p 指向查找路径上访问的最后一个结点， / 并返回函数值为FALSE, 指针 f 指向当前访问 / 的结点的双亲，其初始调用值为NULL / SearchBST, ,2009-2,计算机与信息学院数据结构,第40页,if (!T) else if ( EQ(key, T-data.key) ) else if ( LT(k

20、ey, T-data.key) ) else, p = f; return FALSE; / 查找不成功, p = T; return TRUE; / 查找成功,return SearchBST (T-lchild, key, T, p ); / 在左子树中继续查找,return SearchBST (T-rchild, key, T, p ); / 在右子树中继续查找,2009-2,计算机与信息学院数据结构,第41页,f,T,设 key = 48,f,T,f,T,22,p,f,T,f,T,T,T,T,f,f,f,p,2009-2,计算机与信息学院数据结构,第42页,根据动态查找表的定义，“插

21、入”操作在查找不成功时才进行;,3二叉排序树的插入算法,若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。,2009-2,计算机与信息学院数据结构,第43页,Status Insert BST(BiTree / Insert BST, ,2009-2,计算机与信息学院数据结构,第44页,s = (BiTree)malloc(sizeof( BiTNode); / 为新结点分配空间 s-data = e; s-lchild = s-rchild = NULL;,if ( !p ) T = s; / 插入 s 为新的根结点,else

22、if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入 *s 为 *p 的左孩子 else p-rchild = s; / 插入 *s 为 *p 的右孩子,return TRUE; / 插入成功,2009-2,计算机与信息学院数据结构,第45页,（1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有右子树； （3）被删除的结点既有左子树，也有右子树。,4二叉排序树的删除算法,可分三种情况讨论：,和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。,2009-2,计算机与信息学院数据结构,第46页

23、,（1）被删除的结点是叶子结点,例如:,被删关键字 = 20,88,其双亲结点中相应指针域的值改为“空”,2009-2,计算机与信息学院数据结构,第47页,（2）被删除的结点只有左子树或者只有右子树,其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。,被删关键字 = 40,80,2009-2,计算机与信息学院数据结构,第48页,（3）被删除的结点既有左子树，也有右子树,40,40,以其前驱替代之，然后再删除该前驱结点,被删结点,前驱结点,被删关键字 = 50,2009-2,计算机与信息学院数据结构,第49页,Status DeleteBST (BiTree / 不存在关键字等

24、于key的数据元素 else / DeleteBST,算法描述如下：, ,2009-2,计算机与信息学院数据结构,第50页,if ( EQ (key, T-data.key) ) / 找到关键字等于key的数据元素 else if ( LT (key, T-data.key) ) else, Delete (T); return TRUE; ,return DeleteBST ( T-lchild, key ); / 继续在左子树中进行查找,return DeleteBST ( T-rchild, key ); / 继续在右子树中进行查找,2009-2,计算机与信息学院数据结构,第51页,vo

25、id Delete ( BiTree p = p-lchild; free(q);,q,q,2009-2,计算机与信息学院数据结构,第53页,/ 左子树为空树只需重接它的右子树,q = p; p = p-rchild; free(q);,p,p,q,q,2009-2,计算机与信息学院数据结构,第54页,q = p; s = p-lchild; while (s-rchild) q = s; s = s-rchild; / s 指向被删结点的前驱,/ 左右子树均不空,p-data = s-data; if (q != p ) q-rchild = s-lchild; else q-lchild

26、= s-lchild; / 重接*q的左子树 free(s);,q,s,2009-2,计算机与信息学院数据结构,第55页,5查找性能的分析,对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。,2009-2,计算机与信息学院数据结构,第56页,由关键字序列 3，1，2，5，4构造而得的二叉排序树,由关键字序列 1，2，3，4，5构造而得的二叉排序树，,例如：,2,1,3,4,5,3,5,4,1,2,ASL =（1+2+3+4+5）/ 5 = 3,ASL =（1+

27、2+3+2+3）/ 5 = 2.2,2009-2,计算机与信息学院数据结构,第57页,下面讨论平均情况:,不失一般性，假设长度为 n 的序列中有 k 个关键字小于第一个关键字，则必有 n-k-1 个关键字大于第一个关键字,由它构造的二叉排序树,n-k-1,k,的平均查找长度是 n 和 k 的函数,P(n, k) ( 0 k n-1 ),2009-2,计算机与信息学院数据结构,第58页,假设 n 个关键字可能出现的 n! 种排列的可能性相同，则含 n 个关键字的二叉排序树的平均查找长度,在等概率查找的情况下，,2009-2,计算机与信息学院数据结构,第59页,2009-2,计算机与信息学院数据结

28、构,第60页,由此,可类似于解差分方程，此递归方程有解：,2009-2,计算机与信息学院数据结构,第61页,平衡二叉树是二叉查找树的另一种形式，其特点为：,树中每个结点的左、右子树深度之差的绝对值不大于1 。,例如:,是平衡树,不是平衡树,平衡因子（BF）：结点的左、右子树深度之差，任一结点的平衡因子只能取：-1、0 或 1。,二、平衡二叉树,2009-2,计算机与信息学院数据结构,第62页,如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。调整平衡过程为平衡旋转。,平衡旋转可以归纳为四类： LL平衡旋转 RR平衡旋转 LR平衡旋转 RL平衡旋转,2

29、009-2,计算机与信息学院数据结构,第63页,从发生不平衡的结点起，得到一棵子树。 如果这子树上结点处于一条直线上，则采用单旋转进行平衡化。 如果这子树上的结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。,右单旋转,左单旋转,左右双旋转,右左双旋转,2009-2,计算机与信息学院数据结构,第64页,右单旋转 (LL),h,h,h,A,C,E,B,D,(a) (b) (c),h,h + 1,B,A,C,E,D,h,h,h + 1,C,E,A,B,D,在左子树D上插入新结点使其高度增1，导致结点A的平衡因子增到 2，造成了不平衡。 为使树恢复平衡，从A沿插入路径连续

30、取3个结点A、B和D，它们处于一条方向为“/”的直线上，需做右单旋转。 以结点B为旋转轴，将结点A顺时针旋转。,h,0,0,0,1,1,2,2009-2,计算机与信息学院数据结构,第65页,左单旋转 (RR ),h,h,h,A,C,E,B,D,(a) (b) (c),h,h,h + 1,B,A,C,E,D,h,h,h + 1,C,E,A,B,D,如果在子树E中插入一个新结点，该子树高度增1导致结点A的平衡因子变成-2，出现不平衡。 沿插入路径检查三个结点A、C和E。它们处于一条方向为“”的直线上，需要做左单旋转。 以结点C为旋转轴，让结点A反时针旋转。,-1,-2,0,-1,0,0,2009-

31、2,计算机与信息学院数据结构,第66页,先左后右双旋转 (LR),在C的子树CL或CR中插入新结点，该子树的高度增1。结点A的平衡因子变为+2，发生了不平衡,2009-2,计算机与信息学院数据结构,第67页,从结点A起沿插入路径选取3个结点A、B和C(“”型) 以结点C为旋转轴，做单向左下旋转 再以结点C为旋转轴，做单向右下旋转,2009-2,计算机与信息学院数据结构,第68页,先右后左双旋转 (RL),在C的子树CL或CR中插入新结点，该子树的高度增1。结点A的平衡因子变为-2，发生了不平衡,2009-2,计算机与信息学院数据结构,第69页,从结点A起沿插入路径选取3个结点A、C和D(“”型

32、) 以结点C为旋转轴，作单向右旋 再以结点C为旋转轴，作单向左旋,2009-2,计算机与信息学院数据结构,第70页,例 设一组记录的关键字按以下次序进行插入：8，5，4，9，10，7，2，3，生成平衡二叉排序树的过程如下：,2009-2,计算机与信息学院数据结构,第71页,2009-2,计算机与信息学院数据结构,第72页,1.定义 一棵m阶的B-树,或为空树,或为满足下列特性的m叉树: (1)树中每个结点至多有m棵子树。 (2)除非根结点为叶子结点,否则至少有两棵子树。 (3)除根之外的所有非终端结点至少有m/2棵子树。 (4)所有的非终端结点的结构如下:,其中,k1,k2,.,kn为n个按从

33、小到大顺序排列的键值; p0,pl,p2,.,pn为(n+1)个指针,用于指向该结点的(n+l)棵子树,p0所指向子树中的所有关键字的值均小于kl,pn所指向子树中的所有关键字的值均大于kn,pi(1in-1)所指向子树中的所有关键字的值均大于ki且小于ki+1; n(nm-1)为键值的个数,即子树个数为(n+l)。,三、 B - 树,2009-2,计算机与信息学院数据结构,第73页,(5)所有叶子结点在同一个层次上,且不含有任何信息。,从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找 两个过程交叉进行。,2.查找过程：,若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点

34、中的位置；,若查找不成功，则返回插入位置。,2009-2,计算机与信息学院数据结构,第74页,a,t,b,c,d,f,g,e,h,例如，在图9-13所示B_树中查找关键字80和38,2009-2,计算机与信息学院数据结构,第75页,性能分析 在B-树上进行查找需比较的结点数最多为B-树的高度,B-树的高度与B-树的阶m和键值总数N有关； 分析： (1)若B-树的高度为h+1,则h+1层(即叶结点所在的层)的结点数为N+1。 因为每个非叶结点中的指针数等于其中的键值数加1,因此有: 结点总数=指针总数+1=(键值总数N+非叶结点数)+l (h+1)层的结点数=叶结点数=结点总数非叶结点数=N+1

35、。 (2)根据B-树的定义,B-树的第一层(即根结点)的结点数至少为1个,第二层的结点数至少为2,第三层的结点数至少为2*m/2,第四层的结点数至少为2*(m/2)2,以此类推,第h+1层的结点数至少为2*(m/2)h-1。 (3)综上所述,可得到如下不等式: h1+logm/2(N+1)/2,2009-2,计算机与信息学院数据结构,第76页,3、B-树的插入操作 插入方法： 首先要经过一个从树根结点到叶子结点的查找过程,如果键值k已在树中,则不用做其他事;否则,找出插入位置,然后再进行插入。对于叶子结点处于第(h+1)层的树,插入的位置总是在第h层。若结点的关键字值个数不超过(m-l),直接

36、插入即可;否则需要把结点分裂成两个。 分裂的做法： 取一新结点,把原结点上的键和k按升序排序后,从中间位置(m/2)把键值(不包括中间位置的键值)分成两部分,左部分所含键值放在旧结点中,右部分所含键值放在新结点中,中间位置键值连同新结点的存储位置插入到父亲结点中。若父结点的键值个数超过(m-l),要再分裂,再往上插,直至这个过程传到根结点为止。,2009-2,计算机与信息学院数据结构,第77页,2009-2,计算机与信息学院数据结构,第78页,2009-2,计算机与信息学院数据结构,第79页,4、B-树的删除 删除方法 在深度为(h+l)的m阶B-树中删除一个键值k,首先要查到键值k所在的结点

37、及在结点中的位置。若k所在结点的层数小于h,则把该结点的右边(或左边)指针所指子树中的最小(或最大)键值与k对调,使k移到第h层,这样可根据k所在结点为第h层结点的情况进行删除,从B_树上第h层结点中删除一个键值后,使得该结点的值个数n减1,此时应分以下三种情况进行处理: (1)若删除后结点中键值数目n m/21,在该结点中删去键值k连同右边的指针. (2)若删除后结点中键值数目n m/21,且左(或右)兄弟结点的关键字数目m/21,则把左(或右)兄弟结点中最大(或最小)键值移到父结点中,再把父结点大于(或小于)上移键值的键值下移到被删关键字所在结点中。,2009-2,计算机与信息学院数据结构

38、,第80页,(3)若删除后结点中键值数目nm/21,及其左、右兄弟结点的键值数目都等于m/21,则进行结点的“合并”,即把应删的键值删去后,将该结点中的剩余键值和指针连同父结点中指向该结点指针的左边(或右边)一个键值ki一起合并到左兄弟(或右兄弟)结点中,将ki从父结点中删去。如果因此使父结点中关键字数目m/21,则对此父结点做同样处理,以致于可能直到对根结点做这样的处理而使整个树减少一层。,2009-2,计算机与信息学院数据结构,第81页,2009-2,计算机与信息学院数据结构,第82页,2009-2,计算机与信息学院数据结构,第83页,以上两节讨论的表示查找表的各种结构的共同特点：记录在表

39、中的位置和它的关键字之间不存在一个确定的关系，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。,一、什么是哈希表？,9.3 哈 希 表,用这类方法表示的查找表，其平均查找长度都不为零。不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。,2009-2,计算机与信息学院数据结构,第84页,只有一个办法：预先知道所查关键字在表中的位置，,对于频繁使用的查找表，希望 ASL = 0。,即要求：记录在表中位置和其关键字之间存在一种确定的关系。,例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000

40、xx999 (前两位为年份)。,若以下标为000 999 的顺序表表示之。,则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。,2009-2,计算机与信息学院数据结构,第85页,但是，对于动态查找表而言，,因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key) 作为关键字作为 key 的记录在表中的位置，通常称这个函数 f(key) 为哈希函数。,1) 表长不确定；,2) 在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。,2009-2,计算机与信息学院数据结构,第86页,Zhao, Qian, Sun

41、, Li, Wu, Chen, Han, Ye, Den,例如：对于如下 9 个关键字,设 哈希函数 f(key) = (Ord(第一个字母) -Ord(A)+1)/2,Chen,Zhao,Qian,Sun,Li,Wu,Han,Ye,Den,问题: 若添加关键字 Zhou , 怎么办？,能否找到另一个哈希函数？,2009-2,计算机与信息学院数据结构,第87页,1) 哈希(Hash)函数是一个映象，即： 将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可;,从这个例子可见，,2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，

42、即： key1 key2，而 f(key1) = f(key2)。,2009-2,计算机与信息学院数据结构,第88页,3) 很难找到一个不产生冲突的哈希函数。 一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。,因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外;还需要找到一种“处理冲突” 的方法。,2009-2,计算机与信息学院数据结构,第89页,哈希表的定义:,根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“像”作为相应记录在表中的存储位置，

43、如此构造所得的查找表称之为“哈希表”。,2009-2,计算机与信息学院数据结构,第90页,二、构造哈希函数的方法,对数字的关键字可有下列构造方法:,若是非数字关键字，则需先对其进行数字化处理。,1. 直接定址法,3. 平方取中法,5. 除留余数法,4. 折叠法,6. 随机数法,2. 数字分析法,设计散列函数一般应遵循以下原则： 计算简单。散列函数不应该有很大的计算量，否则会降低查找效率。 函数值(散列地址)分布均匀。函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利用并减少冲突。,2009-2,计算机与信息学院数据结构,第91页,哈希函数为关键字的线性函数 H(key) = key

44、或者 H(key) = a key + b,1. 直接定址法,此法仅适合于： 地址集合的大小 = = 关键字集合的大小,例：关键码集合为10, 30, 50, 70, 80, 90，选取的散列函数为H(key)=key/10，则散列表为：,10,30,50,70,80,90,2009-2,计算机与信息学院数据结构,第92页,此方法仅适合于： 能预先估计出全体关键字的每一位上各种数字出现的频度。,2. 数字分析法,假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, , us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为地址。,例：关键码为8位十进制数，散

45、列地址为2位十进制数,8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7, ,2009-2,计算机与信息学院数据结构,第93页,以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。,3. 平方取中法,此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。,例：散列地址为2位，则关键码1234的散列地址为：,(1234)21522756,2009-2,计算机与

46、信息学院数据结构,第94页,4. 折叠法,此方法适合于: 关键字的数字位数特别多。事先不知道关键码的分布。,将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。,例：设关键码为2 5 3 4 6 3 5 8 7 0 5，散列地址为三位。,2 5 3 4 6 3 5 8 7 + 0 5 1 3 0 8 移位叠加,2 5 3 3 6 4 5 8 7 + 5 0 1 2 5 4 间界叠加,2009-2,计算机与信息学院数据结构,第95页,5. 除留余数法,设定哈希函数为: H(key) = key MOD p 其中， pm (表长) 并且 p 应为不大于

47、m 的素数 或是不含 20 以下的质因子的合数。,除留余数法是一种最简单、也是最常用的构造散列函数的方法，并且不要求事先知道关键码的分布。,2009-2,计算机与信息学院数据结构,第96页,6.随机数法,设定哈希函数为: H(key) = Random(key) 其中，Random 为伪随机函数,通常，此方法用于对长度不等的关键字构造哈希函数。,实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。,2009-2,计算机与信息学院数据结构,第97页,三、处理冲突的方法,“处理冲突” 的实际含义是： 为产生冲突的

48、地址寻找下一个哈希地址,1. 开放定址法,3 .再哈希法,4.建一个公共溢出区,2. 链地址法,通常有以下几种处理冲突的方法:,2009-2,计算机与信息学院数据结构,第98页,为产生冲突的地址 H(key) 求得一个地址序列： H0, H1, H2, , Hs 1 sm-1 其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, , s,1. 开放定址法,对增量 di 常有三种取法：,1) 线性探测再散列 di = c i 最简单的情况 c=1 2) 平方（二次）探测再散列 di = 12, -12, 22, -22, , 3) 随机探测再散列 d

49、i 是一组伪随机数列 或者 di=iH2(key) (又称双散列函数探测),2009-2,计算机与信息学院数据结构,第99页,即：产生的 Hi 均不相同，且所产生的 s(即m-1)个 Hi 值能覆盖哈希表中所有地址。则要求：,注意：增量 di 应具有“完备性”, 随机探测时的 m 和 di 没有公因子。, 平方探测时的表长 m 必为形如 4j+3 的素数（如: 7, 11, 19, 23, 等）；,2009-2,计算机与信息学院数据结构,第100页,例如: 关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 ,设定哈希函数 H(key) = key MOD 11

50、( 表长=11 ),19,01,23,14,55,68,19,01,23,14,68,若采用线性探测再散列处理冲突,若采用二次探测再散列处理冲突,11,82,36,55,11,82,36,1 1 2 1 3 6 2 5 1,ASL=(41+22+6+5+3)/9=22/9,1 1 2 1 2 1 4 1 2,ASL=(51+32+4)/9=15/9,2009-2,计算机与信息学院数据结构,第101页,H2(key) 是另设定的一个哈希函数，它的函数值应和 m 互为素数。,若 m 为素数，则 H2(key) 可以是 1 至 m-1 之间的任意数;若 m 为 2 的幂次，则 H2(key) 应是

51、1 至 m-1 之间的任意奇数。,例如，当 m=11时，可设 di=H2(key)=(3 key) MOD 10+1,19,01,23,14,55,68,11,82,36,2 1 1 1 2 1 2 1 3,双散列函数探测, 19, 01, 23, 14, 55, 68, 11, 82, 36 ,2009-2,计算机与信息学院数据结构,第102页,将所有哈希地址相同的记录都链接在同一链表中。,2. 链地址法,ASL=(61+22+3)/9=13/9,例如:同前例的关键字，哈希函数为 H(key)=key MOD 7, 19, 01, 23, 14, 55, 68, 11, 82, 36 ,2009-2,计算机与信息学院数据结构,第103页,再哈希法：,ii(key) RHi均是不同的哈希函数即：发生冲突时，计算另一个哈希函数地址，直到不再发生冲突为止。,建立一个公共溢出区：,假设哈希函数的值域为，m-1，则建一个基本表HashTable0