数据结构讲义

2023/1/191柳青Email:SchoolofSoftware,YunnanUniversity数据结构(DataStructure)2023/1/1929.1静态查找表9.2动态查找表9.3哈希表

第九章查找2023/1/193查找(Search)的概念

所谓查找，就是在数据集合中寻找满足某种条件的数据元素。查找的结果通常有两种可能：

查找成功，即找到满足条件的数据元素。查找结果可为该元素在结构中的位置，还可进一步给出该元素中的具体信息。

查找不成功，或查找失败。查找结果为一些指示信息，如失败标志、失败位置等。第九章查找2023/1/194第九章查找在每一个元素中有若干属性，其中应当有一个属性，其值可唯一地标识这个元素。它称为关键字(Key)。使用基于关键字的查找，查找结果应是唯一的。实施查找时有两种不同的环境。静态查找表，数据结构在执行查找操作的前后不发生改变。（SST）动态查找表，为保持较高的查找效率，数据结构在执行查找操作时，可同时进行插入和删除等操作，结构可能发生变化。（DST）2023/1/1959.1静态查找表typedefstruct{ElemType*elem;intlength;}SSTable;在静态查找表中，数据元素存放于数组中。查找算法根据给定值x，在数组中进行查找，直到找到x在数组中的存放位置或可确定在数组中找不到x为止。2023/1/1969.1静态查找表所谓顺序查找，又称线性查找，主要用于在线性结构中进行查找。设若表中有n个元素，则顺序查找从表的一端开始，顺序用各元素的关键字与给定值x进行比较，直到找到与其值相等的元素，则查找成功，给出该元素在表中的位置。若整个表都已检测完仍未找到关键字与x相等的元素，则查找失败。给出失败信息。9.1.1顺序表的查找2023/1/197intSearch_Seq(SSTableST,KeyTypekey)//查找成功，返回非0；否则返回0。{ST.elem[0].key=key;//0号单元为监视哨

for(i=ST.length;!EQ(ST.elem[i].key,key);i--);returni;}

顺序查找算法：9.1静态查找表2023/1/1989.1静态查找表衡量一个查找算法的时间效率的标准是：在查找过程中关键字的平均比较次数，这个标准也称为平均查找长度ASL(AverageSearchLength)。通常它是查找元素总数n的函数。另外衡量一个查找算法还要考虑算法所需要的存储量和算法的复杂性等问题。2023/1/199

顺序查找的平均查找长度

设查找第

i

个元素的概率为pi，查找到第

i

个元素所需比较次数为

ci，则查找成功的平均查找长度:

在顺序查找情形，ci=n-i+1,i=1,2,,n，因此

在等概率情形，pi=1/n,

i=1,2,,n。

9.1静态查找表2023/1/19109.1.2

有序表的查找（折半查找）设n个元素存放在一个有序顺序表中，并按其关键字从小到大排好了序。采用折半查找时，先求位于查找区间正中的元素的下标mid，mid=|(low+high)/2」,用其关键字与给定值x比较:elem[mid].key=x，查找成功；elem[mid].key>x，把查找区间缩小到表的前半部分，再继续进行折半查找；elem[mid].key<x，把查找区间缩小到表的后半部分，再继续进行折半查找。每比较一次，查找区间缩小一半。如果查找区间已缩小到一个元素，仍未找到想要查找的元素，则查找失败。9.1静态查找表2023/1/19110513192137566475808892lowmidhigh例Key=21的查找过程：midlowhigh0513192137566475808892midlowhigh05131921375664758088929.1静态查找表12345678910112023/1/19120513192137566475808892lowmidhigh例Key=85的查找过程：midlowhigh0513192137566475808892lowhigh05131921375664758088929.1静态查找表1234567891011midlowhigh05131921375664758088922023/1/19139.1静态查找表折半查找的算法：intSearch_Bin(SSTableST,KeyTypekey){low=1;high=ST.length;while(low<=high){mid=(low+high)/2;ifEQ(ST.elem[mid].key,key) returnmid;elseifLT(key,ST.elem[mid].key) high=mid-1;elselow=mid+1;}return0;}演示2023/1/1914

从有序表构造出的二叉查找树(判定树)

若设n=2h-1，则描述折半查找的二叉查找树是深度为h

的满二叉树。2h=n+1,h=log2(n+1)。第1层结点有1个，查找第1层结点要比较1次；第2层结点有2个，查找第2层结点要比较2次；…。63124597810119.1静态查找表2023/1/1915第i(1

i

h)层结点有2i-1个，查找第i层结点要比较i次，…。假定每个结点的查找概率相等，即pi

=1/n，则查找成功的平均查找长度为：9.1静态查找表2023/1/1916稠密索引：一个索引项对应数据表中一个元素的索引结构。当元素在外存中按加入顺序存放而不是按关键字有序存放时必须采用稠密索引结构，这时的索引结构叫做索引非顺序结构。示例：有一个存放职工信息的数据表，每一个职工对象有近1k字节的信息。

当数据元素个数n很大时，如果用无序表形式的静态查找结构存储，采用顺序查找，则查找效率较低。如果采用有序表存储形式的静态查找结构，则插入新记录进行排序，时间开销也很可观。这时可采用索引方法来实现存储和查找。9.1.3索引顺序表的查找9.1静态查找表2023/1/19172023/1/1918假设内存工作区仅能容纳64k

字节的数据，在某一时刻内存最多可容纳64个元素以供查找。如果元素总数有1024个,不可能把所有元素的数据一次都读入内存。无论是顺序查找或对分查找，都需要多次读取外存记录。如果在索引表中每一个索引项占4个字节,每个索引项索引一个职工对象，则1024个索引项需要4k字节,在内存中可以容纳所有的索引项。这样只需从外存中把索引表读入内存，经过查找索引后确定了职工对象的存储地址，再经过1次读取元素操作就可以完成查找。9.1静态查找表2023/1/1919稀疏索引：把所有n个元素分为b个子表(块)存放，一个索引项对应数据表中一组元素(一个子表)。在子表中,所有元素可能按关键字有序地存放,也可能无序地存放。但所有这些子表必须分块有序，后一个子表中所有元素的关键字均大于前一个子表中所有元素的关键字。它们都存放在数据区中。另外建立一个索引表。索引表由b个索引项组成，第i个索引项记录了子表i中最大关键字max_key以及该子表在数据区中的起始位置obj_addr。各个索引项在索引表中的序号与各个子表的块号有一一对应的关系（第i个索引项是第i个子表的索引项,i=0,1,…,n-1），这样的索引结构叫做索引顺序结构。9.1静态查找表2023/1/19209.1静态查找表2023/1/1921对索引顺序结构进行查找时，一般分为两级查找。

先在索引表ID

中查找给定值K，确定满足

ID[i-1].max_key<K

ID[i].max_key

的i值，即待查元素可能在的子表的序号。然后再在第i个子表中按给定值查找要求的元素。索引表是按max_key有序的，且长度也不大，可以对分查找，也可以顺序查找。9.1静态查找表2023/1/19229.1静态查找表各子表内各个元素如果也按元素关键字有序，可以采用对分查找或顺序查找；如果不是按元素关键字有序，只能顺序查找。索引顺序查找的查找成功时的平均查找长度

ASLIndexSeq=ASLIndex

+ASLSubList其中，ASLIndex

是在索引表中查找子表位置的平均查找长度，ASLSubList是在子表内查找元素位置的查找成功的平均查找长度。2023/1/1923设把长度为n的表分成均等的b个子表，每个子表s个元素，则b=n/s。又设表中每个元素的查找概率相等，则每个子表的查找概率为1/b，子表内各元素的查找概率为1/s。若对索引表和子表都用顺序查找，则索引顺序查找的查找成功时的平均查找长度为

ASLIndexSeq=(b+1)/2+(s+1)/2=(b+s)/2+1索引查找的平均查找长度不仅与表中的元素个数n有关，而且与每个子表中的元素个数s有关。在给定n的情况下，s应选择多大？9.1静态查找表2023/1/19249.1静态查找表利用数学方法可以导出，当s=

时，ASLIndexSeq取极小值+1。这个值比顺序查找强，但比折半查找差。若采用折半查找确定元素所在的子表，则查找成功时的平均查找长度为

ASLIndexSeq=ASLIndex

+ASLSubList

log2(b+1)-1+(s+1)/2

log2(1+n/s)+s/22023/1/1925定义：

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：左子树(如果存在)上所有结点的关键字都小于根结点的关键字。

右子树(如果存在)上所有结点的关键字都大于根结点的关键字。

左子树和右子树也是二叉排序树。特点：

如果对一棵二叉排序树进行中序遍历，可以按从小到大的顺序，将各结点关键字排列起来，所以称为二叉排序树。9.2.1

二叉排序树和平衡二叉树9.2动态查找表一、二叉排序树及其查找过程2023/1/1926二叉排序树上的查找：在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程，也可以是一个非递归的过程。假设想要在二叉排序树中查找关键字为x的元素，查找过程从根结点开始。如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键字进行比较：如果给定值等于根结点的关键字，则查找成功。如果给定值小于根结点的关键字，则继续递归查找根结点的左子树；否则,递归查找根结点的右子树。9.2动态查找表2023/1/1927BiTreeSearchBST(BiTreeT,KeyTypekey){if(!T)||EQ(key,T->data.key)return(T);elseif(LT(key,T->data.key))return(SearchBST(T->lchild,key));elsereturn(SearchBST(T->rchild,key));}BiTreeSearchBST(BiTreeT,KeyTypekey){p=T;//查找成功，返回指向该结点的指针，否则返回NULL。

while(p&&!EQ(key,p->data.key))if(LT(key,p->data.key))p=p->lchild;elsep=p->rchild;return(p);}递归查找算法非递归查找算法9.2动态查找表2023/1/1928二叉排序树的查找分析：BST的平均查找长度与它的形态有关，最好情况下与折半查找的平均查找长度一致，最坏情况下与顺序查找一致。9.2动态查找表2023/1/1929二、二叉排序树的插入为了向二叉排序树中插入一个新元素，必须先使用查找算法检查这个元素是否在树中已经存在。查找成功:

树中已有这个元素，不再插入。查找不成功:

树中原来没有关键字等于给定值的结点，把新元素加到查找操作停止的地方。9.2动态查找表2023/1/1930BiTreeSearchBST(BiTreeT,KeyTypekey,BiTree&pre){//查找成功，返回指向要找的结点的指针，pre指向该结点的父结点；

//否则返回NULL，pre指向查找路径上的最后一个结点。

p=T;pre=NULL;while(p&&!EQ(key,p->data.key){pre=p;if(LT(key,p->data.key))p=p->lchild;elsep=p->rchild;}return(p);}9.2动态查找表修改后的非递归查找算法2023/1/1931StatusInsertBST(BiTree&T,ElemTypee){BiTreepre;if(!SearchBST(T,e.key,pre))//查找不成功

{s=(BiTNpde*)malloc(sizeof(BiTNode));//构造新结点

s->data=e;s->lchild=s->rchild=NULL;if(!pre)T=s;//原树为空时，新结点为根

elseif(LT(e.key,pre->data.key))pre->lchild=s;//新结点为左子结点

elsepre->rchild=s;//新结点为右子结点

return(OK);}return(FALSE);}9.2动态查找表二叉排序树的插入算法2023/1/1932

输入数据序列

{53,78,65,17,87,09,81,45,23}，建立二叉排序树的过程9.2动态查找表2023/1/1933

同样3个数据{1,2,3

}，输入顺序不同，建立起来的二叉排序树的形态也不同。这直接影响到二叉排序树的查找性能。如果输入序列选得不好，会建立起一棵单支树，使得二叉排序树的深度达到最大，这样必然会降低查找性能。

{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}

1231111322233239.2动态查找表2023/1/1934三、二叉排序树的删除

在二叉排序树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会失去。删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。被删结点缺右子树，可以拿它的左子女结点顶替它的位置，再释放它。被删结点缺左子树，可以拿它的右子女结点顶替它的位置，再释放它。被删结点左、右子树都存在，可以在它的右子树中寻找中序下的第一个结点(关键字最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。9.2动态查找表2023/1/19352023/1/1936StatusDeleteBST(BiTree&T,KeyTypekey){BiTreep,f,s,q;p=SearchBST(T,key,f);if(!p)return(FALSE);//不存在待删除结点

if(!p->lchild||!p->rhcild)//待删除结点无左子树或右子树

{q=(p->lchild)?p->lchild:p->rchild;if(!f)T=q;//为根结点

elseif(p==f->lchild)f->lchild=q;elsef->rchild=q;free(p);}9.2动态查找表二叉排序树的删除算法2023/1/1937else//待删除结点存在左、右子树

{q=p;s=p->rchild;//找寻*p右子树中的最左结点*swhile(s->lchild){q=s;//*q为*s的父结点

s=s->lchild;}p->data=s->data;//用*s代替*pif(q==p)p->rchild=s->rchild;elseq->lchild=s->rchild;//*s的右子树为*q的左子树

free(s);}return(TRUE);}9.2动态查找表2023/1/1938四、平衡二叉树（AVL）

1AVL树的定义：一棵AVL（1962年由Adelson,Velskli和Landis提出）树或者是空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是AVL树，且左子树和右子树的深度之差的绝对值不超过1。

深度不平衡的二叉排序树深度平衡的二叉排序树9.2动态查找表2023/1/1939

2结点的平衡因子

(balancefactor)：每个结点附加一个数字，给出该结点右子树的深度减去左子树的深度（或左子树的深度减去右子树的深度）所得的深度差。这个数字即为结点的平衡因子balancefactor。根据AVL树的定义，任一结点的平衡因子只能取-1，0和1。如果一个结点的平衡因子的绝对值大于1，则这棵二叉排序树就失去了平衡，不再是AVL树。如果一棵二叉排序树是深度平衡的，它就成为AVL树。如果它有n个结点，其深度可保持在O(log2n)，平均查找长度也可保持在O(log2n)。9.2动态查找表2023/1/19403平衡化旋转：如果在一棵平衡的二叉排序树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。必须保证平衡化后的二叉树依然是一棵二叉排序树。每插入一个新结点时，AVL树中相关结点的平衡状态会发生改变。因此，在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子(左、右子树的深度差)。如果在某一结点发现深度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。9.2动态查找表2023/1/1941如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转，其中一个是另一个的镜像，其方向与不平衡的形状相关。如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。右单旋转左单旋转

左右双旋转右左双旋转9.2动态查找表2023/1/1942hhhACEBD(a)(b)(c)hhh+1BACEDhhh+1CEABD（1）左单旋转(RR型)：如果在子树E中插入一个新结点，该子树深度增1导致结点A的平衡因子变成+2，出现不平衡。沿插入路径检查三个结点A、C和E。它们处于一条方向为“\”的直线上，需要做左单旋转。以结点C为旋转轴，让结点A反时针旋转。+1+20+1009.2动态查找表2023/1/1943hhhACEBD(a)(b)(c)hh+1BACEDhhh+1CEABD（2）右单旋转(LL型)：在左子树D上插入新结点使其深度增1，导致结点A的平衡因子增到-2，造成了不平衡。为使树恢复平衡，从A沿插入路径连续取3个结点A、B和D，它们处于一条方向为“/”的直线上，需要做右单旋转。以结点B为旋转轴，将结点A顺时针旋转。h000-1-1-29.2动态查找表2023/1/1944（3）先左后右双旋转(LR型)：在下图中子树F或G中插入新结点，该子树的深度增1。结点A的平衡因子变为-2，发生了不平衡。从结点A起沿插入路径选取3个结点A、B和E，它们位于一条形如“”的折线上，因此需要进行先左后右的双旋转。首先以结点E为旋转轴，将结点B反时针旋转，以E代替原来B的位置，做左单旋转。再以结点E为旋转轴，将结点A顺时针旋转，做右单旋转。使之平衡化。9.2动态查找表2023/1/1945插入左单旋转右单旋转00-1-2+1-100+12023/1/1946

（4）先右后左双旋转(RL型)：右左双旋转是左右双旋转的镜像。在下图中子树F或G中插入新结点，该子树深度增1。结点A的平衡因子变为2，发生了不平衡。从结点A起沿插入路径选取3个结点A、C和D，它们位于一条形如“”的折线上，需要进行先右后左的双旋转。首先做右单旋转：以结点D为旋转轴，将结点C顺时针旋转，以D代替原来C的位置。再做左单旋转：以结点D为旋转轴，将结点A反时针旋转，恢复树的平衡。9.2动态查找表2023/1/1947左单旋转插入右单旋转+10000-1-1+1+22023/1/1948161603163-10701-2左右双旋731600073110-117316161190-1-2右单旋3716900013711269161101122例：输入关键字序列{16,3,7,11,9,26,18,14,15}，

建立一棵AVL树。2023/1/1949181803163-101602右左双旋739000182611-1732616119-1左单旋9716140017112626911119.2动态查找表2023/1/19501518231816-2左右双旋73000117149-1161501112626141-29从空树开始的建树过程9.2动态查找表2023/1/1951如右图:用二叉树组织文件，当文件的记录个数为100，000时，要找到给定关键字的记录，需访问外存17次（log2100,000）,太长了！502510751535609020304055708095索引文件数据文件文件头，可常驻内存文件访问示意图：索引文件、数据文件存在盘上

为什么采用B-树和B+树：大量数据存放在外存中，通常存放在硬盘中，要多次访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。用B-树作为索引组织文件，可提高访问速度、减少时间。9.2动态查找表9.2.2B-树和B+树2023/1/1952一、B-树一棵m阶B-树是一棵m路查找树，它或者是空树，或者是满足下列性质的m叉树：根结点不是叶子结点时至少有2棵子树。树中每个结点至多有m棵子树。除根结点以外的所有非叶子结点至少有m/2棵子树。所有非叶子结点的组成为(n,A0,K1,A1,K2,A2,…,Kn,An)，n为关键字个数，Ki为关键字，Ai为指向子树的指针。

Ai-1指向子树的结点的关键字<Ki<Ai指向子树的结点的关键字。所有的叶子结点都位于同一层（可看作是查找失败的结点或外部结点，实际上为空）。一棵m阶B-树是一棵m叉有序平衡树。——B-树及其查找9.2动态查找2023/1/1953

例如：m=4阶B-树。除根结点和叶子结点之外，每个结点的孩子个数 至少为

个；结点的关键字个数至少为1。该B-树的深度为4。 叶子结点都在第4层上。1，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第1层第2层第3层(L层)第4层(L＋1层)9.2动态查找表—B-树2023/1/1954非B-树（至少应有2棵子树）

B-树

非B-树和B-树示例：9.2动态查找表—B-树2023/1/1955#definem3typedefstructBTNode{ //结点定义

int keynum;//结点中关键字个数

structBTNode*parent; //双亲指针

KeyType key[m+1];//关键字数组1m-1structBTNode*ptr[m+1]; //子树指针数组0m};typedefstruct{BTNode *pt; //指向找到的结点

int i; //1..m,在结点中的关键字序号

int tag; //1:查找成功;0:查找失败}Result; //B-树的查找结果类型--B-树的结点类型说明9.2动态查找表2023/1/1956ResultSearchBTree(BtreeT,KeyTypeK){//返回(pt,i,tag)。查找成功，tag=1，pt所指结点中第i个关键字等于K。

//查找失败，则tag=0，K应插到pt所指结点中第i和第i+1个关键字之间。

p=T;q=NULL;found=FALSE;while(p&&!found){for(i=p->keynum,p->key[0]=K;K<p->key[i];i--);//查找i,使p->key[i]<=K<p->key[i+1]if(i>0&&p->key[i]==K)found=TRUE; else{q=p;p=p->ptr[i];}}if(found)return(p,i,1);//查找成功

elsereturn(q,i,0);//查找不成功,返回插入位置}9.2动态查找表–

B-树的查找算法

2023/1/1957

B-树的查找过程是一个在结点内查找和循某一条路径向下一层查找交替进行的过程。在B-树上进行查找，查找成功所需的时间取决于关键字所在的层次，查找不成功所需的时间取决于树的深度。从B-树的定义知,每层关键字个数N最少有：第1层1个结点第2层至少2个结点第3层至少2m/2

个结点第4层至少2m/2

2个结点如此类推，第h

层至少有2m/2

h-2个结点。所有这些结点都不是失败结点。----B-树查找分析9.2动态查找表2023/1/1958若树中关键字有N个,则失败结点数为N+1。这是因为失败一般发生在Ki<x<Ki+1,0i

N，设K0=-，KN+1=+。因此有

N+1=失败结点数=位于第h+1层的结点数

2m/2

h-1

N

2m/2

h-1-1

反之，h

log

m/2

((N+1)/2)+1示例：若B-树的阶数m=199，关键字总数N=1999999，则B-树的深度h不超过

log1001000000+1=4若B-树的阶数m=3，深度h=4，则关键字总数至少为N=23/2

4-1-1=159.2动态查找表2023/1/1959---B-树的插入B-树是从空树起，逐个插入关键字而生成的。插入从某个叶子结点开始。如果在关键字插入后结点中的关键字个数超出了上界m-1，则结点需要“分裂”，否则可以直接插入。实现结点“分裂”的原则是：设结点p中已经有m-1个关键字，当再插入一个关键字后结点中的状态为(m,P0,K1,P1,K2,P2,……,Km,Pm)

其中Ki<Ki+1,1

i<m把结点p分裂成两个结点p和q，它们包含的信息分别为：结点p：(m/2

-1,P0,K1,P1,……,Km/2

-1,Pm/2

-1)结点q：(m

-

m/2,Pm/2,Km/2+1,Pm/2+1,……,Km,Pm)位于中间的关键字Km/2

与指向新结点q的指针形成一个二元组(Km/2,q)，插入到这两个结点的双亲结点中去。9.2动态查找表2023/1/1960结点“分裂”的示例9.2动态查找表2023/1/1961示例：从空树开始逐个加入关键字建立3阶B-树2023/1/1962在插入新关键字时，需要自底向上分裂结点，最坏情况下从被插关键字所在叶结点到根的路径上的所有结点都要分裂。9.2动态查找表2023/1/1963---B-树的删除在B-树上删除一个关键字时，首先需要找到这个关键字所在的结点，从中删去这个关键字。若该结点不是叶子结点，且被删关键字为Ki，1

i

n，则在删去该关键字之后，应以该结点Pi所指示子树中的最小关键字x来代替被删关键字Ki所在的位置，然后在x

所在的叶子结点中删除x。9.2动态查找表2023/1/1964在叶子结点上的删除有以下4种情况：

1）被删关键字所在叶子结点同时又是根结点且删除前该结点中关键字个数n

2，则直接删去该关键字。

2）被删关键字所在叶子结点不是根结点且删除前该结点中关键字个数n

m/2，则直接删去该关键字。9.2动态查找表---B-树的删除2023/1/1965删除55简单删除2023/1/19663）被删关键字所在叶子结点删除前关键字个数n=m/2

-1，若这时与该结点相邻的右兄弟(或左兄弟)

结点的关键字个数n

>m/2，则可按以下步骤调整该结点、右兄弟(或左兄弟)

结点以及其双亲结点，以达到新的平衡。将双亲结点中刚刚大于(或小于)

该被删关键字的关键字Ki(1i

n)下移到被删除的关键字位置；9.2动态查找表2023/1/1967将右兄弟(或左兄弟)

结点中的最小(或最大)关键字上移到双亲结点的Ki位置；将右兄弟(或左兄弟)

结点中的最左(或最右)

子树指针平移到被删关键字所在结点中最后(或最前)

子树指针位置；在右兄弟(或左兄弟)

结点中，将被移走的关键字和指针位置用剩余的关键字和指针填补、调整。再将结点中的关键字个数减1。9.2动态查找表2023/1/1968删除65结点联合调整2023/1/1969删除702023/1/19704）被删关键字所在叶子结点删除前关键字个数n=m/2

-1，若这时与该结点相邻的右兄弟(或左兄弟)

结点的关键字个数n=m/2

-1，则必须按以下步骤合并这两个结点。将双亲结点p中相应关键字下移到选定保留的结点中。若要合并p中的子树指针Pi与Pi+1所指的结点，且保留Pi所指结点，则把p中的关键字Ki+1下移到Pi所指的结点中。9.2动态查找表2023/1/1971把p中子树指针Pi+1所指结点中的全部指针和关键字都照搬到Pi所指结点的后面。删去Pi+1所指的结点。在结点p中用后面剩余的关键字和指针填补关键字Ki+1和指针Pi+1。修改结点

p

和选定保留结点的关键字个数。9.2动态查找表2023/1/1972删除55结点合并2023/1/1973删除80结点合并2023/1/1974非叶结点删除删除50删除552023/1/1975结点合并与调整删除702023/1/1976删除752023/1/1977在合并结点的过程中，双亲结点中的关键字个数减少了。若双亲结点是根结点且结点关键字个数减到0，则该双亲结点应从树上删去，合并后保留的结点成为新的根结点；否则将双亲结点与合并后保留的结点都写回磁盘，删除处理结束。若双亲结点不是根结点，且关键字个数减到m/2

-2，又要与它自己的兄弟结点合并，重复上面的合并步骤。最坏情况下这种结点合并处理要自下向上直到根结点。9.2动态查找表2023/1/1978---B+树B+树可以看作是B-树的一种变形，在实现文件索引结构方面比B-树使用得更普遍。一棵m阶B+树与m阶B-树的主要差别如下：有n棵子树的结点含有n个关键字；所有的叶子结点都处于同一层次上，包含了全部关键字及指向相应数据元素存放地址的指针，且叶子结点本身按关键字从小到大顺序链接；所有的非叶子结点可以看成是索引部分，结点中关键字Ki与指向子树的指针Pi构成其子树(即下一层索引块)的索引项(Ki,Pi

)，Ki是子树中最大的关键字。9.2动态查找表2023/1/1979在B+树中有两个头指针：一个指向B+树的根结点，一个指向关键字最小的叶子结点。可对B+树进行两种查找运算：一种是循叶子结点链的顺序查找，另一种是从根结点开始的随机查找。在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。只是在查找过程中，如果非叶子结点上的关键字等于给定值，查找并不停止，而是继续沿右指针向下，一直查到叶子结点上的这个关键字。B+树的查找分析类似于B_树。9.2动态查找表2023/1/1980本节课后作业

“数据结构题集（C语言版）”

P559.3、P569.11P569.132023/1/1981哈希方法在数据元素的存储位置与它的关键字之间建立一个确定的对应函数关系Hash()，使每个关键字与结构中一个存储位置相对应：

Address

＝Hash(key)在查找时，首先对数据元素的关键字进行函数计算，把函数值当做数据元素的存储位置，在结构中按此位置取数据元素比较。若关键字相等，则查找成功。在存放数据元素时，依相同函数计算存储位置，并按此位置存放。这种方法就是哈希方法。在哈希方法中使用的转换函数叫做哈希函数。而按此种想法构造出来的表或结构就叫做哈希表。使用哈希方法进行查找不必进行多次关键字的比较，查找速度比较快，可以直接到达或逼近具有此关键字的数据元素的实际存放地址。E.g.

电话区号=Hash(城市名)9.3哈希表9.3.1什么是哈希表2023/1/1982哈希函数是一个压缩映象函数。关键字集合比哈希表地址集合大得多。因此有可能经过哈希函数的计算，把不同的关键字映射到同一个哈希地址上，这就产生了冲突

(Collision)。例：有一组数据元素，其关键字分别是12361,07251,03309,30976

采用的哈希函数是hash(x)=x%73+13420

其中，“%”是除法取余操作。则有：hash(12361)=hash(07251)=hash(03309)=hash(30976)=13444。就是说，对不同的关键字，通过哈希函数的计算，得到了同一哈希地址。这些产生冲突的哈希地址相同的不同关键字称为同义词。见P252表9.1由于关键字集合比地址集合大得多，冲突很难避免。所以对于哈希方法，需要讨论以下两个问题：对于给定的一个关键字集合，选择一个计算简单且地址分布比较均匀的哈希函数，避免或尽量减少冲突；拟订解决冲突的方案。9.3哈希表2023/1/1983构造哈希函数时的几点要求：哈希函数的定义域必须包括需要存储的全部关键字，如果哈希表允许有m个地址时,其值域必须在0到m-1之间。哈希函数计算出来的地址应能均匀分布在整个地址空间中：若key

是从关键字集合中随机抽取的一个关键字，哈希函数应能以同等概率取0到m-1中的每一个值。哈希函数应是简单的，能在较短的时间内计算出结果。9.3.2

哈希函数的构造方法9.3哈希表

1.直接定址法此类函数取关键字的某个线性函数值作为哈希地址：

Hash(key)＝a*key+b{a,b为常数}

这类哈希函数是一对一的映射，不会产生冲突。但是，它要求哈希地址空间的大小与关键字集合的大小相同。2023/1/1984

示例：有一组关键字如下：{942148,941269,940527,941630,941805,941558,942047,940001}。哈希函数为

Hash(key)=key

-940000

则有

Hash(942148)=2148Hash(941269)=1269 Hash(940527)=527Hash(941630)=1630 Hash(941805)=1805Hash(941558)=1558 Hash(942047)=2047Hash(940001)=1

可以按计算出的地址存放记录。

2.数字分析法设有n个d位数，每一位可能有r种不同的符号。这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布均匀些；在某些位上分布不均匀，只有某几种符号经常出现。可根据哈希表的大小，选取其中各种符号分布均匀的若干位作为哈希地址。9.3哈希表2023/1/1985示例：若哈希表地址范围有3位数字,取各关键字的④⑤⑥位做为记录的哈希地址。也可以把第①，②，③和第⑤位相加，舍去进位位，变成一位数，与第④，⑥位合起来作为哈希地址。还有其它方法。 ①②③④⑤⑥

942148 941269 940527 941630 941805 941558 942047 940001 数字分析法仅适用于事先明确知道表中所有关键字每一位数值的分布情况，它完全依赖于关键字集合。如果换一个关键字集合，选择哪几位要重新决定。9.3哈希表2023/1/1986

3.除留余数法设哈希表的地址范围是0到m-1,取一个不大于m，但最接近于或等于m的质数p,利用以下公式把关键字转换成哈希地址。哈希函数为：

hash(key)=key%p p

m示例：有一个关键字key=962148，哈希表大小m=25，即HT[25]。取质数p=23。哈希函数hash(key)=key%p。则哈希地址为

hash(962148)=962148%23=12。可以按计算出的地址存放记录。需要注意的是，使用上面的哈希函数计算出来的地址范围是0到22，因此，从23到24这几个哈希地址实际上在一开始是不可能用哈希函数计算出来的，只可能在处理溢出时达到这些地址。9.3哈希表2023/1/1987

4.乘余取整法使用此方法时，先让关键字key乘上一个常数A(0<A<1)，提取乘积的小数部分。然后，再用整数m乘以这个值，对结果向下取整，把它做为哈希的地址。哈希函数为：

hash(key)=

m*(A*key

-

A*key

)

其中,“A*key

-

A*key

”表示取A*key的小数部分。示例：设关键字key=123456，m=10000，且A=0.6180339，则

hash(123456)==10000*(0.6180339*123456-0.6180339*123456)=10000*(76300.0041151-76300)=10000*0.0041151

=41.151=41哈希表的地址范围是0到m-1。9.3哈希表2023/1/19885.平方取中法先计算构成关键字的标识符的内码的平方，然后按照哈希表的大小取中间的若干位作为哈希地址。设标识符可以用一个计算机字长的内码表示。因为内码平方数的中间几位一般是由标识符所有字符决定，所以对不同的标识符计算出的哈希地址大多不相同，例标识符的八进制内码表示及其平方值。 标识符内码 内码的平方哈希地址 A 01 01 001 A1 0134 20420 042 A9 0144 23420 342 B 02 04 004 DMAX04150130 21526443617100 443 DMAX1 5264473522151420 352 AMAX01150130 135423617100 236 AMAX1 3454246522151420 6529.3哈希表2023/1/19896.折叠法此方法把关键字自左到右分成位数相等的几部分，每一部分的位数应与哈希表地址位数相同，只有最后一部分的位数可以短一些。把这些部分的数据叠加起来，就可以得到具有该关键字的记录的哈希地址。有两种叠加方法：

移位法

—

把各部分的最后一位对齐相加；

分界法

—

各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做哈希地址示例：设给定的关键字为key=23938587841，若存储空间限定3位,则划分结果为每段3位.上述关键字可划分为4段：

239

385

878

419.3哈希表2023/1/1990把超出地址位数的最高位删去,仅保留最低的3位，做为可用的哈希地址。一般当关键字的位数很多，而且关键字每一位上数字的分布大致比较均匀时，可用这种方法得到哈希地址。9.3哈希表2023/1/19919.3.3处理冲突的方法

解决冲突的方法又称为溢出处理技术。因为绝大多数哈希函数不能避免产生冲突，因此选择好的解决冲突的方法十分重要。9.3哈希表1开放地址法若设哈希表中的地址为0到m-1，当要加入一个数据元素R2时,用它的关键字R2.key，通过哈希函数hash(R2.key)的计算，得到它的存放位置j，但是在存放时发现这个位置已经被另一个数据元素R1占据了。这时不但发生了冲突，还必须处理溢出。为此，必须把R2存放到表中“下一个”空位置中。如果表未满，则在允许的范围内必定还有空位置。2023/1/1992(1)线性探测法(LinearProbing)9.3哈希表需要查找或加入一个数据元素时，使用哈希函数计算位置号：

H0=hash(key)一旦发生冲突，在表中顺次向后寻找“下一个”空位置Hi的公式为：

Hi

=(Hi-1+1)%m，i=1,2,…,m-1

即用以下的线性探测序列在表中寻找“下一个”空位置：

H0+1,H0+2,…,m-1,0,1,2,…,H0-1

亦可写成Hi=(H0

+di)%m，di

=1,2,…,m-1

其中H0=hash(key)称为Hash函数,m称为Hash表长;当发生冲突时,探查下一个位置。当循环m-1次后就会回到开始探查时的位置,说明待查关键字不在表内,而且表已满,不能再插入新关键字。2023/1/19939.3哈希表假设一组数据元素的关键字为(19,14,23,01,68,20,84,27,55,11,10,79)。哈希表为HT[16]，哈希函数为Hash(key)=key%13，采用线性探查法处理冲突，则上述关键字在哈希表中的存储位置如下图所示，其中HT上面的数字表示关键字找到空位置所需要的探查次数，平均查找长度=探查次数之和/元素个数，即30/12=2.5HT线性探查方法容易产生“堆积”，即在处理冲突过程中发生的两个第一个哈希地址不同的元素争夺同一个后续地址的现象，显然这将会导致查找时间增加。2023/1/1994(2)二次探测法(quadraticprobing)为改善“堆积”问题，减少为完成查找所需的平均探查次数，可使用二次探查法。令哈希函数为：

H0=hash(x)二次探查法在表中寻找“下一个”空位置的公式为：

Hi=(H0

+di)%m，di

=12,-12,22,-22,…,k2,-k2式中的m是表的大小，当m是一个值为4k+3

（k是整数）的质数时，采用二次探查法的Hi才能找到哈希表的每一个位置。在做(H0+

di)%m的运算时，H0+

di

可能为负数，因此实际算式可改为：

if((H0+di)<0)j=(H0

+di+m)%m9.3哈希表2023/1/1995假设一组数据元素的关键字为(19,14,23,01,68,20,84,27,55,11,10)。哈希表为HT[11]，采用的哈希函数是：

Hash(key)=key%11

采用二次探查法处理溢出，则上述关键字在哈希表中哈希位置如图所示，HT上面的数字表示关键字找到空位置所需要的比较次数。9.3哈希表HT其中，求关键字10的存储位置的过程为：

H0=10%11=10; (10+1)%11=0;(10-1)%11=9;(10+4)%11=3; (10-4)%11=6;(10+9)%11=8;(10-9)%11=1;······

平均查找长度22/11=22023/1/19962链地址法采用链地址法解决冲突时，首先对关键字集合用某一个哈希函数计算它们的存放位置。若设哈希表地址空间的所有位置是从0到m-1，则关键字集合中的所有关键字被划分为m个子集，具有相同地址的关键字归于同一子集。同一子集中的关键字互称为同义词。通常关键字互为同义词的数据元素通过一个单链表链接起来，称之为同义词子表。所有关键字互为同义词的数据元素都链接在同一个同义词子表中，各链表的表头结点组成一个向量。向量的元素个数与地址空间的位置数一致。向量中的第i个元素中存放哈希函数为i的同义词子表的头指针。9.3哈希表2023/1/19979.3哈希表假设一组数据元素的关键字为(19,14,23,01,68,20,84,27,55,11,10,79)。哈希表为HT[13]，采用的哈希函数是：

Hash(key)=key%13采用链地址法