数据结构课程内容讲义28.1 8.1 基本概念基本概念8.2 8.2 静态查找表静态查找表8.3 8.3 动态查找表动态查找表8.4 8.4 第8章 查找教材第教材第8 8、1111和和1212章省略，因章省略，因操作系统操作系统课程会涉及。课程会涉及。38.1 基本概念若表中存在特定元素，称查找成功，应输出该记录；若表中存在特定元素，称查找成功，应输出该记录；否则，称查找不成功（也应输出失败标志或失败位置）否则，称查找不成功（也应输出失败标志或失败位置）查找表查找表 查查 找找查找成功查找成功查找不成功查找不成功静态查找静态查找动态查找动态查找关键字关键字主关键字主关键字次关键字次关键字由同一类型的数据元素（或记录）构成的集合。由同一类型的数据元素（或记录）构成的集合。查询查询(Searching)特定元素是否在表中。特定元素是否在表中。只查找，不改变集合内的数据元素。只查找，不改变集合内的数据元素。既查找，又改变集合内的数据元素。既查找，又改变集合内的数据元素。记录中某个数据项的值，可用来识别一个记录记录中某个数据项的值，可用来识别一个记录 ( 预先确定的记录的某种标志预先确定的记录的某种标志 ) 可以唯一标识一个记录的关键字可以唯一标识一个记录的关键字例如例如“学号学号”例如例如“女女”是一种数据结构是一种数据结构识别若干记录的关键字识别若干记录的关键字4（2）对查找表常用的操作有）对查找表常用的操作有哪些？哪些？ v查询某个查询某个“特定的特定的”数据元素是否在表中；数据元素是否在表中；v查询某个查询某个“特定的特定的”数据元素的各种属性；数据元素的各种属性；v在查找表中插入一元素；在查找表中插入一元素；v从查找表中删除一元素。从查找表中删除一元素。 （3) 有哪些查找方法？有哪些查找方法？ 查找方法取决于表中数据的排列方式查找方法取决于表中数据的排列方式;讨论：讨论：（1）查找的过程是怎样的？）查找的过程是怎样的？ 给定一个值给定一个值K K，在含有，在含有n n个记录的文件中进行搜索，寻找个记录的文件中进行搜索，寻找一个关键字值等于一个关键字值等于K K的记录，如找到则输出该记录，否则输出的记录，如找到则输出该记录，否则输出查找不成功的信息。查找不成功的信息。例如查字典例如查字典针对静态查找表和动态查找表的查找方法也有所不同。针对静态查找表和动态查找表的查找方法也有所不同。“特定的特定的”=关键关键字字5（4 4）如何评估查找方法的优劣？）如何评估查找方法的优劣？明确：明确：查找的过程就是将给定的查找的过程就是将给定的K K值与文件中各记录的关键字值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（劣。称为平均查找长度（ASLASL：average search lengthaverage search length）。）。其中：其中：n n是文件记录个数；是文件记录个数；P Pi i是查找第是查找第i i个记录的查找概率（通常取等概率个记录的查找概率（通常取等概率, ,即即P Pi i =1/n =1/n）; ;C Ci i是找到第是找到第i i个记录时所经历的比较次数。个记录时所经历的比较次数。统计意义上的统计意义上的数学期望值数学期望值物理意义：物理意义：假设每一元素被查找的概率相同，则查找每假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为一元素所需的比较次数之总和再取平均，即为ASLASL。显然，显然，ASLASL值越小，时间效率越高。值越小，时间效率越高。 6针对静态查找表的查找算法主要有：针对静态查找表的查找算法主要有： 8.2 静态查找表静态查找表的抽象数据类型参见教材静态查找表的抽象数据类型参见教材P216。一、一、顺序查找（线性查找）顺序查找（线性查找）二、二、折半查找（二分或对分查找）折半查找（二分或对分查找）三、三、静态树表的查找静态树表的查找四、四、分块查找（索引顺序查找）分块查找（索引顺序查找）7一、顺序查找（一、顺序查找（ Linear searchLinear search，又称线性查找，又称线性查找 ）（1）顺序表的机内存储结构：）顺序表的机内存储结构：typedef struct ElemType *elem; /表基址，表基址，0 0号单元留空。表容量为全部元素号单元留空。表容量为全部元素 int length; /表长，即表中数据元素个数表长，即表中数据元素个数SSTable;顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。直接的办法。 v对对顺序结构顺序结构如何线性查找？如何线性查找？见下页之例见下页之例或教材或教材P216P216；v对对单单链链表表结结构构如如何何线线性性查查找找？函函数数虽虽未未给给出出，但但也也很很容容易易编写；只要知道头指针编写；只要知道头指针headhead就可以就可以“顺藤摸瓜顺藤摸瓜”；v对对非线性树结构非线性树结构如何顺序查找如何顺序查找? ?可借助各种遍历操作！可借助各种遍历操作！8（2 2）算法的实现：）算法的实现：技巧：技巧：把待查关键字把待查关键字keykey存入表头或表尾（俗称存入表头或表尾（俗称“哨兵哨兵”），），这样可以加快执行速度。这样可以加快执行速度。例：例：若将待查找的特定值若将待查找的特定值keykey存入顺序表的首部（如存入顺序表的首部（如0 0号单元）号单元），则顺序查找的实现方案为：从后向前逐个比较！，则顺序查找的实现方案为：从后向前逐个比较！int Search_Seq( SSTable ST , KeyType key ) /在顺序表在顺序表STST中，查找关键字与中，查找关键字与keykey相同的元素；若成功，返回其位相同的元素；若成功，返回其位置信息，否则返回置信息，否则返回0 0 ST.elem0.key =key; /设立哨兵，可免去查找过程中每一步设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当都要检测是否查找完毕。当n1000n1000时，查找时间将减少一半。时，查找时间将减少一半。 for( i=ST.length; 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_Seq9返回特殊标志，例如返回空记录或空指针。前例中设立了返回特殊标志，例如返回空记录或空指针。前例中设立了“哨哨兵兵”，就是将关键字送入末地址，就是将关键字送入末地址ST.elem0.keyST.elem0.key使之结束并返回使之结束并返回 i=0i=0。讨论讨论 查找效率怎样计算？查找效率怎样计算？用平均查找长度用平均查找长度ASL衡量。衡量。讨论讨论 查不到怎么办？查不到怎么办？讨论讨论 如何计算如何计算ASL？分析：分析：查找第查找第1个元素所需的比较次数为个元素所需的比较次数为1；查找第查找第2个元素所需的比较次数为个元素所需的比较次数为2；查找第查找第n个元素所需的比较次数为个元素所需的比较次数为n；总计全部比较次数为：总计全部比较次数为：12n = (1+n)n/2未考虑查找不成功的未考虑查找不成功的情况：查找哨兵所需情况：查找哨兵所需的比较次数为的比较次数为n+1n+1这是查找成功的情况这是查找成功的情况若求某一个元素的平均查找次数，还应当除以若求某一个元素的平均查找次数，还应当除以n（等概率），（等概率），即：即： ASL（1n）/2 ，时间效率为，时间效率为 O(n)思考不成功的计算思考不成功的计算10二、折半查找（又称二分查找或对分查找）二、折半查找（又称二分查找或对分查找）优点：算法简单，且对顺序结构或链表结构均适用。优点：算法简单，且对顺序结构或链表结构均适用。缺点：缺点： ASL 太长，时间效率太低。太长，时间效率太低。这是一种容易想到的查找方法。这是一种容易想到的查找方法。先给数据排序（例如按升序排好），形成有序表，然后再将先给数据排序（例如按升序排好），形成有序表，然后再将keykey与正中元素相比，若与正中元素相比，若keykey小，则缩小至左半部内查找；再取其中小，则缩小至左半部内查找；再取其中值比较，每次缩小值比较，每次缩小1/21/2的范围，直到查找成功或失败为止。的范围，直到查找成功或失败为止。v对对顺序表结构顺序表结构如何编程实现折半查找算法？如何编程实现折半查找算法？ 见下页之例见下页之例，或见教材（，或见教材（P219P219）v对对单链表结构单链表结构如何折半查找？如何折半查找？ 无法实现！无法实现！因全部元素的定位只能从头指针因全部元素的定位只能从头指针headhead开始开始v对对非线性非线性(树树)结构结构如何折半查找？如何折半查找？ 可借助二叉排序树来查找（属动态查找表形式）。可借助二叉排序树来查找（属动态查找表形式）。 如何改进如何改进？讨论讨论 顺序查找的特点：顺序查找的特点：11 运算步骤运算步骤：(1) low =1,high =11 ,mid =6 (1) low =1,high =11 ,mid =6 ，待查范围是，待查范围是 1,111,11；(2) (2) 若若 ST.elemmid.key keyST.elemmid.key keyST.elemmid.key key，说明，说明keykey low ,mid-1low ,mid-1， 则令：则令：high =midhigh =mid1;1;重算重算 mid mid ；(4)(4)若若 ST.elem mid .key = keyST.elem mid .key = key，说明查找成功，元素序号，说明查找成功，元素序号=mid;=mid;结束条件：结束条件： （1 1）查找成功）查找成功 ： ST.elemmid.key = keyST.elemmid.key = key （2 2）查找不成功）查找不成功 ： highlow highlow （意即区间长度小于（意即区间长度小于0 0）解：解： 先设定先设定3个辅助标志个辅助标志: low,high,midlow,high,mid，折半查找举例：折半查找举例：LowLow指向待查元素指向待查元素所在区间的下界所在区间的下界highhigh指向待查元素所指向待查元素所在区间的上界在区间的上界midmid指向待查元素所在指向待查元素所在区间的中间位置区间的中间位置 已知如下已知如下11个元素的有序表：个元素的有序表：（05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为请查找关键字为21 和和85的数据元素。的数据元素。显然有：显然有：mid= (low+high)/2 此例作为自测的算法题之一，建议上机验证。此例作为自测的算法题之一，建议上机验证。此例作为自测的算法题之一，建议上机验证。此例作为自测的算法题之一，建议上机验证。12讨论讨论 若关键字不在表中，怎样得知何时停止？若关键字不在表中，怎样得知何时停止？典型标志是：当查找范围的上界典型标志是：当查找范围的上界下界时停止查找。下界时停止查找。讨论讨论 二分查找的效率（二分查找的效率（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-1）个；）个；为方便起见，假设表中全部为方便起见，假设表中全部n个元素个元素 2m-1个，此时就不讨论第个，此时就不讨论第m次比较后还有剩余元素的情况了。次比较后还有剩余元素的情况了。全部比较总次数为全部比较总次数为120221322423m2m1 推推导导过过程程13平均每个数据的查找时间还要除以平均每个数据的查找时间还要除以n n，所以：，所以：（详细推导过程见教材（详细推导过程见教材P221的附录）的附录）课堂练习（多项选择）：课堂练习（多项选择）：采用链式存贮结构采用链式存贮结构采用链式存贮结构采用链式存贮结构 记录的长度记录的长度记录的长度记录的长度 128 128 采用顺序存贮结构采用顺序存贮结构采用顺序存贮结构采用顺序存贮结构 记录按关键字递增有序记录按关键字递增有序记录按关键字递增有序记录按关键字递增有序使用折半查找算法时，要求被查文件：使用折半查找算法时，要求被查文件：思考：思考：假设在有序线性表假设在有序线性表a20上进行折半查找，则上进行折半查找，则平均查找长度为平均查找长度为 。14查找过程可用二叉树描述：每个记录用一个结点表示；结点中值为查找过程可用二叉树描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树。该记录在表中位置，这个描述查找过程的二叉树称为判定树。n个元个元素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。决定。 找到有序表中任一记录的过程就是：走了一条从根结点到与该记录找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相应的结点的路径。相应的结点的路径。 比较的关键字个数：为该结点在判定树上的层次数。比较的关键字个数：为该结点在判定树上的层次数。 查找成功时查找成功时比较的关键字个数最多不超过树的深度比较的关键字个数最多不超过树的深度 d : d = log2 n + 1 若所有结点的空指针域设置为一个指向一个方形结点的指针，称若所有结点的空指针域设置为一个指向一个方形结点的指针，称方形结点为判定树的外部结点；对应的，圆形结点为内部结点。方形结点为判定树的外部结点；对应的，圆形结点为内部结点。 查找不成功的过程查找不成功的过程 就是走了一条从根结点到外部结点的路径。就是走了一条从根结点到外部结点的路径。做习题做习题新建新建 Microsoft Word 文档文档.doc折半查找效率分析法折半查找效率分析法2 2（参见教材（参见教材P220P220）：）：15三、静态树表的查找三、静态树表的查找讨论讨论2：当有序表中各记录的查找概率不相等时，该如何查？：当有序表中各记录的查找概率不相等时，该如何查？首先要明确，此时用折半查找法未必最优！（参见教材首先要明确，此时用折半查找法未必最优！（参见教材P222例）例）改进：若将各记录概率看作是二叉树之权值，则转为研究带改进：若将各记录概率看作是二叉树之权值，则转为研究带权路径长度最小的二叉树（类似最优二叉树）。权路径长度最小的二叉树（类似最优二叉树）。讨论讨论1：对有序表还有其他查找算法吗？：对有序表还有其他查找算法吗？静态最优查找树算法静态最优查找树算法时间代价高；时间代价高；实用算法：近似最优查找树（次优查找树）实用算法：近似最优查找树（次优查找树） （参见教材（参见教材P222225）有，如斐波那契查找和插值查找等（参见教材有，如斐波那契查找和插值查找等（参见教材P221222）16四、分块查找（索引顺序查找）四、分块查找（索引顺序查找）这是一种顺序查找的另一种改进方法。这是一种顺序查找的另一种改进方法。先让数据先让数据分块有序分块有序，即分成若干子表，要求每个子表中的数，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。有序）。然后将各子表中的最大关键字构成一个然后将各子表中的最大关键字构成一个索引表索引表，表中还要包，表中还要包含每个子表的起始地址（即头指针）。含每个子表的起始地址（即头指针）。索引表索引表最大关键字起始地址2 22 21 12 21 13 38 89 92 20 03 33 34 42 24 44 43 38 82 24 44 48 86 60 05 58 87 74 44 49 98 86 65 53 3第第1 1块块第第2 2块块第第3 3块块224886例：例：2222484886861 17 71313特点：块间有特点：块间有序，块内无序序，块内无序17查找步骤查找步骤分两步进行：分两步进行： 对索引表使用折半查找法（因为索引表是有序表）；对索引表使用折半查找法（因为索引表是有序表）； 确定了待查关键字所在的子表后，在子表内采用顺序确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；查找法（因为各子表内部是无序表）；查找效率：查找效率：ASL=LASL=Lb b+L+Lw w对索引表查找的对索引表查找的ASL对块内查找的对块内查找的ASLS为每块内部的记录个数，为每块内部的记录个数，n/s即块的数目即块的数目例如当例如当n=9n=9，s=3s=3时，时，ASLASLbsbs=3.5,=3.5,而折半法为而折半法为3.1,3.1,顺序法为顺序法为5 518n n习题习题n n 要进行线性查找，则线性表要进行线性查找，则线性表要进行线性查找，则线性表要进行线性查找，则线性表 A A ；要进行二分查找，；要进行二分查找，；要进行二分查找，；要进行二分查找，则线性表则线性表则线性表则线性表 B B ；要进行散列查找，则线性表；要进行散列查找，则线性表；要进行散列查找，则线性表；要进行散列查找，则线性表 C C 。顺序存。顺序存。顺序存。顺序存储的表格，其中有储的表格，其中有储的表格，其中有储的表格，其中有9000090000个元素，已按关键项的值的上升个元素，已按关键项的值的上升个元素，已按关键项的值的上升个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，顺序排列。现假定对各个元素进行查找的概率是相同的，顺序排列。现假定对各个元素进行查找的概率是相同的，顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查并且各个元素的关键项的值皆不相同。当用顺序查找法查并且各个元素的关键项的值皆不相同。当用顺序查找法查并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为找时，平均比较次数约为找时，平均比较次数约为找时，平均比较次数约为 D D ，最大比较次数为，最大比较次数为，最大比较次数为，最大比较次数为 E E 。 供选择的答案：供选择的答案：供选择的答案：供选择的答案：ACAC： 必须以顺序方式存储必须以顺序方式存储必须以顺序方式存储必须以顺序方式存储 必须以链表方式存储必须以链表方式存储必须以链表方式存储必须以链表方式存储 必须以散列方式存储必须以散列方式存储必须以散列方式存储必须以散列方式存储 既可以以顺序方式，也可以既可以以顺序方式，也可以既可以以顺序方式，也可以既可以以顺序方式，也可以以链表方式存储以链表方式存储以链表方式存储以链表方式存储 必须以顺序方式存储且数据元素已必须以顺序方式存储且数据元素已必须以顺序方式存储且数据元素已必须以顺序方式存储且数据元素已按值递增或递减的次序排好按值递增或递减的次序排好按值递增或递减的次序排好按值递增或递减的次序排好 必须以链表方式存储且必须以链表方式存储且必须以链表方式存储且必须以链表方式存储且数据元素已按值递增或递减的次序排好数据元素已按值递增或递减的次序排好数据元素已按值递增或递减的次序排好数据元素已按值递增或递减的次序排好D D，E E： 25000 25000 30000 30000 45000 45000 90000 90000n n答案：答案： A=A= B= B= C= C= D D E E 19特点：特点：一、一、二叉排序树的定义二叉排序树的定义二、二、二叉排序树的插入与删除二叉排序树的插入与删除三、三、二叉排序树的查找分析二叉排序树的查找分析四、平衡二叉树四、平衡二叉树8.2 8.2 动态查找表动态查找表表结构在查找过程中动态生成。表结构在查找过程中动态生成。要求：要求： 对于给定值对于给定值key,key,若表中存在其关键字等于若表中存在其关键字等于keykey的记录，则查找成功返回；的记录，则查找成功返回；否则插入关键字等于否则插入关键字等于否则插入关键字等于否则插入关键字等于key key key key 的记录。的记录。的记录。的记录。典型的动态表典型的动态表二叉排序树二叉排序树20一、二叉排序树的定义一、二叉排序树的定义（a）（b）练：下列练：下列2种图形中，哪个不是二叉排序树种图形中，哪个不是二叉排序树 ？-或是一棵空树；或者是具有如下性质的非空二叉树：或是一棵空树；或者是具有如下性质的非空二叉树： （1 1）左子树的所有结点均小于根的值；）左子树的所有结点均小于根的值； （2 2）右子树的所有结点均大于根的值；）右子树的所有结点均大于根的值； （3 3）它的左右子树也分别为二叉排序树。）它的左右子树也分别为二叉排序树。21二、二叉排序树的插入与删除二、二叉排序树的插入与删除将数据元素构造成二叉排序树的优点：将数据元素构造成二叉排序树的优点： 查找过程与顺序结构有序表中的折半查找相似，查找效率高；查找过程与顺序结构有序表中的折半查找相似，查找效率高； 中序遍历此二叉树，将会得到一个关键字的有序序列（即实现中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）；了排序运算）； 如果查找不成功，能够方便地将被查元素插入到二叉树的叶子如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。结点上，而且插入或删除时只需修改指针而不需移动元素。注：若注：若数据元素的数据元素的输入顺序不同，则得到的二叉排序树形态输入顺序不同，则得到的二叉排序树形态也不同！也不同！这种既查找又插入的过程称为动态查找。这种既查找又插入的过程称为动态查找。二叉排序树既有类似于折半查找的特性，又采用了链表存储，二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。它是动态查找表的一种适宜表示。2245452424535312129090如果待如果待查找的关键字序列输入顺序为：查找的关键字序列输入顺序为：（2424，5353， 4545，4545，1212，2424，9090），），24245353454512129090查查找找成成功，功，返返回回查查找找成成功，功，返返回回讨论讨论1 1：二叉排序树的插入和查找操作：二叉排序树的插入和查找操作 则生成二叉排序则生成二叉排序树的过程为：树的过程为：例例：输入待查找的关键字序列输入待查找的关键字序列= =（4545，2424，5353，4545，1212，2424，9090）则生成的二叉排则生成的二叉排序树形态不同：序树形态不同：查查找找成成功，功，返返回回查查找找成成功，功，返返回回23二叉排序树的查找二叉排序树的查找& &插入算法如何实现？插入算法如何实现？查找算法参见教材查找算法参见教材P228算法算法9.5（a,b）;插入算法参见教材插入算法参见教材P228算法算法9.6;24对于二叉排序树，删除树上一个结点相当于删除有序序列中对于二叉排序树，删除树上一个结点相当于删除有序序列中的一个记录，删除后仍需保持二叉排序树的特性。的一个记录，删除后仍需保持二叉排序树的特性。（对链表进行删除操作是很方便的）（对链表进行删除操作是很方便的）讨论讨论2 2：二叉排序树的删除操作：二叉排序树的删除操作如何删除一个结点？如何删除一个结点？假设：假设：* *p p表示被删结点的指针；表示被删结点的指针； P PL和和PR 分别表示分别表示* *P P的左、右孩子指针；的左、右孩子指针；* *f f表示表示* *p p的双亲结点指针；并假定的双亲结点指针；并假定* *p p是是* *f f的左孩子；则可能有三种情况：的左孩子；则可能有三种情况：PR 为为 * * S S 的右子树；的右子树； S SL 为为 Q（ * * S S的双亲结点）右孩子的双亲结点）右孩子*p*p为叶子：为叶子： 删除此结点时，直接修改删除此结点时，直接修改* *f f指针域即可；指针域即可；* *p p只有一棵子树（或左或右）：只有一棵子树（或左或右）：令令P PL或或PR为为* *f f的左孩子即可；的左孩子即可；* *p p有两棵子树：情况最复杂有两棵子树：情况最复杂 25*p*p有两棵子树时，如何进行删除操作？有两棵子树时，如何进行删除操作？分析：分析：设删除前的中序遍历序列为：设删除前的中序遍历序列为：. 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左子树最右下的叶子左子树最右下的叶子左子树最右下的叶子左子树最右下的叶子26F FC CCLS SSLQLPPRQPRF FC CCLS SSLQLPPRQ法法2:2:：令：令*s代替代替*p F FC CCLS SSLQLPPRQ法法1:1:令令*p的左子树的左子树为为 *f的左子树，的左子树，*p的的右子树为右子树为*s的右子树；的右子树；例：请从下面的二叉排序树中删除结点例：请从下面的二叉排序树中删除结点P P。S SSL271) 1) 二叉排序树上查找某关键字等于给定值的结点过程，其实二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。就是走了一条从根到该结点的路径。 比较的关键字次数此结点的层次数比较的关键字次数此结点的层次数; ; 最多的比较次数树的深度（或高度），即最多的比较次数树的深度（或高度），即 loglog2 2 n n +1+12) 2) 一棵二叉排序树的平均查找长度为：一棵二叉排序树的平均查找长度为： 三、二叉排序树的查找分析三、二叉排序树的查找分析其中：其中：n ni i 是每层结点个数；是每层结点个数； C Ci i 是结点所在层次数；是结点所在层次数；m m 为树深。为树深。最坏情况：即插入的最坏情况：即插入的n个元素从一开始就有序，个元素从一开始就有序， 变成单支树的形态！变成单支树的形态！ 此时树的深度为此时树的深度为n ; ASL= (n+1)/2 此时查找效率与顺序查找情况相同。此时查找效率与顺序查找情况相同。28最好情况：即：与折半查找中的判定树相同（形态比较均衡）最好情况：即：与折半查找中的判定树相同（形态比较均衡）3）对有）对有 n 个关键字的二叉排序树的平均查找长度个关键字的二叉排序树的平均查找长度: 设每种树态出现概率相设每种树态出现概率相 同同 ，查找每个关键字也是等概率的。，查找每个关键字也是等概率的。则则ASL求解过程可推导。求解过程可推导。 （详见教材（详见教材P232）树的深度为：树的深度为： log 2n +1 ；ASL=log 2(n+1) 1 ；与折半查找相同。；与折半查找相同。结论：二叉排序树的结论：二叉排序树的ASL2（11/n）ln n