《数据结构课程的内容课件》由会员分享，可在线阅读，更多相关《数据结构课程的内容课件（28页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程的内容酥蛊揭句叙菏积金孰莽叶赞佬嘿觉虹亨亚翔谱桶室界衬泻恃惨颂手纂洪诀数据结构课程的内容课件数据结构课程的内容课件18.1 8.1 基本概念基本概念8.2 8.2 静态查找表静态查找表8.8.3 3 动态查找表动态查找表8.4 8.4 哈希表哈希表第8章 查找教材第教材第8 8、1111和和1212章省略，因操作系统课程会涉及。章省略，因操作系统课程会涉及。纠勇镁闺鸡撅跋磨淖蕊针元棘翰靴撤夫柄突嘲整趁腹栗蚂揭刺粗岭甭宝指数据结构课程的内容课件数据结构课程的内容课件28.1 基本概念若表中存在特定元素，称查找成功，应输出该记录；若表中存在特定元素，称查找成功，应输出该记录；否则，称查
2、找不成功（也应输出失败标志或失败位置）否则，称查找不成功（也应输出失败标志或失败位置）查找表查找表 查查 找找查找成功查找成功查找不成功查找不成功静态查找静态查找动态查找动态查找关键字关键字主关键字主关键字次关键字次关键字由同一类型的数据元素（或记录）构成的集合。由同一类型的数据元素（或记录）构成的集合。查询查询(Searching)特定元素特定元素是否在表中。是否在表中。只查找，不改变集合内的数据元素。只查找，不改变集合内的数据元素。既查找，又改变集合内的数据元素。既查找，又改变集合内的数据元素。记录中某个数据项的值，可用来识别一个记录记录中某个数据项的值，可用来识别一个记录 ( 预先确定的
3、记录的某种标志预先确定的记录的某种标志 ) 可以可以唯一唯一标识一个记录的关键字标识一个记录的关键字例如例如“学号学号”例如例如“女女”是一种数据结构是一种数据结构识别若干记录的关键字识别若干记录的关键字蓟显坠暇陀守微智貌壕减屿水定搬犊饲胚垛映瘴云惠勺卤文霖城魁绎淬激数据结构课程的内容课件数据结构课程的内容课件3（2）对查找表常用的操作有）对查找表常用的操作有哪些？哪些？ v查询某个查询某个“特定的特定的”数据元素是否在表中；数据元素是否在表中；v查询某个查询某个“特定的特定的”数据元素的各种属性；数据元素的各种属性；v在查找表中插入一元素；在查找表中插入一元素；v从查找表中删除一元素。从查找
4、表中删除一元素。 （3) 有哪些查找方法？有哪些查找方法？ 查找方法取决于表中数据的排列方式查找方法取决于表中数据的排列方式;讨论：讨论：（1）查找的过程是怎样的？）查找的过程是怎样的？ 给定一个值给定一个值K K，在含有，在含有n n个记录的文件中进行搜索，寻找个记录的文件中进行搜索，寻找一个关键字值等于一个关键字值等于K K的记录，如找到则输出该记录，否则输出的记录，如找到则输出该记录，否则输出查找不成功的信息。查找不成功的信息。例如查字典例如查字典针对静态查找表和动态查找表的查找方法也有所不同针对静态查找表和动态查找表的查找方法也有所不同。“特定的特定的”=关键关键字字汁森抡嫉檬渣逃应棠
5、踏陶靛翁批圭凋邦咯群瘤默边骗阴札蛇谨徘昨傀绷宙数据结构课程的内容课件数据结构课程的内容课件4（4 4）如何评估查找方法的优劣？）如何评估查找方法的优劣？明确：明确：查找的过程就是将给定的查找的过程就是将给定的K K值与文件中各记录的关键字值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为劣。称为平均查找长度平均查找长度（ASLASL：average search lengthaverage search length）。）。其中：其中：n n是文件记录个数；是文件记录个数；P Pi i是查找第是查找第i
6、i个记录的查找概率（通常取等概率个记录的查找概率（通常取等概率, ,即即P Pi i =1/n =1/n）; ;C Ci i是找到第是找到第i i个记录时所经历的比较次数。个记录时所经历的比较次数。统计意义上的统计意义上的数学期望值数学期望值物理意义：物理意义：假设每一元素被查找的概率相同，则查找每假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为一元素所需的比较次数之总和再取平均，即为ASLASL。显然，显然，ASLASL值越小，时间效率越高。值越小，时间效率越高。 祈斌仁童彪秒领咽质谍浚臣奄岁嘱士布控崭悄帜暮社哥凌诅返延顽雹晰樊数据结构课程的内容课件数据结构课程
7、的内容课件5针对静态查找表的查找算法主要有：针对静态查找表的查找算法主要有： 8.2 静态查找表静态查找表的抽象数据类型参见教材静态查找表的抽象数据类型参见教材P216。一、一、顺序查找（线性查找）顺序查找（线性查找）二、二、折半查找（二分或对分查找）折半查找（二分或对分查找）三、三、静态树表的查找静态树表的查找四、四、分块查找（索引顺序查找）分块查找（索引顺序查找）激拄惦了侦刨耐钝溶惫刺末积斥铀盈到揭尔潍挪驮岿砸舞科讳绅捏钳惕莆数据结构课程的内容课件数据结构课程的内容课件6一、顺序查找（一、顺序查找（ Linear searchLinear search，又称线性查找又称线性查找 ）（1）顺
8、序表的机内存储结构：顺序表的机内存储结构：typedef struct ElemType *elem; /表基址，表基址，0 0号单元留空。表容量为全部元素号单元留空。表容量为全部元素 int length; /表长，即表中数据元素个数表长，即表中数据元素个数SSTable;顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。直接的办法。 v对对顺序结构顺序结构如何线性查找？如何线性查找？见下页之例见下页之例或教材或教材P216P216；v对对单单链链表表结结构构如如何何线线性性查查找找？函函数数虽虽未未给给出出，但但也也很很
9、容容易易编写；只要知道头指针编写；只要知道头指针headhead就可以就可以“顺藤摸瓜顺藤摸瓜”；v对对非线性树结构非线性树结构如何顺序查找如何顺序查找? ?可借助各种遍历操作！可借助各种遍历操作！蛋铜栏你溢阿撵嫂盔酱则叼吗巡钢龋访低哀讲杭账割傍躇蕊三构斌首揽没数据结构课程的内容课件数据结构课程的内容课件7（2 2）算法的实现：算法的实现：技巧：技巧：把待查关键字把待查关键字keykey存入表头或表尾（俗称存入表头或表尾（俗称“哨兵哨兵”），），这样可以加快执行速度。这样可以加快执行速度。例：例：若将待查找的特定值若将待查找的特定值keykey存入存入顺序表的顺序表的首部首部（如（如0 0号单
10、元）号单元），则顺序查找的实现方案为：，则顺序查找的实现方案为：从后向前从后向前逐个比较！逐个比较！int Search_Seq( SSTable ST , KeyType key ) /在顺序表在顺序表STST中，查找关键字与中，查找关键字与keykey相同的元素；若成功，返回其位相同的元素；若成功，返回其位置信息，否则返回置信息，否则返回0 0 ST.elem0.key =key; /设立哨兵，可免去查找过程中每一步设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当都要检测是否查找完毕。当n1000n1000时，查找时间将减少一半。时，查找时间将减少一半。 for( i=ST.len
11、gth; ST.elem i .key!=key; - - i ); /不要用不要用for(i=n; i0; - -i) for(i=n; i0; - -i) 或或 for(i=1; i=n; i+) for(i=1; i=n; i+) return i; /若到达若到达0 0号单元才结束循环，说明不成功，返回号单元才结束循环，说明不成功，返回0 0值值(i=0)(i=0)。成功时则返回找到的那个元素的位置。成功时则返回找到的那个元素的位置i i。 / Search_Seq耘麓摧螺淫跳忘搪持窄餐疑诵敖沮狸确叁免廓煎怕邹从斗箔猩浪牛嫩莎还数据结构课程的内容课件数据结构课程的内容课件8返回特殊标志
12、，例如返回空记录或空指针。前例中设立了返回特殊标志，例如返回空记录或空指针。前例中设立了“哨哨兵兵”，就是将关键字送入末地址，就是将关键字送入末地址ST.elemST.elem0 0.key.key使之结束并返回使之结束并返回 i=0i=0。讨论讨论 查找效率怎样计算？查找效率怎样计算？用平均查找长度用平均查找长度ASL衡量。衡量。讨论讨论 查不到怎么办？查不到怎么办？讨论讨论 如何计算如何计算ASL？分析：分析：查找第查找第1个元素所需的比较次数为个元素所需的比较次数为1；查找第查找第2个元素所需的比较次数为个元素所需的比较次数为2；查找第查找第n个元素所需的比较次数为个元素所需的比较次数为
13、n；总计全部比较次数为：总计全部比较次数为：12n = (1+n)n/2未考虑查找不成功的未考虑查找不成功的情况：查找哨兵所需情况：查找哨兵所需的比较次数为的比较次数为n+1n+1这是查找成功的情况这是查找成功的情况若求某一个元素的平均查找次数，还应当除以若求某一个元素的平均查找次数，还应当除以n（等概率），（等概率），即：即： ASL（1n）/2 ，时间效率为，时间效率为 O(n)思考不成功的计算思考不成功的计算叠挟时晨钱众蔗奢婿彻株来凋镰跨哮限嫉绑瑚壹固臂搅工蜗苟铰勤半往燥数据结构课程的内容课件数据结构课程的内容课件9二、折半查找（又称二分查找或对分查找）二、折半查找（又称二分查找或对分查
14、找）优点：优点：算法简单，且对顺序结构或链表结构均适用。算法简单，且对顺序结构或链表结构均适用。缺点：缺点： ASL 太长，时间效率太低。太长，时间效率太低。这是一种容易想到的查找方法。这是一种容易想到的查找方法。先给数据排序先给数据排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再将，然后再将keykey与正中元素相比，若与正中元素相比，若keykey小，则缩小至左半部内查找；再取其中小，则缩小至左半部内查找；再取其中值比较，每次缩小值比较，每次缩小1/21/2的范围，直到查找成功或失败为止。的范围，直到查找成功或失败为止。v对对顺序表结构顺序表结构如何编程实现折半查找
15、算法？如何编程实现折半查找算法？ 见下页之例见下页之例，或见教材（，或见教材（P219P219）v对对单链表结构单链表结构如何折半查找？如何折半查找？ 无法实现！无法实现！因全部元素的定位只能从头指针因全部元素的定位只能从头指针headhead开始开始v对对非线性非线性(树树)结构结构如何折半查找？如何折半查找？ 可借助二叉排序树来查找（属动态查找表形式）。可借助二叉排序树来查找（属动态查找表形式）。 如何改进如何改进？讨论讨论 顺序查找的特点：顺序查找的特点：荆谢救声砂窟批费农用缀酥见膳彝辐厩楚啸组款学堰雄牢很闭学礁智细脖数据结构课程的内容课件数据结构课程的内容课件10 运算步骤运算步骤：(
16、1) low =1,high =11 ,mid =6 (1) low =1,high =11 ,mid =6 ，待查范围是，待查范围是 1,11 1,11；(2) (2) 若若 ST.elemmid.key ST.elemmid.key key keykey，说明，说明keykey low ,midlow ,mid-1-1 ， 则令：则令：high =mid1high =mid1; ;重算重算 mid mid ；(4)(4)若若 ST.elem mid .key ST.elem mid .key = key= key，说明查找成功，元素序号，说明查找成功，元素序号=mid;=mid;结束条件：
17、结束条件： （1 1）查找成功）查找成功 ： ST.elemmid.key = key ST.elemmid.key = key （2 2）查找不成功）查找不成功 ： highlowhighlow （意即区间长度小于（意即区间长度小于0 0）解：解： 先设定先设定3个辅助标志个辅助标志: low,high,midlow,high,mid，折半查找举例：折半查找举例：LowLow指向待查元素指向待查元素所在区间的下界所在区间的下界highhigh指向待查元素所指向待查元素所在区间的上界在区间的上界midmid指向待查元素所在指向待查元素所在区间的中间位置区间的中间位置 已知如下已知如下11个元素
18、的个元素的有序表有序表：（05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为请查找关键字为21 和和85的数据元素。的数据元素。显然有：显然有：mid= (low+high)/2 此例作为自测的算法题之一，建议上机验证。此例作为自测的算法题之一，建议上机验证。此例作为自测的算法题之一，建议上机验证。此例作为自测的算法题之一，建议上机验证。霹枷句遗讹牙障笼客淡藕殖斜绿逢炉禄薛口肥距铸权模怯拱爱谈肢吮呵概数据结构课程的内容课件数据结构课程的内容课件11讨论讨论 若关键字不在表中，怎样得知何时停止？若关键字不在表中，怎样得知何时停止？典型标志是：当查找范围的上界典型
19、标志是：当查找范围的上界下界时停止查找。下界时停止查找。讨论讨论 二分查找的效率（二分查找的效率（ASLASL）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
20、-1）个个；为方便起见，假设表中全部为方便起见，假设表中全部n个元素个元素 2m-1个，个，此时就不讨论第此时就不讨论第m次比较后还有剩余元素的情况了。次比较后还有剩余元素的情况了。全部比较总次数为全部比较总次数为120221322423m2m1 推推导导过过程程滞滑也滔揣庄鳞娃耽峙钢禹疲试持碑梧疵库畏舞狞轻摄慕鸿秽制峭骑陌涝数据结构课程的内容课件数据结构课程的内容课件12平均每个数据的查找时间还要除以平均每个数据的查找时间还要除以n n，所以：，所以：（详细推导过程见教材（详细推导过程见教材P221的附录）的附录）课堂练习课堂练习（多项选择）：（多项选择）：采用链式存贮结构采用链式存贮结构
21、记录的长度记录的长度128 采用顺序存贮结构采用顺序存贮结构 记录按关键字递增有序记录按关键字递增有序使用折半查找算法时，要求被查文件：使用折半查找算法时，要求被查文件：思考：思考：假设在有序线性表假设在有序线性表a20上进行折半查找，则上进行折半查找，则平均查找长度为平均查找长度为 。鳖篱穆皇哄人宾贵葵遍己药题霄跌藤近甄获钒憋脑残距贯琳弟硅志差敲伎数据结构课程的内容课件数据结构课程的内容课件13查找过程可用查找过程可用二叉树二叉树描述：每个记录用一个结点表示；结点中值为描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树。该记录在表中位置，这个描述查找
22、过程的二叉树称为判定树。n个元个元素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。决定。 找到有序表中任一记录的过程就是找到有序表中任一记录的过程就是：走了一条从根结点到与该记录：走了一条从根结点到与该记录相应的结点的路径。相应的结点的路径。 比较的关键字个数：比较的关键字个数：为该结点在判定树上的层次数。为该结点在判定树上的层次数。 查找成功时查找成功时比较的关键字个数最多不超过树的深度比较的关键字个数最多不超过树的深度 d : d = log2 n + 1 若所有结点的空指针域设置为一个指向一个方形结点的指针，称若所
23、有结点的空指针域设置为一个指向一个方形结点的指针，称方形结点为判定树的外部结点；对应的，圆形结点为内部结点。方形结点为判定树的外部结点；对应的，圆形结点为内部结点。 查找不成功的过程查找不成功的过程 就是走了一条从根结点到外部结点的路径。就是走了一条从根结点到外部结点的路径。做习题做习题新建新建 Microsoft Word 文档文档.doc折半查找效率分析法折半查找效率分析法2 2（参见教材（参见教材P220P220）：）：距舆誓汝烩误积擎适逸沤稻谱澈闸符仑萨葛镜账泳匡筑涅捻胖薛耪敞豢液数据结构课程的内容课件数据结构课程的内容课件14三、静态树表的查找三、静态树表的查找讨论讨论2：当有序表中
24、各记录的当有序表中各记录的查找概率不相等查找概率不相等时，该如何查？时，该如何查？首先要明确，此时首先要明确，此时用折半查找法未必最优用折半查找法未必最优！（参见教材（参见教材P222例）例）改进：改进：若将各记录概率看作是二叉树之权值，则转为研究带若将各记录概率看作是二叉树之权值，则转为研究带权路径长度最小的二叉树（类似最优二叉树）。权路径长度最小的二叉树（类似最优二叉树）。讨论讨论1：对对有序表有序表还有其他查找算法吗？还有其他查找算法吗？静态最优查找树算法静态最优查找树算法时间代价高；时间代价高；实用算法：实用算法：近似最优查找树（近似最优查找树（次优次优查找树）查找树） （参见教材（参
25、见教材P222225）有，如斐波那契查找和插值查找等有，如斐波那契查找和插值查找等（参见教材（参见教材P221222）花肇稀惜盔劫颈喧矾索营粥踞隆睁碧的绊亚押财宠牡闷桥扔疹谋垂躬齐低数据结构课程的内容课件数据结构课程的内容课件15四、分块查找（索引顺序查找）四、分块查找（索引顺序查找）这是一种顺序查找的另一种改进方法。这是一种顺序查找的另一种改进方法。先让数据先让数据分块有序分块有序，即分成若干子表，要求每个子表中的数，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。有序）。然后将各子表中的最
26、大关键字构成一个然后将各子表中的最大关键字构成一个索引表索引表，表中还要包，表中还要包含每个子表的起始地址（即头指针）。含每个子表的起始地址（即头指针）。索引表索引表最大关键字起始地址2222121213138 89 92020333342424444383824244848606058587474494986865353第第1 1块块第第2 2块块第第3 3块块224886例：例：2222484886861 17 71313特点：块间有特点：块间有序，块内无序序，块内无序埃川治怯务吞慰背姜耸冒裸捅消厦沁疟牛阑嚏臭匣雨踪或挛笋佯破届塑吻数据结构课程的内容课件数据结构课程的内容课件16查找步骤查
27、找步骤分两步进行：分两步进行： 对索引表使用折半查找法（因为索引表是有序表）；对索引表使用折半查找法（因为索引表是有序表）； 确定了待查关键字所在的子表后，在子表内采用顺序确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；查找法（因为各子表内部是无序表）；查找效率：查找效率：ASL=LASL=Lb b+L+Lw w对索引表查找的对索引表查找的ASL对块内查找的对块内查找的ASLS为每块内部的记录个数，为每块内部的记录个数，n/s即块的数目即块的数目例如当例如当n=9n=9，s=3s=3时时，ASLASLbsbs= =3.53.5, ,而折半法为而折半法为3.13.
28、1, ,顺序法为顺序法为5 5切焚跌馋辊解颇监栗溪圭体茁偷襄见戌逐葡刽哥化贰约航谅追祟刑辱凤迪数据结构课程的内容课件数据结构课程的内容课件17n习题n 要进行线性查找，则线性表要进行线性查找，则线性表 A ；要进行二分查找，则；要进行二分查找，则线性表线性表 B ；要进行散列查找，则线性表；要进行散列查找，则线性表 C 。顺序存储。顺序存储的表格，其中有的表格，其中有90000个元素，已按关键项的值的上升顺个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找且各个元素
29、的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为时，平均比较次数约为 D ，最大比较次数为，最大比较次数为 E 。 供选择的答案供选择的答案：AC： 必须以顺序方式存储必须以顺序方式存储 必须以链表方式存储必须以链表方式存储 必须以散列方式存储必须以散列方式存储 既可以以顺序方式，也可以既可以以顺序方式，也可以以链表方式存储以链表方式存储 必须以顺序方式存储且数据元素已必须以顺序方式存储且数据元素已按值递增或递减的次序排好按值递增或递减的次序排好 必须以链表方式存储且必须以链表方式存储且数据元素已按值递增或递减的次序排好数据元素已按值递增或递减的次序排好D，E： 25000 300
30、00 45000 90000n答案： A= B= C= D E 或庙匈艘萝蔫那胜猖反莱贴成彭塑蝴屈嘛草莆悍奸细瞪忙本专要翟湍豺杨数据结构课程的内容课件数据结构课程的内容课件18特点：特点：一、一、二叉排序树的定义二叉排序树的定义二、二、二叉排序树的插入与删除二叉排序树的插入与删除三、三、二叉排序树的查找分析二叉排序树的查找分析四、平衡二叉树四、平衡二叉树8.2 8.2 动态查找表动态查找表表结构在查找过程中动态生成。表结构在查找过程中动态生成。要求：要求： 对于给定值对于给定值key,key,若表中存在其关键字等于若表中存在其关键字等于keykey的记录，则查找成功返回；的记录，则查找成功返回
31、；否则插入关键字等于否则插入关键字等于否则插入关键字等于否则插入关键字等于key key key key 的记录。的记录。的记录。的记录。典型的动态表典型的动态表二叉排序树二叉排序树撵楞具蓬厕酞李斟醛牺哪吏握垒突再勤凶婪锐泪汪益赦擅麓邱维垦朱呼畴数据结构课程的内容课件数据结构课程的内容课件19一、一、二叉排序树的定义二叉排序树的定义（a）（b）练：练：下列下列2种图形中，哪个不是二叉排序树种图形中，哪个不是二叉排序树 ？-或是一棵空树；或者是具有如下性质的非空二叉树：或是一棵空树；或者是具有如下性质的非空二叉树： （1 1）左子树的所有结点均小于根的值；）左子树的所有结点均小于根的值； （2
32、2）右子树的所有结点均大于根的值；）右子树的所有结点均大于根的值； （3 3）它的左右子树也分别为二叉排序树。）它的左右子树也分别为二叉排序树。悄禹劳傣述酉略劈盟治键滓铂豹油伺入穷氮译费帅坎靖蛰诲逸焚烤徒痢背数据结构课程的内容课件数据结构课程的内容课件20二、二叉排序树的插入与删除二、二叉排序树的插入与删除将数据元素构造成二叉排序树的优点：将数据元素构造成二叉排序树的优点： 查找过程与顺序结构有序表中的查找过程与顺序结构有序表中的折半查找折半查找相似，查找效率高；相似，查找效率高； 中序遍历中序遍历此二叉树，将会得到一个关键字的有序序列（此二叉树，将会得到一个关键字的有序序列（即实现即实现了排
33、序运算了排序运算）；）； 如果查找不成功，能够方便地将被查元素如果查找不成功，能够方便地将被查元素插入到二叉树的叶子插入到二叉树的叶子结点结点上，而且插入或删除时只需修改指针而不需移动元素。上，而且插入或删除时只需修改指针而不需移动元素。注：注：若若数据元素的数据元素的输入顺序不同，则得到的二叉排序树形态输入顺序不同，则得到的二叉排序树形态也不同！也不同！这种既查找又插入的过程称为这种既查找又插入的过程称为动态查找动态查找。二叉排序树既有类似于折半查找的特性，又采用了链表存储，二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。它是动态查找表的一种适宜表示。芋慢
34、丁撮记蚁按董甫烙恍木绎俗剁袒黑榆挝棺获褂祝鄂椽酉举纺警蠢家钦数据结构课程的内容课件数据结构课程的内容课件2145452424535312129090如果待如果待查找的关键字序列输入顺序为：查找的关键字序列输入顺序为：（2424，5353， 45 45，4545，1212，2424，9090），），24245353454512129090查查找找成成功，功，返返回回查查找找成成功，功，返返回回讨论讨论1 1：二叉排序树的插入和查找操作：二叉排序树的插入和查找操作 则生成二叉排序则生成二叉排序树的过程为：树的过程为：例例：输入待查找的关键字序列输入待查找的关键字序列= =（4545，2424，53
35、53，4545，1212，2424，9090）则生成的二叉排则生成的二叉排序树形态不同：序树形态不同：查查找找成成功，功，返返回回查查找找成成功，功，返返回回瞳渺奥寄迈琼梢雹遭芭秀版裔孵豁茄鳃剁癸撕波歪葫民鸣诱意郑宠掷肚齿数据结构课程的内容课件数据结构课程的内容课件22二叉排序树的查找二叉排序树的查找&插入算法如何实现？插入算法如何实现？查找算法查找算法参见教材参见教材P228算法算法9.5（a,b）;插入算法插入算法参见教材参见教材P228算法算法9.6;赶亦帚涯前浑击敷坞斗符狞赛另局颈梦音尖坏霄点狡继凋泡央案遵病氦埃数据结构课程的内容课件数据结构课程的内容课件23对于二叉排序树，删除树上一
36、个结点相当于删除有序序列中对于二叉排序树，删除树上一个结点相当于删除有序序列中的一个记录，删除后仍需保持二叉排序树的特性。的一个记录，删除后仍需保持二叉排序树的特性。（对链表进行删除操作是很方便的）（对链表进行删除操作是很方便的）讨论讨论2 2：二叉排序树的删除操作：二叉排序树的删除操作如何删除一个结点？如何删除一个结点？假设：假设：*p*p表示被删结点的指针；表示被删结点的指针； P PL和和PR 分别表示分别表示*P*P的左、右孩子指针；的左、右孩子指针；*f*f表示表示*p*p的双亲结点指针；并假定的双亲结点指针；并假定*p*p是是*f*f的的左孩子左孩子；则可能有三种情况：；则可能有三
37、种情况：PR 为为 * S * S 的右子树；的右子树； S SL 为为 Q（ * S * S的双亲结点）右孩子的双亲结点）右孩子*p*p为叶子：为叶子： 删除此结点时，直接修改删除此结点时，直接修改*f*f指针域即可；指针域即可；*p*p只有一棵子树（或左或右）：只有一棵子树（或左或右）：令令P PL或或PR为为*f*f的左孩子即可；的左孩子即可；*p*p有两棵子树：情况最复杂有两棵子树：情况最复杂 鸡羔竞熄扮芥至迈防懒眨肾赚饰恿齿砖康挽玫鹅怒径叉互叼足毯澜谭燃粪数据结构课程的内容课件数据结构课程的内容课件24*p*p有两棵子树时，如何进行删除操作？有两棵子树时，如何进行删除操作？分析：分析
38、：设删除前的中序遍历序列为：设删除前的中序遍历序列为：. s p PR . /显然显然显然显然p p p p的直接前驱是的直接前驱是的直接前驱是的直接前驱是s s s s希望删除希望删除p p后，其它元素的相对位置不变。有两种解决方法：后，其它元素的相对位置不变。有两种解决方法：法法1 1：令令*p*p的左子树为的左子树为 *f*f的左子树，的左子树，*p*p的右子树为的右子树为*s*s的右子的右子树；树； /即即即即F FL L=P=PL L ; F; FR R=P=PR R ; ;法法2 2：令令*s*s代替代替*p *p / *s*s*s*s为为为为*p*p*p*p左子树最右下的叶子左子
39、树最右下的叶子左子树最右下的叶子左子树最右下的叶子蝎检步痞您粱徐却庶宋板解觅忧然砧蝇佣逞匡嘉刁藉敛或浇居皑乌继慨炼数据结构课程的内容课件数据结构课程的内容课件25F FC CCLS SSLQLPPRQPRF FC CCLS SSLQLPPRQ法法2:2:：令令*s代替代替*p F FC CCLS SSLQLPPRQ法法1:1:令令*p的左子树的左子树为为 *f的左子树，的左子树，*p的的右子树为右子树为*s的右子树；的右子树；例：例：请从下面的二叉排序树中删除结点请从下面的二叉排序树中删除结点P P。S SSL舍误指镀殉翻醚盆厨凤腹煞揩仙撤闰闰绵虏悉渔阻曝硝矽多疵缕毖民骆悔数据结构课程的内容课
40、件数据结构课程的内容课件261) 1) 二叉排序树上查找某关键字等于给定值的结点过程，其实二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。就是走了一条从根到该结点的路径。 比较的关键字次数比较的关键字次数此结点的层次数此结点的层次数; ; 最多的比较次数最多的比较次数树的深度（或高度），即树的深度（或高度），即 loglog2 2 n n +1+12) 2) 一棵二叉排序树的平均查找长度为：一棵二叉排序树的平均查找长度为： 三、二叉排序树的查找分析三、二叉排序树的查找分析其中：其中：n ni i 是每层结点个数；是每层结点个数； C Ci i 是结点所在层次数
41、；是结点所在层次数；m m 为树深。为树深。最坏情况：最坏情况：即插入的即插入的n个元素从一开始就有序，个元素从一开始就有序， 变成单支树的形态！变成单支树的形态！ 此时树的深度为此时树的深度为n ; ASL= (n+1)/2 此时查找效率与顺序查找情况相同。此时查找效率与顺序查找情况相同。强嫩彬货动治吼穗减睡铲畏扩甥锁钱聊狗舶音屎您傈党砚耪伯跑苹跟箍付数据结构课程的内容课件数据结构课程的内容课件27最好情况：最好情况：即：与折半查找中的判定树相同（形态比较均衡）即：与折半查找中的判定树相同（形态比较均衡）3）对有）对有 n 个关键字的二叉排序树的平均查找长度个关键字的二叉排序树的平均查找长度: 设每种树态出现概率相设每种树态出现概率相 同同 ，查找每个关键字也是等概率的。，查找每个关键字也是等概率的。则则ASL求解过程可推导。求解过程可推导。 （详见教材（详见教材P232）树的深度为：树的深度为： log 2n +1 ；ASL=log 2(n+1) 1 ；与折半查找相同。；与折半查找相同。结论：二叉排序树的结论：二叉排序树的ASL2（11/n）ln n搬库耘串起队翘借朵电蛰懒错挛辐帘滨疫藉呼纬托咎媒赫秽搬幻沪签折蛰数据结构课程的内容课件数据结构课程的内容课件28
