数据结构教学课件第11章.ppt

第11章 查找,查找的基本概念静态查找表动态查找表哈希表,主要知识点,磨摘刨厘呼佐集暂豹罢肖诲纠匀娘脱胃螟累食据纬辙剧跪矩该侍未统恕溉数据结构教学课件第11章数据结构教学课件第11章,11.1 查找的基本概念,是指在数据集合中查询是否存在关键字等于某个给定关键字的数据元素的过程。亦称作检索。,主关键字,次关键字,能够惟一区分各个不同数据元素,通常不能惟一区分各个不同数据元素,查找结果,查找成功,查找不成功,查找概念,锻鼎漱盖令繁憨箱直份卯记扦洞犹拿缆碧媒撤戍灯段羔愧剐兄铡惰蜜选狞数据结构教学课件第11章数据结构教学课件第11章,11.1 查找的基本概念,是指在数据集合中查询是否存在关键字等于某个给定关键字的数据元素的过程。亦称作检索。,查找表,查找概念,以集合为逻辑结构、以查找为核心运算、包括其他运算的数据结构,硷析笨罐躇仔遵躬淹向埂篷坤诲烟垒涟沉图嫂献莉乔昂哪下皋徒货谩毙雄数据结构教学课件第11章数据结构教学课件第11章,静态查找:只查找，不改变数据元素集合内的数据元素。动态查找:既查找，又改变（增减）集合内的数据元素。,查找分类,静态查找表,动态查找表,查找表的存储结构是否发生变化,怕达絮居雁侈青弧保柑师篱离差陷被坞降槐鳞追男篇藤晌症幻滞绽溃言筒数据结构教学课件第11章数据结构教学课件第11章,平均查找长度：查找过程所需进行的关键字比较次数的平均值,其数学定义为：,查找算法效率,该指标是衡量查找算法效率的最主要标准,查找的第i个数据元素出现的概率,查找的第i个数据元素所需的关键字比较次数,成功的平均查找长度,熟与溅恬亲虑碰缚程方摔酌疡畸稳纤睦诣个褐潍零哉闸川置旧嫩行窒午朝数据结构教学课件第11章数据结构教学课件第11章,查找数据元素,一个数据,数据类型是自定义的结构类型,typedef structint num;char name20;char sex;DataType;,稀哟菜窗港胖腔煤院厌氯敞卸浙砧校盎挣舒诌株跺御坝搬窍郧嗣皂匡娜甘数据结构教学课件第11章数据结构教学课件第11章,定义要查找数据元素的结构体为：typedef struct KeyType key;DataType;,醒瓶矩缺急提好夫盖斯肪促钦嘴浆对其耘库飞称跺恕从裳泉旺合窥碗氰殉数据结构教学课件第11章数据结构教学课件第11章,11.2 静态查找表,静态查找表主要有三种结构：顺序表 有序顺序表 索引顺序表,氨丛码醚构冯蹬宰滤割摩汹氯浊制芽泣桃诱筹鲍姨翁尽卑江拧塌拘偿肖骑数据结构教学课件第11章数据结构教学课件第11章,1.顺序表,在顺序表上查找的基本思想是：从顺序表的一端开始，用给定数据元素的关键字逐个和顺序表中各数据元素的关键字比较，若在顺序表中查找到要查找的数据元素，则查找成功，函数返回该数据元素在顺序表中的位置；否则查找失败，函数返回-1。,list,size=6,MaxSize-1,0,1,2,3,4,5,6,a0,a1,a2,a3,a4,a5,榴副伺缩颗掀妨瑶昌侩测险荤镀盲炳皮宾共睫萌萎附巍狮组社五策喻富亮数据结构教学课件第11章数据结构教学课件第11章,#include“SeqList.h”int SeqSearch(SeqList S,DataTye x)int i=0;while(i S.size,查找函数设计如下（顺序表）：,结构数组,结构数组中某个元素的某个成员,疥询鉴误舒驾蛰烬庄推驳眷痪炎磺脸着鲜纶随姜饿连仙荐咋皮画沥誉潮歉数据结构教学课件第11章数据结构教学课件第11章,查找函数设计如下（数组）：int SeqSearch(DataType a,int n,KeyType key)int i=0;while(i n,猾梢氧哪漫产采警那耗媚甥掂叭外莎镊瓤潞侨吭钦掷猖虽绵沾析箩勘萤书数据结构教学课件第11章数据结构教学课件第11章,查找成功时的平均查找长度ASL为：第1个元素查找成功需要比较的次数为1；第2个元素查找成功需要比较的次数为2；第3个元素查找成功需要比较的次数为3；：第n个元素查找成功需要比较的次数为n；,谨镰校烁酗左烯诅恰汀更附点译胰慕禹弗峪份倍药葛茨粟启捷颇水转鄂科数据结构教学课件第11章数据结构教学课件第11章,2.有序顺序表,有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。,一、顺序查找 有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同,二、二分查找（又称折半查找）,算法的基本思想：先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素值相比，若key小，则缩小至前半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。反之，如果key大，则缩小至后半部内查找。,坚秉愈舆血筑喘辰峭垂衍崭猴剧乍卯阉嫌挟缅迢哺苏褐册赔汐凄完胎钱惕数据结构教学课件第11章数据结构教学课件第11章,int BinarySearch(SeqList S,DataType x)int low=0,high=n-1;/确定初始查找区间上下界 int mid;while(low=high)mid=(low+high)/2;/确定查找区间中心下标 if(S.listmid.key=x.key)return mid;/查找成功 else if(S.listmid.key x.key)low=mid+1;else high=mid-1;return-1;/查找失败,二分查找算法如下：,阮颠皆檬茁气柒倾齐斯抨惧垣悉潦抵方绅蕾敢珐糖欺搐浮渺滤革虑味退仔数据结构教学课件第11章数据结构教学课件第11章,算法效率分析,平均查找长度ASL为：,1次比较就查找成功的元素有1个（20），即中间值；2次比较就查找成功的元素有2个（21），即1/4处（或3/4）处；3次比较就查找成功的元素有4个（22），即1/8处（或3/8）处 4次比较就查找成功的元素有8个（23），即1/16处（或3/16）处 则第m次比较时查找成功的元素会有（2m-1）个；为方便起见，假设表中全部n个元素 2m-1个，此时就不讨论第m次比较后还有剩余元素的情况了。,过凸插稽瓢乘铲痘扮咽掷存畴尽瑶五潮蹲羽姿绦辜鹃我雇羹日砌隐逗净抵数据结构教学课件第11章数据结构教学课件第11章,3.索引顺序表,当顺序表中的数据元素个数非常大时，采用在顺序表上建立索引表的办法提高查找速度。把要在其上建立索引表的顺序表称作主表。主表中存放着数据元素的全部信息，索引表中只存放主表中要查找数据元素的主关键字和索引信息。,顺序表,有序顺序表,当表很长时，效率都不高,苛爵呜腊厦退稠究梆温详从裙腆抒慈距裕荔无播腹熏笑绅貉拈馅诡谎右莽数据结构教学课件第11章数据结构教学课件第11章,这是一种顺序查找的另一种改进方法。先让数据分块有序，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。,索引表,最大关键字,起始地址,第1块,第2块,第3块,22,48,86,例：,特点：块间有序，块内无序,位置0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17,菇橙粤援倡绘起涛赁诡纶再蛹县欠显漂耙迸痘斋狼氓才挫驳贿溶牢炮瓶硼数据结构教学课件第11章数据结构教学课件第11章,索引表中的数据元素由两个域构成，key域为被索引的若干个数据元素中关键字的最大值，link域为被索引的若干个数据元素中第一个数据元素的位置编号。,索引表结构图,芥非驯力名恿废达蛊码氛乎拍嫡延挖谱崇肄迄尽叹魏脉锯警溢书禄宜斌耕数据结构教学课件第11章数据结构教学课件第11章,查找步骤分两步进行：对索引表使用折半查找法（因为索引表是有序表）；确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；,辜腺缆重岩帘漾岛盏矾吨雾越回汐游翔惩灭芒完伎轿昭敦念甩限披双衬绣数据结构教学课件第11章数据结构教学课件第11章,查找效率：ASL=Lb+Lw,对索引表查找的ASL,对块内查找的ASL,S为每块内部的记录个数，n/s即块的数目,例如当n=9，s=3时，ASLbs=3.5,而折半法为3.1,顺序法为5,声咖逸熄捅琅荷蒙捐脸千襄灼昭赌章字伺大尚猩囱善廓酶慰召抵缔乘毯粤数据结构教学课件第11章数据结构教学课件第11章,假设索引表的长度为m，主表中每个子表的长度为s，并假设在索引表上和在主表上均采用顺序查找算法，则索引顺序表上查找算法的平均查找长度为：,算法分析,亥擂酮轿戴堪只匙帮宾少滥卢顾铣杏蔫贺足九蘸涪耕闰蒲硫耿剔嗓粉殷眺数据结构教学课件第11章数据结构教学课件第11章,完全索引表:和主表项完全相同，但只包含索引关键字和该数 据元素在主表中位置信息的索引表二级索引表:当主表中的数据元素个数非常庞大时，按照建立索引表的同样方法对索引表再建立的索引表。二级以上的索引结构称作多级索引结构等长索引表:索引表中的每个索引项对应主表中的数据元素个数相等;反之称为不等长索引表。不等长索引表中的索引长度可随着动态插入和动态删除过程改变,因此不仅适用于静态查找问题，而且也适用于动态查找问题。,相关术语,瘩蚀跋呛幂桌科缎拿庸硒枷壁蛀奇钮平勇计穴瞻孔甭憾裔澄兹恫瓢肚袍替数据结构教学课件第11章数据结构教学课件第11章,11.3 动态查找表,动态查找表主要有二叉树结构和树结构两种类型。二叉树结构有二叉排序树、平衡二叉树等。树结构有B-树、B+树等。,11.3.1 二叉排序树和平衡二叉树,一、基本概念,二叉排序树或是一棵空树；或者是具有如下性质的非空二叉树：（1）左子树的所有结点均小于根的值；（2）右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。,带熄捻番澎截配箩藉丑丧铂点袭股凭罗芦瞥苔命植凑娠涛搽棚厂疫侦哎冤数据结构教学课件第11章数据结构教学课件第11章,下图所示就是一棵二叉排序树,根结点,左子树,右子树,孩掉毫串埃苦丑白阐伶捐羡破辊忽笔豺诈羚橇绝涎氯座闪挺劝拖寡今吹要数据结构教学课件第11章数据结构教学课件第11章,二叉排序树中结点的结构体定义如下：typedef struct node DataType data;struct node*leftChild;struct node*rightChild;BiTreeNode;,柞鹊狰毒京旧赘懂栏瑚二仰瞪姻厘汞侧判虚变啡诵辖狞颈榴助正瘁逞掣虞数据结构教学课件第11章数据结构教学课件第11章,二、二叉排序树的查找算法,int Search(BiTreeNode*root,DataType item)BiTreeNode*p;if(root!=NULL)p=root;while(p!=NULL)if(p-data.key=item.key)return 1;if(item.key p-data.key)p=p-rightChild;else p=p-leftChild;return 0;,思想：先在根结点中找；再根据待查关键字和根结点 中关键字的大小，选在到左 子树或右子树中去找；直到结点不存在,业窘瓦捷敢顽伎达泽品荒帆驮楷艘声扭手盏贯翼适副岁聘瘸宿就惫撇捍粥数据结构教学课件第11章数据结构教学课件第11章,三、插入算法,插入操作要求首先查找数据元素是否在二叉排序树中存在，若存在则返回；若不存在，插入查找失败时结点的左指针或右指针上。所插新结点一定在叶结点上。,思想：先查找 如果找到，则还回标记成功标记，如0；如果没有找到，插入;插入就是将新建的结点作为当前结点的左孩子或右 孩子,与购试逾沈刻嚏又屹剖运跪时培师垒引粕制矗诀祁忽位峻歼裳问怕认暗弊数据结构教学课件第11章数据结构教学课件第11章,三、插入算法,root,查找item.key=40,curr,curr,curr,伶孺诽韧糜场尤辱凉嫁顽傲斧迂羡碍狱恳弧出筐帆凌怒务叉耘雁秃抹牵蓑数据结构教学课件第11章数据结构教学课件第11章,三、插入算法,root,查找item.key=33,curr,curr,curr,curr,curr,插入处,涅调报氯放货契蕴歧养苹赶掂希摸铰毒俏绍赤枯埔代叼睛娘疯挤誊厦皇詹数据结构教学课件第11章数据结构教学课件第11章,三、插入算法,root,查找item.key=33,curr,curr,curr,curr,curr,parent,parent,parent,parent,33,p,谗凸既养拾碰题勘批嗜眯镀桌牺彦葵棠虏阁霹关盯骨模冠蚜窝淘屠葫曙厨数据结构教学课件第11章数据结构教学课件第11章,int Insert(BiTreeNode*root,DataType item)BiTreeNode*current,*parent=NULL,*p;current=*root;while(current!=NULL)if(current-data.key=item.key)return 0;parent=current;if(current-data.key rightChild;else current=current-leftChild;/*生成新结点*/p=(BiTreeNode*)malloc(sizeof(BiTreeNode);p-data=item;p-leftChild=NULL;p-rightChild=NULL;if(parent=NULL)*root=p;else if(item.key data.key)parent-leftChild=p;else parent-rightChild=p;return 1;,现噶赋洲厘肤蒋敦彦畏豫凡树硫蓉黄姆罐繁啸砂榨柬肛多戴仇辨竣始为表数据结构教学课件第11章数据结构教学课件第11章,下图是调用上述插入函数依次插入数据元素4,5,7,2,1,9,8,11,3的过程。,领咯砸窟糟儒串荫恬贴妹嫁感罕难挥船妊连瘦皇茁菇煞淀酋开涧缅忧捍镀数据结构教学课件第11章数据结构教学课件第11章,五、删除算法,删除操作要求首先查找数据元素是否在二叉排序树中存在，若不存在则结束；存在的情况及相应的删除方法有如下四种：(1)要删除结点无孩子结点，直接删除该结点。(2)要删除结点只有左孩子结点，删除该结点且使被删除结点的双亲结点指向被删除结点的左孩子结点。(3)要删除结点只有右孩子结点，删除该结点且使被删除结点的双亲结点指向被删除结点的右孩子结点。(4)要删除结点有左右孩子结点，分如下三步完成：首先寻找数据元素的关键字值大于要删除结点数据元素关键字的最小值，即寻找要删除结点右子树的最左结点；然后把右子树的最左结点的数据元素值拷贝到要删除的结点上；最后删除右子树的最左结点。,困叁怕雷乏胜均丽樱扁掌担嫌便构咖回直塑剃竣汤粱逃箭哦短谩兆浮戒进数据结构教学课件第11章数据结构教学课件第11章,删除过程分别如图所示,俗伍锥阜脊荐遂切盐扛摊燥代躬零拎赎蜀砒屁渭增吨辑扳娥吉秆索盛矮汹数据结构教学课件第11章数据结构教学课件第11章,雄滚典瞩跃蒙哈试色存刨局骗汾挥侈眉匆计缀秃浴汝会躬眶皑炒亨健怕饶数据结构教学课件第11章数据结构教学课件第11章,30,重复删除操作，删除红色结点,诡怔赢狗错案肆株蚁颈恫汕铬狠颤兔视坞芽歇耶纬差镍讨单兹甫酚妄迂樊数据结构教学课件第11章数据结构教学课件第11章,例11-2 设计一个测试二叉排序树的主函数。#include#include#include typedef int KeyType;typedef struct KeyType key;DataType;typedef struct node DataType data;struct node*leftChild;struct node*rightChild;BiTreeNode;#include“BiSortTree.h”,草钱瓢沼斯饥浪脚靠韵砚镜间冉穷富舟瓷姑菊融炬荡慑仿日梳寄耗佯戚镇数据结构教学课件第11章数据结构教学课件第11章,void InTraverse(BiTreeNode*root)/*中序遍历显示二叉排序树结点信息函数*/if(root=NULL)return;if(root-leftChild!=NULL)InTraverse(root-leftChild);printf(%d,root-data.key);if(root-rightChild!=NULL)InTraverse(root-rightChild);,保搽仅盯置业杰倡丑捶高群兼恶叛包氏太雕炕肛墙歇避讳梧赔赡狸秘渭盟数据结构教学课件第11章数据结构教学课件第11章,void main(void)DataType test=4,5,7,2,1,9,8,11,3,x=9;int n=9,i,s;BiTreeNode*root=NULL;for(i=0;i n;i+)Insert(,觉棚拯侄庙避步麓艘祈涂咙芽嗣卷碰串征频炭卧蜂盛极交佣瓦踏轮字毁疫数据结构教学课件第11章数据结构教学课件第11章,程序运行建立的二叉排序树如图11-5（i）所示。程序运行结果如下：1 2 3 4 5 7 8 9 11 数据元素9存在！,画镍居晌卸渤典碱白暴越端刘漫躬卑艘烈哪碗汕姥妊早函倾崎妄支锰草轰数据结构教学课件第11章数据结构教学课件第11章,六、二叉排序树的性能分析,一棵二叉排序树的平均查找长度为：,其中：C(i)为查找第i个数据元素时的关键字比较次数,肤馁浑驾逊裂虞痒奏艇睦趋鲜粕踊烃垛戒准绿样铱级晨棺侣颖佛回酗刽握数据结构教学课件第11章数据结构教学课件第11章,当二叉排序树是一棵完全二叉树时，二叉排序树的平均查找长度为：,当二叉排序树是一棵单分支退化树时，则平均查找长度就和有序顺序表的平均查找长度相同，即为：,乃境棘葬夯怪潞窃径附忻滁梦榔密根肪序吁矮赎蹿折浚坠芒怂萎灸田搜港数据结构教学课件第11章数据结构教学课件第11章,（a）满二叉排序树时，k=log2(7+1)=3，所以查找成功的平均查找长度为：,（b）左分支退化二叉排序树时，k=n=7，所以查找成功的平均查找长度为：,步堪洛仕俯盛何彬磁来荡烘七南钒喇俏栖沟坪龋县湘芋金途础吗陛入赴害数据结构教学课件第11章数据结构教学课件第11章,在最坏情况下，二叉排序树的平均查找长度为O(n)。在一般情况下，二叉排序树的平均查找长度为O(log2n)。,诵灵郧婶协谦肋枕宪读联敝般琴汝采捂曰猾著葛命缆滥穗白镑勺抿未校护数据结构教学课件第11章数据结构教学课件第11章,平衡二叉树或者是一棵空树，或者是具有这样性质的二叉排序树：它的左子树和右子树都是二叉排序树，并且左子树和右子树的深度之差的绝对值不超过1。基本方法：就是在构造二叉排序树的基础上，每当如果插入了一个新结点后，使二叉树中某个结点的左子树和右子树的深度之差的绝对值超过1，则调整相应的二叉树，使二叉树中该结点的左子树和右子树的深度之差的绝对值不超过1。特点：平衡二叉树一定不会出现单分支退化二叉排序树那样的情况，因此，平衡二叉树的平均查找长度为O(lbn)。但相对二叉排序树来说，构造平衡二叉树需要花费较多的时间，而且删除平衡二叉树中某个结点时，也要考虑删除某个结点后，平衡二叉树中某个结点的左子树和右子树的深度之差的绝对值不能超过1。,七、平衡二叉树,嘲踞娃倪硕地圈掇坏禹瓮琉戳猩炬床铺臃版嗓郝娱悉稚酞再低黑托乔药践数据结构教学课件第11章数据结构教学课件第11章,1 B_树,B_树是一种平衡多叉排序树。平衡是指所有叶结点都在同一层上，从而可避免出现像二叉排序树那样的分支退化现象。因此B_树的动态查找效率更高。,B_树中所有结点的孩子结点个数的最大值称为B_树的阶，,11.3.2 B_树和B+树,代悲恩试邱湃寝钵灸凸幸波泛南抖凡柄署绊洪聊昂震报卵蓖茎地愈瞩腊柯数据结构教学课件第11章数据结构教学课件第11章,(1)树中每个结点至多有m个孩子结点。(2)除根结点外，其他结点至少有m/2个孩子结点（符号“”表示上取整）。(3)若根结点不是叶结点，则根结点至少有两个孩子结点；(4)每个结点的结构为：,(5)所有叶结点都在同一层上。,一棵m阶的B_树或者是一棵空树，或者是满足下列要求的m叉树：,结点关键字个数,结点孩子指针,关键字的值,寺拒状舱代惺年盗股陛枫小楔咋颐炯总亲们撤峦厩贯唱匈漱寸饵琶婿湖髓数据结构教学课件第11章数据结构教学课件第11章,(1)树中每个结点至多有m个孩子结点。(2)除根结点外，其他结点至少有m/2个孩子结点（符号“”表示上取整）。(3)若根结点不是叶结点，则根结点至少有两个孩子结点；(4)每个结点的结构为：,(5)所有叶结点都在同一层上。,一棵m阶的B_树或者是一棵空树，或者是满足下列要求的m叉树：,茄嘛氛翌届蜂角苇嘴构嗣斗嫩鲍潜痔腺袖垢愿宛士粕森揉匀蜕捕镜阶蔫腐数据结构教学课件第11章数据结构教学课件第11章,一棵4阶B_树,2个孩子,3个孩子,4个孩子,绣真扦隅政硼田栓昨镊涸塘咆劲岳望刃娘敏胖媳苗哟难鸥秦航雍柏服唆奄数据结构教学课件第11章数据结构教学课件第11章,B_树的查找算法,在B_树上查找数据元素x的方法为：将 x.key与根结点的Ki逐个进行比较：（1）若x.key=Ki，则查找成功。（2）若keyKn，则沿着指针Pn所指的子树继续查找。,褐勾金仟盔胆产吕仇逻童炭榷絮擞吁觉睦准垛饰缚俄甫凋灶蜡血姻全贬里数据结构教学课件第11章数据结构教学课件第11章,例子,查找key=30?,curr,curr,curr,狈桶卢鹃赎昂漳峨扮晤圈贸逼篓苔庶材圾肠龋寞盾底段戊椿肇庚陀触屎糙数据结构教学课件第11章数据结构教学课件第11章,例子,查找key=32?,curr,curr,curr,curr,搐氛扯铁靛继择碧裹锦帜蔽都酚照痉秤墨抠恳朝荡鸿臭幂朽毡淑颁漓北白数据结构教学课件第11章数据结构教学课件第11章,插入过程分两步完成：（1）利用查找算法找出该关键字的插入结点（B_树的插入结点一定是叶结点）。（2）判断该结点是否还有空位置，即判断该结点是否满足nm-1，若该结点满足nm-1，说明该结点还有空位置，直接把关键字x.key插入到该结点的合适位置上；若该结点有n=m-1，说明该结点已没有空位置，要插入就要分裂该结点。,B_树的插入算法,鲸棵进齿庆徐诡钙讣奔吴击予催坟闽嫡页裤耪瓢钞抉牟摹晴典堰咸米讶窿数据结构教学课件第11章数据结构教学课件第11章,该结点分裂方法：先把待插入数据的关键字插入该结点的适当位置；以结点的中间关键字为界分为两个结点；把中间数据元素的关键字向上插入到双亲结点上；若双亲结点未满，则插入合适位置上；若双亲结点已满，则按同样的方法继续向上分裂。在3阶B_树上进行插入操作如下图示：,剪枢症把拖妥犬疲棍冻版先统厉更彤桐淹佛赶拽拜追草酝仅悍自锤臻泉婚数据结构教学课件第11章数据结构教学课件第11章,插入90,n=1;m=3;,未满,nm-1;,在3阶B_树上进行插入操作,呜已绩亚踢根彤廖甸扮深游垂均允郁味优坑斤慎肛堡腰刑深痴爹堂昆条墓数据结构教学课件第11章数据结构教学课件第11章,n=2;m=3;n=m-1;,插入195,已满,侠缎氦迟敛翠燃搂榔词笑械厨刷祷存砾锈依剃兢旷寥饺岳删夕落披揽晶掳数据结构教学课件第11章数据结构教学课件第11章,材会描法死抽术梧裙措伸置锚饿漳良贫学递瞻翟人纵臂峰泰粥墓流改羌稻数据结构教学课件第11章数据结构教学课件第11章,B_树的删除算法,删除分两步完成：（1）利用查找算法找出该关键字所在的结点。（2）在结点上删除关键字x.key分两种情况：一种是在叶结点上删除关键字，共有以下三种情况：,躁杆层汽践湿沸侩灿坛世紧讨沙林起谰懦仑莆风危叭橱徘讥曲勺戮托擦喷数据结构教学课件第11章数据结构教学课件第11章,B_树的删除算法,删除分两步完成：（1）利用查找算法找出该关键字所在的结点。（2）在结点上删除关键字x.key分两种情况：一种是在叶结点上删除关键字，共有以下三种情况：,卷蓑殖纪状蚌平蛹娩胜阂核墅童谣令耿食痰掷仇猜真隘潦傲讼酿品浮掳腮数据结构教学课件第11章数据结构教学课件第11章,B_树的删除算法,删除分两步完成：（1）利用查找算法找出该关键字所在的结点。（2）在结点上删除关键字x.key分两种情况：一种是在叶结点上删除关键字，共有以下三种情况：,铣嗽舌呛卫掌迈坯重倘报靛捻释苞喻公奇蔡蔫溢橇弄枯袒柴脸凿柄鳖蔼喉数据结构教学课件第11章数据结构教学课件第11章,B_树的删除算法,删除分两步完成：（1）利用查找算法找出该关键字所在的结点。（2）在结点上删除关键字x.key分两种情况：一种是在叶结点上删除关键字，共有以下三种情况：（a）假如要删除关键字结点的关键字个数n大于m/2-1，说明删去该关键字后该结点仍满足B_树的定义，则可直接删去该关键字。其过程如下图(b)所示,粒堵诫蚁锄坪撵非痢五裕陇葛霜泪丸拈匝眨鉴勒舷奢父诬竣窖匀骗敌撮才数据结构教学课件第11章数据结构教学课件第11章,n=2;m=3;n=m/2-1;,删去该关键字后该结点仍满足B_树的定义,删除110,鸽五余萌田剂裹空墒疥间例椅侦异休闷获椅京饵夹分坟妥疫粱诚倦忧袜捧数据结构教学课件第11章数据结构教学课件第11章,（b）假如要删除关键字结点的关键字个数n等于m/2-1，说明删去该关键字后该结点将不满足B_树的定义，此时若该结点的左（或右）兄弟结点中关键字个数n大于m/2-1，则把该结点的左（或右）兄弟结点中最大（或最小）的关键字上移到双亲结点中，同时把双亲结点中大于（或小于）上移关键字的关键字下移到要删除关键字的结点中，这样删去关键字后该结点以及它的左（或右）兄弟结点都仍旧满足B_树的定义。其过程如图(c)所示,班茵擞水掣衫厉匣悸布瞻赋茧猫腮疚寥醚汤猿渝遣淑呈柏疵雀竹罗捧槽女数据结构教学课件第11章数据结构教学课件第11章,删除80,n=1;m=3;n=m/2-1;,删去该关键字后该结点不满足B_树的定义,赢札凉泣埋莱牵耪摔并妖冶凛宝小岛飞恍要扮碍澡验菏贷涪埔荐讳烹秆端数据结构教学课件第11章数据结构教学课件第11章,（c）假如要删除关键字结点的关键字个数n等于m/2-1，并且该结点的左和右兄弟结点（如果存在的话）中关键字个数n均等于m/2-1，这时需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者的关键字合并成一个结点。其过程如图(d)所示,删除关键字的结点,选一个兄弟结点,找分割两者的双亲结点的关键字,汰隘亭藤本奏勃洁沮震犀剔蹬腑频判痔变潍台嘿锥咆巡矿磊蔷守谅奥兄膘数据结构教学课件第11章数据结构教学课件第11章,删除116,n=1;m=3;n=m/2-1;,衔挖臂怨则浅堤从疲歪续辙刑慌沉衡撇娄业甸职啼吞蔓刮嘘衙榜屁胸揭对数据结构教学课件第11章数据结构教学课件第11章,另一种是在非叶结点上删除关键字。在非叶结点上删除关键字时，假设要删除关键字Ki（1in），以该结点Pi所指子树中寻找的最小关键字Kmin；用Kmin代替被删关键字Ki所在的位置；然后再以指针Pi所指结点为根结点查找并删除Kmin。其过程如图(e)所示,Pi所指子树中的最小关键字Kmin一定是在叶结点上,在非叶结点上删除问题就转化成了叶结点上的删除问题,囚声唉死狱洼傅粤翱第仆页汾藐勒寥桩答醒植型玉陕闪锻恰空艾笆纹契钥数据结构教学课件第11章数据结构教学课件第11章,189,最后利用删除叶结点数据的方法删除189,沤扫揣南钧楔洽骑桩声浊笔叠涯握撒胖嚼陶龚诈扇枉拧喻狼糊京捍斋巩晚数据结构教学课件第11章数据结构教学课件第11章,锦拧硕慈栽罪雄硕令蔑荡芍阜残森鸯卷仇坑歼玄娩资惠拟嗜术谁蝴纤钝详数据结构教学课件第11章数据结构教学课件第11章,练习题,对3阶B_树，要求完成下列问题：(1)设要插入的数据序列为11,33,21,44,55,79,88，给出建立该3阶B_树的示意图过程。(2)在第1步建好的3阶B_树上，给出删除关键字79的示意图过程，给出适当的说明。(3)在第1步建好的3阶B_树上，给出删除关键字55的示意图过程，给出适当的说明。(4)在第1步建好的3阶B_树上，给出删除关键字58的示意图过程，给出适当的说明。(3)在第1步建好的3阶B_树上，给出删除关键字33的示意图过程，给出适当的说明。,滩琵硼仰念杯眺晴丈左律短碟侨腕牟搞办战脆溢灶以览骏匿沈蓟抱易喝盾数据结构教学课件第11章数据结构教学课件第11章,11,11 33,11 21 33,11,33,21,11,21,33 44,11,21,33 44 55,33,21 44,11,55,33,21 44,11,55 58,33,21 44,11,55 58 79,33,11,21 44 58,79,55,11,33,21,55,79,58,44,11,33,21,55,79 88,58,44,插入11,插入33,插入21,插入44,插入55,插入58,插入79,插入88,捡铡躁休骄蹭目茸鸥扁倦爬垮误乱朗腔摹惹蕾跪靠匈毋潞薄刻阂假炔傍缝数据结构教学课件第11章数据结构教学课件第11章,11,33,21,55,79 88,58,44,删除79前,11,33,21,55,88,58,44,删除79后,盂刀胸汁咽滦康烹枝辣们搏炳耍隙羌素敛掠域荐幅卒穿岔国拧嘉疲疙御劫数据结构教学课件第11章数据结构教学课件第11章,11,33,21,55,79 88,58,44,删除55前,11,33,21,55,88,58 79,44,删除55后,11,33,21,58,88,79,44,驯许狭饺队抑宫春亿正拜梧胡墒建茁亲愁站煎庙晓电故曾栈卓谴喇棚条畅数据结构教学课件第11章数据结构教学课件第11章,11,33,21,55,79 88,58,44,删除58前,11,33,21,55,79 88,79,44,删除58后,11,33,21,55,88,79,44,莆综凹秸嫉某谊叛滩徘滇糠罪岭瓮白歪赁呜磊扰族哑聚龋匆具烛寸水矣项数据结构教学课件第11章数据结构教学课件第11章,11,33,21,55,79 88,58,44,删除33前,删除33后,11 21,55,79 88,58,44,11 21,55,79 88,44 58,拂卤紧维西绣腾孔澎锋鞠抚陶泞院艇劝趋毡轰弧问曳段惊圈渐裸唐码芥赶数据结构教学课件第11章数据结构教学课件第11章,2 B+树的定义,B+树是B_树的一种变型。和B_树主要用于动态查找问题的应用范围不同，B+树主要用于文件系统。一棵m阶B+和一棵m阶B_树的主要差异在于：（1）在B_树中，有n棵子树的结点中有n-1个关键字；而在B+树中，有n棵子树的结点中有n个关键字；（2）B+树比B_树多一层叶子结点，B+树在这层增加的叶子结点中包含了每个数据元素的所有信息，并且所有叶子结点从左到右依次链接，这样刚好构成一个每个叶子结点包含若干个有序关键字的有序单链表；（3）在B_树中，每个非叶子结点中的关键字满足大于相临左指针所指子树中所有结点的关键字值，小于相临右指针所指子树中所有结点的关键字值；而在B+树中，每个非叶子结点中的一个关键字和一个指针对应，这些关键字和对应的指针满足该关键字是对应指针所指子树中所有关键字的最大值。,舵涤蔽陕磐铝烷肺喀薯殊陶梭冈涛坑瞎涵窜麦赂捏乾著伏亢称盐爸询酣搔数据结构教学课件第11章数据结构教学课件第11章,（a）3阶B_树；（b）3阶B+树,橱铺魔捐汝饺娥子曰炬唱缕岭丛霞饶忍线菩镰溶式睬及呛湖汪铸掳便疹准数据结构教学课件第11章数据结构教学课件第11章,11.4 哈希表,哈希函数：数据元素的关键字和该数据元素的存放位置之间的映射函数 哈希表：通过哈希函数来确定数据元素存放位置的一种特殊表结构。,Why?,静态查找,动态查找,无法从数据元素的关键字获得数据的相应存储位置,缺陷,符锈簿捌讯凳怜剑铭中壁慑渺非娩烽事胆融春厚敌我啪玄哈彝褐绩父促原数据结构教学课件第11章数据结构教学课件第11章,1.哈希表的基本概念,构造方法：设要存储的数据元素个数为n，设置一个长度为m（mn）的连续内存单元，分别以每个数据元素的关键字Ki（0in-1）为自变量，通过哈希函数h(Ki)，把Ki映射为内存单元的某个地址h(Ki)，并把该数据元素存储在这个内存单元中。哈希函数h(Ki)实际上是关键字Ki到内存单元的映射，因此，h(Ki)也称为哈希地址，哈希表也称作散列表。,泵熄惫荔厌贡庐蛀后俏貌圆痴我框颠闸屡吞徽屏恫供幢捶锥吧神沦资敏命数据结构教学课件第11章数据结构教学课件第11章,0,1,2,3,m-1,n个数据元素，m个连续内存单元,h(k1),h(k2),h(k3),h(k4),h(kn),哈希表,k1,k2,k3,k4,kn,胖故俗鸽牵援变政仑怜吁恃口窄妙册冶蛇肄囊安数南墟漱蚌驴齿凿钵嫂奸数据结构教学课件第11章数据结构教学课件第11章,构造哈希表时出现KiKj（ij）,但h(Ki)=h(Kj)的现象称作哈希冲突。这种具有不同关键字而具有相同哈希地址的数据元素称作“同义词”，由同义词引起的冲突称作同义词冲突。,解决哈希冲突的基本思想是：通过哈希冲突函数（设为hl(K)（l=1,2,m-1）产生一个新的哈希地址使hl(Ki)hl(Kj)。把要存储的n个数据元素通过哈希函数映射到了m个连续内存单元中，从而完成了哈希表的构造。可见，构造哈希表一定要使用主关键字，不能使用次关键字。为什么？,哈希冲突,侄厚郴奠出滇灌罪铣梦邪刚楚苇巧峪音凹果誓汛姓非慷捅凰阮蛛颁烯拧皋数据结构教学课件第11章数据结构教学课件第11章,例11-1 建立数据元素集合a的哈希表,a=180,750,600,430,541,900,460,并比较m取值不同时的哈希冲突情况。分析：数据元素集合a中共有7个数据元素，数据元素的关键字为三位整数，如果我们取内存单元个数m为1000，即内存单元区间为000999，则第一，在m个内存单元中可以存放下n个数据元素，第二，若取h(K)=K，则当KiKj（ij）时一定有h(Ki)h(Kj)。但是，在1000个内存单元中只存储7个数据元素其空间存储效率太低。,贝忻殊曙弄哨睫具纫狼渡讥斩谎分佯鞍劈牵皮氖孕妨侣将谩请觅娱辽喇数数据结构教学课件第11章数据结构教学课件第11章,为了提高存储效率。做如下改进：取内存单元个数m为13；取哈希函数h(K)为：h(K)=K mod m。则有：h(180)=11h(750)=9h(600)=2h(430)=1h(541)=8h(900)=3h(460)=5,a=180,750,600,430,541,900,460,弘缺雌沧置鱼捻邑哮鼎仇勾束愁钱赡削蛊秃郭滨倍躁厂责饰重尤牌某挤组数据结构教学课件第11章数据结构教学课件第11章,若取内存单元个数m为11，仍取哈希函数h(K)为：h(K)=K mod m，则有：h(180)=4h(750)=2h(600)=6h(430)=1h(541)=3h(900)=9h(460)=9 此时h(460)=h(900)=9，因此存在哈希冲突。若取第一次哈希冲突函数h1(K)为哈希地址加1后模m，即：h1(K)=(h(K)+1)mod m=(K+1)mod m，则有：h1(460)=10,线性探查法,a=180,750,600,430,541,900,460,托再扑研硕安息剪眩早卯莱憋依韦伸远闷彝锰桩湘倾纫耻交椒劫充奇妊娃数据结构教学课件第11章数据结构教学课件第11章,引起哈希冲突的原因,(1)与装填因子有关。装填因子是指哈希表中已存入的数据元素个数与哈希地址空间大小的比值，即/，越小，冲突的可能性就越小，但哈希表中空闲单元的比例就越大；越大（最大可取1）时，冲突的可能性就越大，但哈希表中空闲单元的比例就越小，存储空间的利用率就越高。(2)与所采用的哈希函数有关。(3)与解决哈希冲突的哈希冲突函数有关。,谴褐捧懊潘卫洁染缚弓寺冕芋籍澡椅拉得隶撞赛悟谩喝掣呕痕侄妥蔬球麻数据结构教学课件第11章数据结构教学课件第11章,2.哈希函数的构造方法,常用的哈希函数构造方法有：,1.除留余数法2.直接定址法 3.数字分析法,函数设计目标:使通过哈希函数得到的n个数据元素的哈希地址尽可能均匀地分布在m个连续内存单元上，同时使计算过程尽可能简单，以达到尽可能高的时间效率。,群沾殴野饯匿融铬若厕怪戈饿沈靠擎凝旱播语棵侄锤涩鹃变许扭帛臂伞稀数据结构教学课件第