数据结构(第九章 查找)

数据结构第9章查找基本概念——若表中存在特定元素，称查找成功，应输出该记录；——否则，称查找不成功（也应输出失败标志或失败位置）查找表查找查找成功查找不成功静态查找动态查找关键字主关键字次关键字——由同一类型的数据元素（或记录）构成的集合。——查询(Searching)特定元素是否在表中。——只查找，不改变集合内的数据元素。——既查找，又改变（增减）集合内的数据元素。——记录中某个数据项的值，可用来识别一个记录

(预先确定的记录的某种标志)——可以唯一标识一个记录的关键字例如“学号”例如“女”是一种数据结构——识别若干记录的关键字基本概念（2）对查找表常用的操作有哪些？查询某个“特定的”数据元素是否在表中；查询某个“特定的”数据元素的各种属性；在查找表中插入一元素；从查找表中删除一元素。

（3）

有哪些查找方法？讨论：（1）查找的过程是怎样的？

给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。例如查字典“特定的”=关键字

查找的基本方法可以分为两大类，即比较式查找法和计算式查找法。其中比较式查找法又可以分为静态查找表和动态查找表，而计算式查找法也称为HASH（哈希）查找法。静态查找表：只作前两种操作。动态查找表：查找过程中同时插入不存在或删除已存在的某个元素。基本概念（4）如何评估查找方法的优劣？明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（ASL：averagesearchlength）。其中：n是文件记录个数；Pi是查找第i个记录的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i个记录时所经历的比较次数。统计意义上的数学期望值物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。显然，ASL值越小，时间效率越高。主要内容9.1静态查找表9.2动态查找表9.3哈希表9.1静态查找表静态查找表的抽象数据类型抽象数据类型静态查找表的定义:ADTStaticSearchTable{D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。数据关系R：数据元素同属一个集合。数据对象D:Create(&ST,n); //构造一个含n个数据元素的静态查找表ST。

Destroy(&ST); //销毁表ST。

Search(ST,key);//查找ST中其关键字等于key的数据元素。

Traverse(ST,Visit());//按某种次序对ST的每个元素调用函数 Visit()一次且仅一次。}ADTStaticSearchTable基本操作P：针对静态查找表的查找算法主要有：

一、顺序查找（线性查找）二、折半查找（二分或对分查找）三、静态树表的查找四、分块查找（索引顺序查找）9.1静态查找表顺序表的机内存储结构：typedefstruct{ElemType*elem;//表基址，0号单元留空。表容量为全部元素

intlength;//表长，即表中数据元素个数}SSTable;顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。对顺序结构如何线性查找？对单链表结构如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针head就可以“顺藤摸瓜”；对非线性树结构如何顺序查找?可借助各种遍历操作！9.1静态查找表顺序查找以顺序表表示静态查找表，则Search函数可用顺序查找来实现。其顺序存储结构如下：i01234567891011

513192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。例如：9.1静态查找表顺序查找9.1静态查找表顺序查找算法的实现：技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。例：若将待查找的特定值key存入顺序表的首部（如0号单元），则顺序查找的实现方案为：从后向前逐个比较！intSearch_Seq(SSTableST,KeyTypekey){//在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0ST.elem[0].key=key;//设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当n>1000时，查找时间将减少一半。

for(i=ST.length;ST.elem[i].key!=key;--i);

//不要用for(i=n;i>0;--i)或for(i=1;i<=n;i++)returni;//若到达0号单元才结束循环，说明不成功，返回0值(i=0)。成功时则返回找到的那个元素的位置i。}//Search_Seq时间复杂度为O(ST.length)9.1静态查找表顺序查找顺序查找性能分析查找算法的平均查找长度(AverageSearchLength)：

为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。其中:n为表长

Pi

为查找表中第i个记录的概率

Ci为找到该记录时，曾和给定值比较过的 关键字的个数9.1静态查找表顺序查找顺序表查找的平均查找长度为：对顺序表而言，Ci=n-i+1ASL=nP1+(n-1)P2++2Pn-1+Pn在等概率查找的情况下，9.1静态查找表顺序查找在不等概率查找的情况下，ASLss在

Pn≥Pn-1≥···≥P2≥P1时取极小值。表中记录按查找概率由小到达重新排列,以提高查找效率。

若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。9.1静态查找表折半查找顺序表的查找算法简单，但平均查找长度较大，不适用于表长较大的查找表。若以有序表表示静态查找表，则查找过程可以基于“折半”进行。有序表的查找折半查找查找过程：每次将待查记录所在区间缩小一半。适用条件：采用顺序存储结构的有序表。1.设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。2.初始时，令

low=1,high=n,mid=(low+high)/2

让k与mid指向的记录比较

若k==r[mid].key，查找成功

若k<r[mid].key，则high=mid-1

若k>r[mid].key，则low=mid+1

3.重复上述操作，直至low>high时，查找失败。9.1静态查找表折半查找折半查找算法实现9.1静态查找表折半查找lowhighmid例1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid例如key=21的查找过程low

指示查找区间的下界;high

指示查找区间的上界;mid=(low+high)/2。例key=70的查找过程1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid9.1静态查找表折半查找1234567891011513192137566475808892lowhigh当下界low大于上界high时，则说明表中没有关键字等于Key的元素，查找不成功。9.1静态查找表折半查找intcount=0;//记录查找次数intSearch_Bin(SSTableST,KeyTypekval){//在顺序表ST中顺序查找其关键字等于key的数据元素

intlow=1,mid,high=ST.length;//置区间初值

while(low<=high) {count++; mid=(low+high)/2;if(kval==ST.elem[mid].key)returnmid;//若找到，则函数值为该元素在表中的位置

elseif(kval<ST.elem[mid].key)high=mid-1;//继续在前半区间进行查找

elselow=mid+1;//继续在后半区间进行查找

}return0;//找不到时，i为0}折半查找算法9.1静态查找表折半查找折半查找的时间效率为O(log2n)先看一个有11个元素的表的例子：n=116391425781011i1234567891011Ci12233334444折半查找的性能分析判定树：描述查找过程的二叉树。有n个结点的判定树的深度为log2n+1折半查找法在查找过程中进行的比较次数最多不超过log2n+19.1静态查找表折半查找9.1静态查找表折半查找假设有序表的长度n=2h-1,（h=log2(n+1））,则描述折半查找的判定树是深度为h的满二叉树。树中层次为1的结点有1个，层次为2的结点有2个，层次为h的结点有2h-1个。假设表中每个记录的查找概率相等则查找成功时折半查找的平均查找长度9.1静态查找表静态树表的查找静态最优查找树算法——时间代价高；实用算法：近似最优查找树（次优查找树）（参见教材P222—225）9.1静态查找表索引顺序表的查找顺序表有序表表的特性无序有序存储结构顺序或链式顺序插删操作易于进行需移动元素ASL的值大小顺序表和有序表的比较9.1静态查找表索引顺序表的查找索引顺序表在建立顺序表的同时，建立一个索引项，包括两项：关键字项和指针项。索引表按关键字有序，表则为分块有序索引表……131211109876543210……7810405210索引顺序表=索引+顺序表顺序表……46786152402522333114192108179.1静态查找表索引顺序表的查找索引顺序查找 又称分块查找查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找适用条件：分块有序表算法实现：用数组存放待查记录,每个数据元素至少含有关键字域建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针12345678910111213141516171822121389203342443824486058745786532248861713索引表查38例如9.1静态查找表索引顺序表的查找9.1静态查找表索引顺序表的查找分块查找方法评价9.1静态查找表查找方法比较ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表顺序查找折半查找

分块查找9.2动态查找表动态查找表的特点:表结构本身是在查找过程中动态生成。若表中存在其关键字等于给定值key的记录,表明查找成功；否则插入关键字等于key的记录。InitDSTable(&DT)//构造一个空的动态查找表DT。DestroyDSTable(&DT)//销毁动态查找表DT。SearchDSTable(DT,key);//查找DT中与关键字key等值的元素。InsertDSTable(&DT,e);//若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。DeleteDSTable(&T,key);//删除DT中关键字等于key的数据元素。TraverseDSTable(DT,Visit());//按某种次序对DT的每个结点调用函数Visit()一次且至多一次。基本操作：}ADTDynamicSearchTableD是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。ADTDynamicSearchTable{数据对象D：数据关系R：数据元素同属一个集合。抽象数据类型动态查找表的定义：9.2动态查找表9.2动态查找表(n)(1)(n)(1)(nlogn)几种查找表的特性查找插入删除无序顺序表无序线性链表有序顺序表有序线性链表静态查找树表(n)(n)(logn)(n)(logn)(1)(1)(n)(1)(nlogn)从查找性能看，最好情况能达(logn)，此时要求表有序；从插入和删除的性能看，最好情况能达(1)，此时要求存储结构是链表。结论：一、二叉排序树二、平衡二叉树三、B树四、B+树9.2动态查找表9.2动态查找表二叉排序树又称二叉查找树（BinarySortTree）定义二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：若它的左子树不空，则左子树上所有结点的值均小于根结点的值；若它的右子树不空，则右子树上所有结点的值均大于根结点的值；它的左、右子树也都分别是二叉排序树。二叉排序树9.2动态查找表二叉排序树503080209010854035252388例如:是二叉排序树。66不9.2动态查找表二叉排序树通常，取二叉链表作为二叉排序树的存储结构typedefstructBiTNode{//结点结构

TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;9.2动态查找表二叉排序树1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左子树上进行查找；3）若给定值大于根结点的关键字，则继续在右子树上进行查找。否则若二叉排序树为空，则查找不成功；二叉排序树的查找算法：9.2动态查找表二叉排序树50308020908540358832例如:二叉排序树查找关键字==50,505035,503040355090,50809095,9.2动态查找表二叉排序树从上述查找过程可见，在查找过程中，生成了一条查找路径:

从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;或者

从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。

——查找成功

——查找不成功9.2动态查找表二叉排序树算法描述如下：StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){//在根指针T所指二叉排序树中递归地查找其

//关键字等于key的数据元素，若查找成功，

//则返回指针p指向该数据元素的结点，并返回

//函数值为TRUE;}//SearchBST

…………否则表明查找不成功，返回

//指针p指向查找路径上访问的最后一个结点，

//并返回函数值为FALSE,指针f指向当前访问

//的结点的双亲，其初始调用值为NULL9.2动态查找表二叉排序树if(!T)elseif(EQ(key,T->data.key))

elseif(LT(key,T->data.key))

else{p=f;returnFALSE;}//查找不成功{p=T;returnTRUE;}//查找成功SearchBST(T->lchild,key,T,p);//在左子树中继续查找SearchBST(T->rchild,key,T,p);//在右子树中继续查找9.2动态查找表二叉排序树T设key=48fTfT22pTfTTTTfffp302010403525239.2动态查找表二叉排序树根据动态查找表的定义，“插入”操作在查找不成功时才进行;若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。二叉排序树的插入算法9.2动态查找表二叉排序树intInsertBST(BiTree&T,ElemTypee){ if(!SearchBST(T,e.key,NULL,p)) {s=newBiTNode;//为新结点分配空间

s->data=e; s->lchild=s->rchild=NULL; if(!p)T=s;//插入s为新的根结点

elseif(e.key<p->data.key) p->lchild=s;//插入*s为*p的左孩子

elsep->rchild=s;//插入*s为*p的右孩子

return1;//插入成功

}elsereturn0;}//InsertBST50308020908540358832505050304035505080909.2动态查找表二叉排序树一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列每次插入的新结点都是二叉排序树上新的叶子结点插入时不必移动其它结点，仅需修改某个结点的指针结论9.2动态查找表二叉排序树二叉排序树的删除算法

和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。可分三种情况讨论：被删除的结点是叶子；被删除的结点只有左子树或者只有右子树；被删除的结点既有左子树，也有右子树。9.2动态查找表二叉排序树50308020908540358832（1）被删除的结点是叶子结点例如:被删关键字=2088其双亲结点中相应指针域的值改为“空”9.2动态查找表二叉排序树50308020908540358832（2）被删除的结点只有左子树或者只有右子树

其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。被删关键字=40809.2动态查找表二叉排序树50308020908540358832（3）被删除的结点既有左子树，也有右子树4040以其（中序遍历）前驱替代之，然后再删除该前驱结点被删结点前驱结点被删关键字=509.2动态查找表二叉排序树StatusDeleteBST(BiTree&T,KeyTypekey){//若二叉排序树T中存在其关键字等于key的

//数据元素，则删除该数据元素结点，并返回

//函数值TRUE，否则返回函数值FALSEif(!T)returnFALSE; //不存在关键字等于key的数据元素

else{}}//DeleteBST算法描述如下：……见下页9.2动态查找表二叉排序树if(EQ(key,T->data.key)) //找到关键字等于key的数据元素elseif(LT(key,T->data.key))

else{Delete(T);returnTRUE;} DeleteBST(T->lchild,key);//继续在左子树中进行查找DeleteBST(T->rchild,key);//继续在右子树中进行查找上页else{}中内容9.2动态查找表二叉排序树voidDelete(BiTree&p){//从二叉排序树中删除结点p，

//并重接它的左子树或右子树

if(!p->rchild){}elseif(!p->lchild){}else{}}//Delete其中删除操作过程如下所描述：………………p//右子树为空树则只需重接它的左子树q=p;p=p->lchild;delete(q);pqq9.2动态查找表二叉排序树9.2动态查找表二叉排序树//左子树为空树只需重接它的右子树q=p;p=p->rchild;delete(q);ppqq9.2动态查找表二叉排序树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;elseq->lchild=s->lchild;//重接*q的左子树delete(s);9.2动态查找表二叉排序树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;//重接*q的右子树

elseq->lchild=s->lchild;//重接*q的左子树delete(s);PCpFPRfCLQSLQLSqsfCpFPRSCLQQLSLqfLpFPRPCLqsfpFPRLCLq9.2动态查找表二叉排序树二叉排序树查找性能的分析

对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL值，显然，由值相同的n个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。9.2动态查找表二叉排序树由关键字序列3，1，2，5，4构造而得的二叉排序树由关键字序列1，2，3，4，5构造而得的二叉排序树，例如：2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.29.2动态查找表平衡二叉树平衡二叉树又称AVL树，是具有如下性质的二叉树：

为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子balance。这样，可以得到AVL树的其它性质：即|左子树深度-右子树深度|≤1左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值≤1任一结点的平衡因子只能取：-1、0或1；如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树；对于一棵有n个结点的AVL树，其高度保持在O(log2n)数量级，ASL也保持在O(log2n)量级。9.2动态查找表平衡二叉树(a)平衡树(b)不平衡树例：判断下列二叉树是否AVL树？00011-1-120001-19.2动态查找表平衡二叉树如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。现分别介绍这四种平衡旋转。平衡旋转可以归纳为四类：

LL平衡旋转

RR平衡旋转

LR平衡旋转

RL平衡旋转9.2动态查找表平衡二叉树若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。(以B为旋转轴）ABCABC1）LL平衡旋转：9.2动态查找表平衡二叉树

在一般二叉排序树的结点中增加一个存放平衡因子的域bf，就可以用来表示平衡二叉排序树。在下面的讨论中，我们约定：用来表示结点的字母，同时也用来表示指向该结点的指针。因此，LL型失衡的特点是：A->bf=2，B->bf=1。相应调整操作可用如下语句完成：B=A->lchild；

A->lchild=B->rchild；

B->rchild=A；

A->bf=0；B->bf=0；9.2动态查找表平衡二叉树

最后，将调整后二叉树的根结点B“接到”原A处。令A原来的父指针为FA，如果FA非空，则用B代替A做FA的左子或右子；否则原来A就是根结点，此时应令根指针t指向B：if(FA==NULL)t=B;elseif(A==FA->lchild)FA->lchild=B;elseFA->rchild=B；ABC9.2动态查找表平衡二叉树若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。(以B为旋转轴）2）RR平衡旋转：ABCABCRR型失衡的特点是：A->bf=-2，B->bf=-1。相应调整操作可用如下语句完成：B=A->rchild；A->rchild=B->lchild；B->lchild=A；A->bf=0；B->bf=0；9.2动态查找表平衡二叉树9.2动态查找表平衡二叉树

最后，将调整后二叉树的根结点B“接到”原A处。令A原来的父指针为FA，如果FA非空，则用B代替A做FA的左子或右子；否则，原来A就是根结点，此时应令根指针t指向B：if(FA==NULL)t=B;elseif(A==FA->lchild)FA->lchild=B;elseFA->rchild=B；ABC9.2动态查找表平衡二叉树若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。(以插入的结点C为旋转轴）ABCABCABC3）LR平衡旋转：9.2动态查找表平衡二叉树LR型失衡的特点是：A->bf=2，B->bf=-1。相应调整操作可用如下语句完成：B=A->lchild；C=B->rchild；B->rchild=C->lchild；A->lchild=C->rchild；C->lchild=B；C->rchild=A；9.2动态查找表平衡二叉树然后针对上述三种不同情况，修改A、B、C的平衡因子：if(S->key<C->key)/*在CL下插入S*/{A->bf=-1；B->bf=0；C->bf=0；}if(S->key>C->key)/*在CR下插入S*/{A->bf=0；B->bf=1；C->bf=0；}if(S->key==C->key)/*C本身就是插入的新结点S*/{A->bf=0；B->bf=0；}9.2动态查找表平衡二叉树

最后，将调整后的二叉树的根结点C“接到”原A处。令A原来的父指针为FA，如果FA非空，则用C代替A做FA的左子或右子；否则，原来A就是根结点，此时应令根指针t指向C：if(FA==NULL)t=C;elseif(A==FA->lchild)FA->lchild=C;elseFA->rchild=C；ABC9.2动态查找表平衡二叉树若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。(以插入的结点C为旋转轴）4）RL平衡旋转：ABCABCABC9.2动态查找表平衡二叉树RL型失衡的特点是：A->bf=-2，B->bf=1。相应调整操作可用如下语句完成：B=A->rchild；C=B->lchild；B->lchild=C->rchild；A->rchild=C->lchild；C->lchild=A；C->rchild=B；然后针对上述三种不同情况，修改A、B、C的平衡因子：if(S->key<C->key)/*在CL下插入S*/{A->bf=0；B->bf=-1；C->bf=0；}if(S->key>C->key)/*在CR下插入S*/{A->bf=1；B->bf=0；C->bf=0；}if(S->key==C->key)/*C本身就是插入的新结点S*/{A->bf=0；B->bf=0；}9.2动态查找表平衡二叉树

最后，将调整后的二叉树的根结点C“接到”原A处。令A原来的父指针为FA，如果FA非空，则用C代替A做FA的左子或右子；否则，原来A就是根结点，此时应令根指针t指向C：

if(FA==NULL)t=C;elseif(A==FA->lchild)FA->lchild=C;elseFA->rchild=C；ABC9.2动态查找表平衡二叉树

综上所述，在一个平衡二叉排序树上插入一个新结点S时，主要包括以下三步：（1）查找应插位置，同时记录离插入位置最近的可能失衡结点A（A的平衡因子不等于0）。（2）插入新结点S，并修改从A到S路径上各结点的平衡因子。（3）根据A、B的平衡因子，判断是否失衡以及失衡类型，并做相应处理。9.2动态查找表平衡二叉树9.2动态查找表平衡二叉树013037024例：请将下面序列构成一棵平衡二叉排序树：

（13，24，37，90，53）013037-113024-124-213需要RR平衡旋转(绕B逆转,B为根）090-124-137053190-237需要RL平衡旋转(绕C先顺后逆）037090053037090053

9.2动态查找表B树B树的定义

空树或m叉树每个结点至多有m棵子树，如根结点不是叶，至少有两棵子树，除根之外，所有非终端结点至少有m/2棵子树。所有的非终端结点含有信息

(n,A0,K1,A1,K2,······,Kn,An)5)所有叶结点都在同一层次，叫做失败结点。9.2动态查找表B树所有的非终端结点含有信息n:有n+1棵子树，K1≤K2≤······≤Kn关键字有序序列,指针Ai指向子树中结点的关键字小于Ki,

nA0K1A1K2·····KnAn9.2动态查找表B树

1·35·1·18·2·43·78·1·11·1·27·1·39·1·99·3·47·53·FFFFFFFFFFF

在B树中的“失败”结点(F)是当搜索值x不在树中时才能到达的结点。

根据m阶B_树的定义，结点的类型定义如下：#defineM5/*根据实际需要定义B_树的阶数*/typedefstructBTNode{intkeynum;/*结点中关键字的个数*/structBTNode*parent;/*指向父结点的指针*/KeyTypekey[M+1];/*关键字向量,key[0]未用*/structBTNode*ptr[M+1];/*子树指针向量*/RecType*recptr[M+1];/*记录指针向量,recptr[0]未用*/}BTNode;9.2动态查找表B树9.2动态查找表B树1·35·1·18·2·43·78·1·11·1·27·1·39·1·99·3·47·53·FFFFFFFFFFFB树的搜索过程检索结点53B树的搜索过程是一个在结点内搜索和循某一条路径向下一层搜索交替进行的过程。9.2动态查找表B树30一棵B树是平衡的m

路搜索树，但一棵平衡的m

路搜索树不一定是B树。352040253010154550root4550354020root101525非B树 B树9.2动态查找表B树设在m阶B树中每层结点个数达到最少,则B树的高度可能达到最大。设树中关键字个数为N，从B树的定义知：

1层1个结点

2层至少2个结点

3层至少2m/2

个结点

4层至少2m/2

2个结点如此类推，

h

层至少有2m/2

h-2个结点。所有这些结点都不是失败结点。h+1层至少有2m/2

h-1

个结点。这一层是叶子结点，不是失败结点。高度h与关键字个数N之间的关系9.2动态查找表B树若树中关键码有N个,则失败结点数为N+1。这是因为失败数据一般与已有关键码交错排列。因此，有

N

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

2m/2

h-1

N2m/2

h-1-1

h-1log

m/2

((N

+1)/2)

hlog

m/2

((N

+1)/2)+1所有的非失败结点所在层次为1h。示例：若B树的阶数m=199,关键码总数N=1999999，则B树的高度h不超过

log1001000000+1=4查找的比较次数与树的深度有关9.2动态查找表B树m值的选择如果提高B树的阶数

m,可以减少树的高度,从而减少读入结点的次数,因而可减少读磁盘的次数。事实上，m

受到内存可使用空间的限制。当m很大超出内存工作区容量时,结点不能一次读入到内存,增加了读盘次数,也增加了结点内搜索的难度。B树的插入B树是从空树起,逐个插入关键码而生成的。在B树，每个非失败结点的关键码个数都在

[m/2-1,m-1]

之间。插入在某个叶结点开始。如果在关键码插入后结点中的关键码个数超出了上界m-1，则结点需要“分裂”，否则可以直接插入。9.2动态查找表B树实现结点“分裂”的原则是：设结点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)，插入到这两个结点的双亲结点中去。见教材242页例9.2动态查找表B树fhmb(a)一棵2-3树fhmbd(b)插入d后fhmpbd分裂(c)插入p后并进行分裂hfmbdphlfmbdp(d)插入l后分裂ghlfmbdp(e)插入g后并进行分裂lfhmbdpp分裂在3阶B树中进行插入的过程lfhmbdpglbdpghfm(f)继续进行分裂9.2动态查找表B树9.2动态查找表B树B树的删除先找到这个关键码所在的结点,从中删去这个关键码。若该结点是最下层非终端结点,且关键字数目不小于m/2

，删除完成若该结点不是最下层非终端结点,且被删关键码为Ki,1in,则在删去该关键码之后,应以该结点Pi所指示子树中的最小关键码x来代替被删关键码Ki所在的位置,然后在x

所在的结点中删除x。例：教材245页图9.17(a)删除53简单删除58758010406560703050acbdefgh5558删除557580m=3删除5510406560703050acbdefgh9.2动态查找表B树9.2动态查找表B树删除最下层非终端结点中的关键字的情形：⑴若结点N中的关键字个数>m/2-1：在结点中直接删除关键字K，如后图(b)∽(c)所示。⑵若结点N中的关键字个数=m/2-1：若结点N的左(右)兄弟结点中的关键字个数>m/2-1，则将结点N的左(或右)兄弟结点中的最大(或最小)关键字上移到其父结点中，而父结点中大于(或小于)且紧靠上移关键字的关键字下移到结点N，如后图(a)。⑶若结点N和其兄弟结点中的关键字数=m/2-1：删除结点N中的关键字，再将结点N中的关键字、指针与其兄弟结点以及分割二者的父结点中的某个关键字Ki，合并为一个结点，若因此使父结点中的关键字个数<m/2-1，则依此类推，如后图(d)。在B_树中进行删除的过程删除qlmbdqeghfplbdpeghfm删除h(a)删除elbdpegfmlbpegfm删除dlpgmbf(b)(c)(d)9.2动态查找表B树9.2动态查找表B+树B-树的变形根结点(非叶时)至少有两个结点除根外，非叶结点至少有[m/2]棵子树,最多有m棵子树,非叶结点都是索引，含有子树中的最大或最小关键字含有n个关键字的非叶结点有n棵子树所有的叶子结点都在同一个层次上，叶子结点中包含全部关键字，以及指向这些关键字的指针所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字9.2动态查找表B+树59971544597297101521374451598591976372根叶B+树两种查找：从根开始，从叶起始9.2动态查找表B+树B树(上图)与B+树（下图）比较B树与B+树的随机查找、插入、删除的过程基本上与B树类似。只是在查找时，若非终端结点的关键字等于给定值，并不终止，而是继续向下直到叶子结点。9.3哈希表哈希表的相关定义哈希查找:又叫散列查找，利用哈希函数进行查找的过程。基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。哈希函数:在记录的关键字与记录的存储地址之间建立的一种对应关系。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。 可写成，addr(ai)=H(ki)

其中：ai是表中的一个元素

addr(ai)是ai的存储地址

ki是ai的关键字9.3哈希表哈希表的相关定义哈希表根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。9.3哈希表哈希表的相关定义98例30个地区的各民族人口统计表编号地区总人口汉族回族…1北京2上海…...…...以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区名作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=199.3哈希表哈希表的相关定义从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。冲突：key1key2，但H(key1)=H(key2)的现象9.3哈希表哈希函数构造的方法哈希函数构造的方法直接定址法数字分析法平方取中法折叠法除留余数法随机数法9.3哈希表哈希函数构造的方法哈希函数为关键字的线性函数

H(key)=key或者H(key)=akey+b此法仅适合于：地址集合的大小==关键字集合的大小其中a和b为常数直接定址法优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突.缺点：要占用连续地址空间，空间效率低。

例：关键码集合为{100，300，500，700，800，900}，选取哈希函数为Hash(key)=key/100，则存储结构（哈希表）如下：01234567899008007005003001009.3哈希表哈希函数构造的方法数字分析法

假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。此法适于能预先估计出全体关键字的每一位上各种数字出现的频度。例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址9.3哈希表哈希函数构造的方法9.3哈希表哈希函数构造的方法

以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。此方法适合于:

关键字中的每一位都有某些数字重复出现频度很高的现象。平方取中法9.3哈希表哈希函数构造的方法将关键字分割成若干部分，然后取它们的叠加和为哈希地址。两种叠加处理的方法：移位叠加:将分割后的几部分低位对齐相加间界叠加:从一端沿分割界来回折送，然后对齐相加(此法适于关键字的数字位数特别多)

折叠法

例关键字为：0442205864，哈希地址位数为4586442200410088H(key)=0088移位叠加58640224046092H(key)=6092间界叠加除留余数法

设定哈希函数为:H(key)=keyMODp(p≤m)

其中，m为表长

p为不大于m的质数或是不含20以下的质因子9.3哈希表哈希函数构造的方法9.3哈希表哈希函数构造的方法

给定一组关键字为:12,39,18,24,33,21，若取p=9,则他们对应的哈希函数值将为:3,3,0,6,6,3可见，若p中含质因子3,则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能例如：为什么要对p加限制？9.3哈希表哈希函数构造的方法随机数法设定哈希函数为:H(key)=Random(key)其中，Random为伪随机函数此法用于构造关键字长度不等的哈希函数。选取哈希函数考虑的因素：计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）关键字分布情况记录的查找频率

9.3哈希表处理冲突的方法处理冲突的方法“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。开放定址法链地址法为产生冲突的地址H(key)求得一个地址序列：H0,H1,H2,…,Hs1≤s≤m-1Hi=(H(key)+di)MODm其中：i=1,2,…,s H(key)为哈希函数;m为哈希表长;di为增量序列,有下列三种取法:开放定址法9.3哈希表处理冲突的方法对增量di

的三种取法：1)线性探测再散列

di=ci最简单的情况c=12)二次探测再散列

di=12,-12,22,-22,…,3)随机探测再散列

di

是一组伪随机数列或者

di=i×H2(key)(又称双散列函数探测)9.3哈希表处理冲突的方法注意：增量di应具有“完备性”即：产生的Hi

均不相同，且所产生的

s(m-1)个Hi值能覆盖哈希表中所有地址。则要求：※平方探测时的表长m必为形如4j+3

的素数（如:7,11,19,23,…等）；※随机探测时的m和di没有公因子。9.3哈希表处理冲突的方法9.3哈希表处理冲突的方法例表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=keyMOD11,现有第4个记录，其关键字为38，按三种处理冲突的方法，将它填入表中(1)H(38)=38MOD11=5冲突

H1=(5+1)MOD11=6冲突

H2=(5+2)MOD11=7冲突

H3=(5+3)MOD11=8不冲突(2)H(38)=38MOD11=5冲突

H1=(5+1²)MOD11=6冲突

H2=(5-1²)MOD11=4不冲突(3)H(38)=38MOD11=5冲突设伪随机数序列为9，则：

H1=(5+9)MOD11=3不冲突0123456789106017293838389.3哈希表处理冲突的方法例如:给定关键字集合构造哈希表

{19,01,23,14,55,68,11,82,36}设定哈希函数H(key)