08 第8章 查找.pptx

第1页：第八章查找

第八章查找

第2页：查找的基本概念

几个概念

• 查找表
• 同类数据元素构成的集合；元素之间松散关系
• 操作
• 查询存在、检索属性=>静态查找：
• 插入、删除=>动态查找
• 关键字：数据元素或记录的数据项值
• 主关键字、次关键字
• 查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素
• 查找方法
• 取决于表中数据元素的组织关系，例如
• 松散关系：顺序查找
• 大小顺序关系：对半查找

第3页：第八章内容提要

本章内容：掌握静态表上的各种查找算法和性能分析；掌握动态查找表上的各种查找算法和性能分析

• 8.1静态查找
• 8.2动态查找
• 8.3哈希表
• 本章重点

第4页：第一节静态查找

第一节静态查找

第5页：静态查找的内容安排

1.1顺序表的查找

• 1.2有序表的查找
• 1.3索引顺序表的查找

第6页：1.1顺序表的查找

1.1顺序表的查找

• 顺序查找又称线性查找，是最简单的查找方法，它是从线性表的一端开始，顺序扫描线性表，依次将扫描到的结点的关键字和给定的值k比较，若相等，则查找成功，若扫描结束后仍为找到，则查找失败

第7页：顺序查找的存储结构与算法

存储结构Typedefstruct{ElemType*elem;//数据元素存储空间基址Intlength;}

• 查找过程
• 从表的一端开始逐个进行记录的关键字和给定值的比较intSearch_Seq(SSTableST,KeyTypekey){ST.elem[0].key=key;for(i=S.length;!EQ(ST.elem[i].key,key);--i);returni;东华理工学院程朋}根

第8页：顺序查找举例

例如算法描述01234567找6489101192888075645637211913564监视哨iiiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1

第9页：顺序查找的性能分析

性能分析

• 等概率时的平均查找长度
• 缺点:平均查找长度较大，特别是当n很大时查找效率较低
• 优点：算法简单且适应面广n1(ni1)ni1nissiPCASLi11n2

第10页：1.2有序表的查找

1.2有序表的查找

• 特点：
• 数据元素按关键字的大小依次排列
• 查找过程：
• 采用折半查找实现
• 先确定待查记录所在范围，然后逐步缩小范围，直到找到或找不到该记录为止lowhighmid

第11页：折半查找算法

查找算法

• intSearch_Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。low=l;high=ST.length;while(low<=high){mid=(low+high)/2;//置区间初值ifEQ(key,ST.elem[mid].key)returnmid;//找到待查元素elseifLT(key,ST.elem[mid].key)high=mid-1;//继续在前半区间查找elselow=mid+1;//继续在后半区间进行查找}return0;//在顺序表中不存在待查元素
• }//Search_Bin

第12页：折半查找举例

7928880756456372119135找21891011highmidlow1110987654321

• 例如算法描述123456928880756456372119135lowmidhigh1234567891011928880756456372119135lowmidhigh

第13页：折半查找举例续

1234567928880756456372119135找70891011lowmid1234567high891011928880756456372119135123456928880756456372119135lowhighmid123456low7midhigh891011928880756456372119135lowmidhigh7891011

第14页：折半查找的判定树

1110987654321928880756456372119135lowhigh1185210741936判定树：7891011928880756456372119135

• 例如算法描述123456

第15页：折半查找的性能分析

性能分析

• 查找过程可用一个二叉树来描述
• 在查找成功时进行比较的关键字个数最多不超过树的深度log2n+1
• 如果查找不成功，则找了一条从根结点到外部结点的路径，进行比较的关键字个数最多也不超过树的深度log2n+1
• 等概率时的平均查找长度
• 折半查找的效率比顺序查找高，但要求是只能查找有序表22j2log(n1)1log(n1)11n1nnhj1nASLPCi1j1iibs

第16页：1.3静态树表的查找

1.3静态树表的查找

• 是针对有序表中各记录的查找概率不等时的一种查找方法
• 方法是：根据各记录的权值，建立一棵二叉树，使这棵二叉树的带权路径长度PH值在所具有同样权值的二叉树中近似为最小，称这类二叉树为次优查找树

第17页：次优查找树的构造方法

设有记录系列（rl,rl+1,…rh），对应的权值为（wl,wl+1,…wh）

• 构造次优查找树的方法如下：
• 先找到记录系列中
• 为计算方便，引入累计权值和的概念，这时
• 取最小值Pi的结点作为根结点，然后分别对（rl,rl+1,…ri-1）和（ri+1,,…rh）构造两i棵次优查找树Pi|hi1ji1i1jjww|swiwji1Pi|(swhswl1)swiswi1|

第18页：次优查找树构造举例

例如

• 已知含有9个关键字的有序表及其权值为：IHGFEDCB关键字：A53443521权值：1
• 构造过程如下：28232016129421swi:231580715222527Pi:Pi:119619i=4，左子树817i=6，根i=8，右子树

第19页：次优查找树示例

FDHBEGHAC次优查找树

第20页：1.4索引顺序表的查找

1.4索引顺序表的查找

• 实现方法
• 用分块查找来实现
• 除表本身外，还需建立一个索引表，原表分成多个子表每个子表对应索引表中的一个记录项
• 查找过程
• 选确定记录所在的块，然后在块中顺序查找（如果记录是有序的则可以用折半查找）
• 设每块含有s个记录，则分块查找的时间为222sASLLLb1s11(ns)1bsbw

第21页：分块查找示例

1234567891011121314151617182248861713索引表5386577458604824384442332098131222查38查找成功

第22页：第二节动态查找表

第二节动态查找表

第23页：动态查找表的特点

特点：表结构本身是在查找过程中动态生成

• 2.1二叉排序树和平衡二叉树
• 2.2B树和B+树

第24页：二叉排序树的内容安排

2.1二叉排序树和平衡二叉树

• （1）二叉排序树及其查找过程
• （2）二叉排序树的插入
• （3）二叉排序树的删除
• （4）查找分析
• （5）平衡二叉树

第25页：二叉排序树的定义

(1)叉排序树及其查找过程

• 二叉排序树
• 或者是一棵空树，或者具有如下性质的二叉树:
• (1)如果左子树不为空，则左子树上的所有结点的值均小于它的根结点的值；
• (2)如果右子树不为空，则右子树上的所有结点的值均大于它的根结点的值；
• (3)它的左右子树均为二叉排序树

第26页：二叉排序树的查找过程

查找过程

• 将给定值与根结点的关键字比较，若相等则查找成功，否则根据给定值和根结点的关键字之间的关系分别在左子树(<根)和右子树(>根)上继续查找查61找到61查25没找到

第27页：二叉排序树的查找算法

东华理工学院程朋根

• BiTreeSearchBST(BiTreeT,KeyTypekey，BiTreef,BiTree&p){
• //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素，若查找成功则指针p指向该数据元素结点，并返回TRUE，否则指针p指向查找路径上访问的最后一个结点并返回FALSE，指针f指向T的双亲，其初始调用为NULLif(!T){p=f;returnFALSE; }//查找不成功elseifEQ(key,T->data.key){p=T;returnTRUE;}//查找成功elseifLT(key, T->data.key)//在左子树中继续查找SearchBST(T->lchild,key,T,p);elseSearchBST(T->rchild,key,T,p);//在右子树中继续查找
• }//SearchBST

第28页：二叉排序树的插入

(2)二叉排序树的插入

• 二叉排序树是一种动态树表，是在查找过程中当树种不存在关键字等于给定的结点时在进行插入
• 图解实例（45,24,53,45,12,24,90）

第29页：二叉排序树的插入算法

插入算法 StatusInsertBST(BiTree&T,ElemTypee){//查找不成功S=(BiTree)malloc(sizeof(BiTNode)); s->data=e; s->lchild=s->rchild=NULL; if(!p)T =s;//被插结点*s为左孩子elsep->rchild=s;} else return FALSE;} 
第30页：二叉排序树的删除情况
(3)二叉排序树的删除
删除一个结点后依旧保持二叉树的特性
删除的几种情况：
假设*p为被删除的结点，Rl和Rr为它的左右子树，*f为p的父结点
(1)如果删除的结点是根：
无左孩子，则右孩子为根结点
有左孩子，则左孩子为根结点，右孩子则作为左子树按中序遍历时最后一个结点(如D)的右孩子ABCDABCPABCFDEACDBFE
第31页：删除非根结点的处理
(2)删除的为非根结点：1.若*p为叶结点，即Rl和Rr为空，只需修改*p的父指针2.若*p只有左子树或右子树，则可以将Rl或Rr取代p成为p双亲的孩子
第32页：删除左右子树均非空的处理
03）若*p的左右孩子都不空，则在删除*p之前做中序遍历求*p的前驱*s(例如…CLC…QLQSLSPPR…)，然后进行两种处理：
方法一:令*p的左子树为其双亲f的左子树，*p的右子树为*s的右子树；方法一
第33页：删除处理方法二
方法二:令*p的直接前驱替代*p,然后再从二叉排序树中删去它的直接前驱方法二
第34页：二叉排序树的删除算法
二叉排序树的删除算法 StatusDeleteBST(BiTree&T,KeyTypekey){//不存在关键字等于key的数据元素else{ ifEQ(key,T->data.key)Delete(T); elseifLT(key,T->data.key)DeleteBST(T->lchild,key); elseDeleteBST(T->rchild,key); returnTRUE; } } 
第35页：删除结点的重接算法
voidDelete(BiTree&p){//从二叉排序树中删除结点p，并重接它的左或右子树if(!p->rchild){//右子树空则只重接它的左子树q=p;p=p->lchild;free(q);}elseif(!p->lchild){//只重接它的右子树q=p;p=p->rchild;free(q);}else{q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild }//转左，然后向右到尽头,即s没有右孩子；q为s的父结点p->data=s->data;//s指向被删结点的“前驱”if(q!=p)q->rchild=s->lchild;//重接*q的右子树elseq->lchild=s->lchild;//重接*q的左子树}
}//Delete
第36页：二叉排序树的查找分析
(4)查找分析
特性：二叉排序树不唯一，深度不一，平均查找长度和树形态有关
例如，关键字序列（45,24,53,12,37,93）和关键字系列（12,24,37,45,53,93）构成的不同形态的二叉查找树
最坏的单支情况；平均查找长度为(n+1)/2
最好的情况和折半查找相同，平均查找长度和log2n成正比返回452453931237122437455393单支
第37页：平衡二叉树的定义
(5)平衡二叉树
平衡二叉树(BalancedBinaryTree,)
或者是一棵空树
或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差(平衡因子)的绝对值不超过1
平衡因子
左子树的深度减去右子树的深度
平衡二叉树上所有结点的平衡因子只可能是-1,0,1
第38页：平衡二叉树的生成过程
关键字系列:(13,24,37,90,53)
平衡二叉树的生成过程向左逆时针向右顺时针向左逆时针
第39页：平衡调整的四种类型
X0A-2A0B0RR型B-1X-1B-1X0RL型X0A0B0B0A-2X-1B1X0A0A2X0B0LL型B-1X0A2X0A0B0A2X1B0LR型A-2
平衡二叉树的平衡调整
在插入或删除操作过程中有可能破坏原来的平衡，因此要进行调整形成新的平衡，分四种情况：
LL型、LR型、RR型、RL型
第40页：平衡二叉树的存储与右旋
平衡二叉树存储结构与旋转处理算法
TypedefstructBSTNode{ElemTypedata;Intbf;//结点平衡因子StructBSTNode*lchild,*rchild;
}
VoidR_Rotate(BSTree&p){//作右旋处理lc=p->lchild;P->lchild=lc->rchild;lc->rchild=p;p=lc;
}//R_Rotatelc➔rlcR_Rotatelc➔lp➔rlc➔lp➔rlc➔rPlcp
第41页：左旋处理算法
VoidL_Rotate(BSTree&p){//作左旋处理rc=p->rchild;P->rchild=rc->rchild;rc->lchild=p;p=rc;
}//L_Rotaterc➔rrcL_Rotaterc➔lp➔lrc➔rrc➔lp➔lPrcP
第42页：左平衡旋转处理算法
东华理工学院程朋根
平衡二叉树的平衡处理算法
VoidLeftBalance(BSTree&T){//对以指针T所指结点为根的二叉树作左平衡旋转处理，算法结束时，T指向新的根结点lc=T-lchild;Swith(lc->bf){//bf平衡因子caseLH:T->bf=lc->bf=EH;R_Rotate(T);break;caseRH:rd=lc->rchild;switch(rd->bf){caseLH:T->bf=RH;lc->bf=EH;break;//fig1caseEH:T->bf=lc->bf;break;//fig2//fig3caseLH:T->bf=EH;lc->bf=LH;break;}//switch(rd-bf)rd->bf =EH;R_Rotate(T);L_Rotate(T->lchild);}//switch(lc-bf)
}//LeftBalancerd➔llc-1平衡Fig1lc➔lp➔rp➔rrd➔lTrdT-1rd1lc0lc➔l
第43页：2.2B树的概念
2.2B树和B+树
B树概念
一棵m阶B树，或为空树，为满足下列特性的m叉树
(1)树中每个结点最多有m棵子树
(2)若根结点不是叶子结点，则至少有两棵树
(3)除根之外的所有非终端结点至少有m/2棵子树
(4)所有的非终端结点有n-1个关键字和n个指针域(m/2-1≤n≤m-1)
(5)所有叶结点都出现在同一层上，且不设指针域
第44页：B树的查找过程
B树的查找过程
先从根结点中查找，若X在根结点中，则查找成功；否则进行以下三中情之一
(1)若X<K1,则继续到A0结点中去查找
(2)若X>Kn,则继续到An结点中去查找
(3)若Ki<X<Ki+1,则继续到Pi结点中去查找
(4)若Pi指向空，则查找失败A0，K1，A1，K2，A2，…，An-1，Kn，An
第45页：B树的插入操作
B树的插入操作
B树的生成是从空树起，逐个插入关键字而得
对于一个m阶的B树，若在一个不满m-1个关键字的结点中进行插入，就直接进行插入
但在一个已有m-1个关键字的结点中进行插入，则要将结点分成两个结点，并且还要在它的上层结点进行插入
如果上层结点已满，则要再次分解上层结点，…，直到根结点m=3
第46页：B树的插入算法
东华理工学院程朋根
B树的插入操作算法
StatusInsertTree(Btree&T,KeyTypeK,Btreeq,inti){//在m阶B树T上结点*p的key[i]与key[i+1]之间插入关键字Kx=K;ap=NULL;finished=FALSEwhile(q&&!Finished){insert(q,i,x,ap);//将x和ap分别插入到q->key[i+1]和q->ptr[i+1]if(q->keynum<m)finished=TRUE;else{s=[m/2];split(q,ap);x=q->key[s];//将->key[s+1..m],q->ptr[s..m]和q->recptr[s+1..m]移入新结点*apq=q->parent;if(q)i=Search(q,x);}//else}//whileif(!finished)//为空树或根结点分裂为*q和*apNewRoot(T,q,x,ap);//生成含信息(T,x,ap)的新的根结点*T,原T和ap为子树指针
}
第47页：B树的删除操作
B树的删除操作
首先找到要删除关键字的结点
若所删除关键字为非终端结点中的Ki(如根结点的45)，则可以指针Ai所指子树的最小关键字Y(50)替代Ki,然后在相应的结点中删除Y
若删除关键字在最下层非终端结点，且结点的关键字个数不少于m/2,，则直接删除（如12）(a)，否则要进行“合并”操作
若所在结点数目为m/2-1,右兄弟结点数目大于m/2-1,则兄弟结点最小关键字(61)上移，双亲结点小于且紧靠上移关键字的关键字下移（如53）(b)
第48页：B树删除的合并操作
若所在结点和兄弟结点关键字数目均为m/2-1{(53)，(70)},假设右兄弟的地址由双亲结点的指针Ai所指，则所在结点的剩余关键字和指针，加上双亲结点中的关键字Ki(61)，合并到Ai所指的兄弟结点中(61,70)(c)
如果双亲结点关键字数目小于m/2-1，依此类推:(c)中删除37->(d)
第49页：B+树的概念
B+树的概念
一棵m阶B+树和m阶的B树的差异在于：
有n棵子树的结点有n个关键字(B树为n+1)
所有的叶结点中包含了全部关键字的信息及指向关键字记录的指针
且叶结点依据关键字大小自小而大顺序连接
所有的非终端结点其实是索引部分，它包行其子树中最大（或最小）关键字
第50页：B+树的查找操作
B+的查找操作：从最小关键字顺序查找、从根结点开始随机查找
随机查找时一直要追踪到叶结点
第51页：第三节哈希表
第三节哈希表
第52页：哈希表的概念
为提高查找的效率，希望一次存取就能查找到所需的记录，为此必须建立记录的关键字与其存储位置之间的函数关系f，这个映射关系称为哈希(Hash)函数
根据设定的哈希函数H(key)和处理冲出（如链地址法）的方法将一组关键字映象到一个有限的连续地址集上，以关键字在地址中的象为记录在表中的存储位置，这个表便称为哈希表
哈希函数的方法：
直接地址法：H(key)=a*Key+b
数值分析法
平方中数法
折叠法
除留余数法
处理冲突方法
第53页：直接地址法
直接地址法
取关键字或关键字的某个线性函数值为哈希地址H(key)=key或H(key)=a*key+b
例如：某地区进行不同年龄（1—100岁）人口数字统计时，1到100一般是连续的，可以建立地址和年龄的直接对应关系:H(key)=key
如按年份查询，则也可以采用直接地址法建立地址和年份的关系，1949、1950、1953、…分别对应1、2、3、…:H(key)=key-1948
第54页：数字分析法
取关键字的若干数字位组成哈希地址
条件是必须预先知道关键字
分析各个关键字在不同位上的随机分布情况，如果某位在不同的关键字上是相同的，则不能采用，如果是随机的则可以考虑采用
数字分析法
第55页：平方中数法与除留余数法
平方中数法
折叠法
除留余数法H(key)=keyMODpp≤mp为质数或不包含小于20的质因素的合数
第56页：处理冲突的方法
处理冲突方法
开放地址
再哈希
链地址法
建立公共溢出区
第57页：本章重点
查找的分类
顺序表查找、有序表的查找
二叉排序树概念、构造过程
平衡二叉树的概念、平衡处理方法
B树概念、B树的查找、插入、删除方法
B+树的概念
哈希函数、哈希表的概念本章重点：
第58页：习题
习题：
1、折半查找的条件、算法及其分析，并举例。
2、输入整数系列（86，50，78，59，64，55，23，100，40，80，45），画出建立二叉排序树过程，最后分别图示将其中50，86删除后的二叉排序树删除。
3、能计算二叉树各结点的平衡因子，并判断一棵树是否是平衡二叉树。