1、第第7 7章章 查找表查找表2022年8月3日星期三本章概述本章概述 “查找查找”是日常生活中常有的事，人们几乎每天都是日常生活中常有的事，人们几乎每天都要做要做“查找查找”工作。例如，在电话号码簿中查找某单工作。例如，在电话号码簿中查找某单位或某人的电话号码；在阅读文献时查阅字典以确定位或某人的电话号码；在阅读文献时查阅字典以确定某个词的含义；在程序设计中，查找也是一种常用的某个词的含义；在程序设计中，查找也是一种常用的基本运算，如编译程序中符号表的查找、信息处理系基本运算，如编译程序中符号表的查找、信息处理系统中信息的查找等。因此，如何高效率地实现查找运统中信息的查找等。因此，如何高效率地
2、实现查找运算是查找表的基本问题，也是本章的重点内容。算是查找表的基本问题，也是本章的重点内容。2022年8月3日星期三7.1 7.1 基本概念与术语基本概念与术语 关键字关键字:是数据元素（或记录）中某个数据项的值，是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录用它可以标识（识别）一个数据元素（或记录）。）。若若此关键字可以唯一地标识一个记录，则称此关键此关键字可以唯一地标识一个记录，则称此关键字为主关键字（字为主关键字（primary keyprimary key），不同的记录其主关键），不同的记录其主关键字不同，反之，称用以识别若干记录的关键字为次关字不同，
3、反之，称用以识别若干记录的关键字为次关键字（键字（secondary keysecondary key）。）。查找（查找（searchingsearching）：根据给定的某个值，在表中）：根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素。确定一个关键字等于给定值的记录或数据元素。2022年8月3日星期三7.2 7.2 顺序表的查找顺序表的查找 当顺序表作为线性表的存储结构时，存储结点间当顺序表作为线性表的存储结构时，存储结点间的位置关系与对应数据元素之间的逻辑关系（邻接关的位置关系与对应数据元素之间的逻辑关系（邻接关系）是一致的，即数据元素在线性表中的次序与它们系）是一致的，
4、即数据元素在线性表中的次序与它们在顺序表中次序相同。在顺序表中次序相同。顺序表的存储结构如下：顺序表的存储结构如下：typedef strict typedef strict ElemType ElemType*elemelem;/存储空间基址存储空间基址,建表时按照实际长度分配建表时按照实际长度分配,0,0号号单元不用单元不用intint length;length;/顺序表长度顺序表长度STableSTable;2022年8月3日星期三 查找可分为静态查找和动态查找两大类。查找可分为静态查找和动态查找两大类。静态查找是指在查找时只对数据元素进行查询和检静态查找是指在查找时只对数据元素进行查
5、询和检索。索。动态查找除包括静态查找的要求外，还包括插入数动态查找除包括静态查找的要求外，还包括插入数据元素集合中不存在的数据元素，或者从数据元素集合据元素集合中不存在的数据元素，或者从数据元素集合中删除已存在的某个数据元素。中删除已存在的某个数据元素。静态查找时构造的存储结构称作静态查找表。静态查找时构造的存储结构称作静态查找表。动态查找时构造的存储结构称作动态查找表。动态查找时构造的存储结构称作动态查找表。2022年8月3日星期三 顺序查找适用于线性表的顺序存储结构，也适用于顺序查找适用于线性表的顺序存储结构，也适用于链式存储结构，表内的数据元素是无序的。链式存储结构，表内的数据元素是无序
6、的。顺序查找的查找过程为：顺序查找的查找过程为：从顺序表中的最后一个记录开始，逐个进行记录的从顺序表中的最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值关键字和给定值的比较，若某个记录的关键字和给定值比较后相等，则查找成功，找到所查记录；如果直至第比较后相等，则查找成功，找到所查记录；如果直至第一个记录，关键字和给定值比较都不等，则表明表中没一个记录，关键字和给定值比较都不等，则表明表中没有所查找的记录，查找失败。有所查找的记录，查找失败。查找算法描述如算法查找算法描述如算法7.17.1所示。所示。7.2.1 7.2.1 顺序查找顺序查找2022年8月3日星期三
7、 int Search_Seq(STable ST,KeyType key)int Search_Seq(STable ST,KeyType key)/在顺序表在顺序表STST中顺序查找其关键字等于中顺序查找其关键字等于keykey的数据元的数据元素素 i=0;i=0;ST.elem0.key=key;ST.elem0.key=key;/设置监视哨设置监视哨 for(i=ST.length;ST.elemi.key!=key;-i);for(i=ST.length;ST.elemi.key!=key;-i);/从后往前找从后往前找 retirn i;retirn i;/找不到时，找不到时，i
8、i为为0 0/Search_Seq/Search_Seq算法算法 7.1 7.12022年8月3日星期三 在查找之前先将在查找之前先将ST.elem0ST.elem0的关键字赋值的关键字赋值keykey，则，则ST.elem0 ST.elem0 在此起到了哨兵的作用。目的是避免在查在此起到了哨兵的作用。目的是避免在查找的每一步都要判断整个表是否查找完毕，即在找的每一步都要判断整个表是否查找完毕，即在forfor循循环中省去了判定下标越界的条件，提高了算法的效率。环中省去了判定下标越界的条件，提高了算法的效率。ST.elemi.keyST.elemi.key表示第表示第i i个记录的关键字，个记
9、录的关键字，ST.lengthST.length表表示顺序表中元素的个数，示顺序表中元素的个数，keykey为查找的对象。为查找的对象。2022年8月3日星期三 查找算法的基本操作也就是查找算法的基本操作也就是“将记录的关键字和将记录的关键字和给定值进行比较给定值进行比较”，比较的次数依赖于这个数据元素，比较的次数依赖于这个数据元素在结构中所处的位置。在结构中所处的位置。为了确定要查找的记录位置，与给定值进行比较为了确定要查找的记录位置，与给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的的关键字个数的期望值称为查找算法在查找成功时的平均查找长度平均查找长度ASL(average s
10、earch length)ASL(average search length)。对于含。对于含有有n n个记录的表，平均查找长度的计算公式为：个记录的表，平均查找长度的计算公式为：2022年8月3日星期三 其中，其中，P Pi i为查找第为查找第i i个记录的概率，个记录的概率，；C Ci i为在表中找到其关键字与给定值相等的第为在表中找到其关键字与给定值相等的第i i个记个记录时，和给定值已进行过比较的关键字个数。一般录时，和给定值已进行过比较的关键字个数。一般情况下情况下,C,Ci i等于等于n ni+1i+1。niiiCPASL111niiP2022年8月3日星期三若查找每个元素的概率相
11、同，即为若查找每个元素的概率相同，即为P P1 1=P=P2 2=P=Pn n=1/n=1/n。对于等概率的查找，其平均查找长度的计。对于等概率的查找，其平均查找长度的计算公式可简化为：算公式可简化为：ASL =ASL =iniiCP1niiCn11niinn1)1(121n2022年8月3日星期三 查找算法的平均查找长度应是查找成功时的平均查找长度查找算法的平均查找长度应是查找成功时的平均查找长度与查找不成功时的平均查找长度之和的一半。如果查找不成与查找不成功时的平均查找长度之和的一半。如果查找不成功，比较次数为功，比较次数为n+1n+1。假设查找成功与不成功的可能性相同，。假设查找成功与不
12、成功的可能性相同，则则 ASL=ASL=)1(21)1(1211ninnni)1(43n2022年8月3日星期三 折半查找又称为二分查找，是一种效率较高的查找折半查找又称为二分查找，是一种效率较高的查找方法，它要求线性表的结点必须是按关键字非递减方法，它要求线性表的结点必须是按关键字非递减(或非或非递增递增)的次序排列的，并采用顺序结构存储。的次序排列的，并采用顺序结构存储。折半查找的查找过程是：折半查找的查找过程是：首先确定待查记录所在的范围，然后逐渐缩小范围直首先确定待查记录所在的范围，然后逐渐缩小范围直到查到或者查不到结果为止。假设指针到查到或者查不到结果为止。假设指针lowlow指向待
13、查记录指向待查记录所在范围的下界所在范围的下界ST.elemST.elem1 1，指针，指针highhigh指向待查记录所在指向待查记录所在范围范围的上界的上界ST.elemST.lengthST.elemST.length，指针指针midmid指向待查记录指向待查记录所在范围的中间位置，即所在范围的中间位置，即mid=(low+high)/2mid=(low+high)/2。用给定。用给定值值keykey与与midmid指定的值指定的值ST.elemmidST.elemmid相比较。若相等，则表相比较。若相等，则表示查找成功；若不相等，则缩小范围，直到新的示查找成功；若不相等，则缩小范围，直
14、到新的midmid值等值等于给定值或者查找区间的大小小于零时为止。于给定值或者查找区间的大小小于零时为止。7.2.2 7.2.2 有序表的折半查找有序表的折半查找2022年8月3日星期三 【例【例7-17-1】已知如下已知如下1010个数据元素的有序表个数据元素的有序表(关键字即为数关键字即为数据元素的值据元素的值)7 7，1818，2525，3737，5454，6262，7676，8080，8989，9898要求查找关键字为要求查找关键字为2525和和8585的数据元素。的数据元素。解：首先看给定值解：首先看给定值key=25key=25的查找过程：的查找过程：(1)(1)令指针令指针low
15、low指向第指向第1 1个元素，指针个元素，指针highhigh指向第指向第1010个数据元素，个数据元素，此时此时mid=mid=(1+10)/2(1+10)/2=5=5。2022年8月3日星期三 (2)key(2)key小于小于ST.elemmid.keyST.elemmid.key，说明待查找元素若，说明待查找元素若存在，必在区间存在，必在区间lowlow，mid-1mid-1区间内，令指针区间内，令指针highhigh等于等于mid-1(mid-1(第第4 4个数据元素个数据元素)，重新得到，重新得到mid=mid=(1+4)/2(1+4)/2=2=2。2022年8月3日星期三(3)(
16、3)此时此时keykey大于大于ST.elemmid.keyST.elemmid.key，说明待查元素若存在，说明待查元素若存在，必在区间必在区间mid+1mid+1，highhigh区间内，令指针区间内，令指针lowlow等于等于mid+1 mid+1(第第3 3个数据元素个数据元素)，重新得到，重新得到mid=mid=(3+4)/2(3+4)/2=3=3。（4)4)此时此时ST.elemmid.keyST.elemmid.key等于等于2525，与给定值相等，查找，与给定值相等，查找成功，返回该元素在表中的位置即指针成功，返回该元素在表中的位置即指针midmid的值。的值。2022年8月3
17、日星期三 由例可见，当由例可见，当keykey值小于值小于ST.elemmid.keyST.elemmid.key，说明，说明待查元素位置在待查元素位置在lowlow和和midmid之间，则令指针之间，则令指针high=mid-1high=mid-1，在表的前半部分取中间位置的记录比较；当在表的前半部分取中间位置的记录比较；当keykey值大值大于于ST.elemmid.keyST.elemmid.key，说明待查元素的位置在，说明待查元素的位置在midmid和和highhigh之间，则令指针之间，则令指针low=mid+1low=mid+1，在表的后半部，在表的后半部分再取中间位置的记录进行
18、比较。分再取中间位置的记录进行比较。折半查找的算法可描述为折半查找的算法可描述为算法算法7.27.2。2022年8月3日星期三 折半查找的过程可用一棵二叉树来表示，如下图折半查找的过程可用一棵二叉树来表示，如下图所示，树中每个结点表示表中的一个记录，结点的值所示，树中每个结点表示表中的一个记录，结点的值对应元素的关键字，结点上面的编号为对应的值在表对应元素的关键字，结点上面的编号为对应的值在表中的位置。每个根结点对应当前查找区间的中间元素中的位置。每个根结点对应当前查找区间的中间元素ST.elemmidST.elemmid，它的左子树和右子树分别对应该区，它的左子树和右子树分别对应该区间的前半
19、部分和后半部分，通常把此二叉树称为折半间的前半部分和后半部分，通常把此二叉树称为折半查找的判定树。查找的判定树。2022年8月3日星期三2022年8月3日星期三 由此图得出结论，在有序表中折半查找成功的过由此图得出结论，在有序表中折半查找成功的过程就是一条从根结点到满足条件的记录所对应结点的程就是一条从根结点到满足条件的记录所对应结点的路径，给定值同关键字比较的次数就等于该路径的结路径，给定值同关键字比较的次数就等于该路径的结点数，或该结点在判定树上的层次数，它最多不会超点数，或该结点在判定树上的层次数，它最多不会超过树的深度，而具有过树的深度，而具有n n个结点的判定树的深度为个结点的判定树
20、的深度为log2nlog2n+1+1，所以折半查找在查找成功时和给定值进，所以折半查找在查找成功时和给定值进行比较的关键字个数至多为行比较的关键字个数至多为log2nlog2n+1+1。2022年8月3日星期三 折半查找不成功时，如该例查找给定值为折半查找不成功时，如该例查找给定值为8585，在折，在折半查找的判定树上的路径是从根结点出发最后指向空子半查找的判定树上的路径是从根结点出发最后指向空子树的过程，该路径中给定值与关键字进行比较的次数仍树的过程，该路径中给定值与关键字进行比较的次数仍为路径中的结点数，所以折半查找不成功时，给定值与为路径中的结点数，所以折半查找不成功时，给定值与关键字进
21、行比较的次数也不超过关键字进行比较的次数也不超过log2nlog2n+1+1。2022年8月3日星期三 假设表中每个记录的查找概率都相等，即假设表中每个记录的查找概率都相等，即Pi=1/nPi=1/n，则查找成功时折半查找的平均查找长度为：则查找成功时折半查找的平均查找长度为：1221112log(1)1 log(1)1nnii iiinASLpcinnn 2022年8月3日星期三 斐波那契查找是根据斐波那契序列的特点对表进行斐波那契查找是根据斐波那契序列的特点对表进行分割的。斐波那契序列定义为：分割的。斐波那契序列定义为：F F0 0=0=0，F F1 1=1=1，F Fi i=F=Fi i
22、-1+F1+Fi i-2-2（i2i2）。）。设记录个数比某个斐波那契数小设记录个数比某个斐波那契数小1 1，即，即n=Fn=Fi i-1-1，斐波，斐波那契查找是把关键字那契查找是把关键字keykey与与ST.elemFST.elemFi-1i-1.key.key作比较，作比较，若相等，则成功；若若相等，则成功；若keyST.elemFkeyST.elemFkeyST.elemFi-1i-1.key.key，则继续在则继续在ST.elemFST.elemFi-1i-1+1+1至至ST.elemFST.elemFi-1i-1 中查找，表的中查找，表的元素个数是元素个数是(F(Fi-1i-1)-
23、(F)-(Fi-1i-1+1)+1=F+1)+1=Fi i-F-Fi-1i-1-1=F-1=Fi-2i-2-1-1。7.2.3 7.2.3 斐波那契查找斐波那契查找2022年8月3日星期三 与折半查找相比，与折半查找相比，FibonacciFibonacci查找法的明显优点查找法的明显优点在于它只涉及加法和减法运算，而不用除法。因为除在于它只涉及加法和减法运算，而不用除法。因为除法比加减法要占去更多的机时，所以斐波那契查找的法比加减法要占去更多的机时，所以斐波那契查找的平均性能要比折半查找好，但最坏情况下的性能（虽平均性能要比折半查找好，但最坏情况下的性能（虽然仍是然仍是O(lognO(log
24、n)）却比折半查找差。）却比折半查找差。2022年8月3日星期三 分块查找又称索引顺序查找，是顺序查找的改进方法。分块查找又称索引顺序查找，是顺序查找的改进方法。分块查找算法中，除了表本身以外，还需建立一个分块查找算法中，除了表本身以外，还需建立一个“索引索引表表”。下图中，表中下图中，表中1818个记录，分成三块，对每一块建立一个记录，分成三块，对每一块建立一个索引项。索引项有两项内容：关键字项，其值为该块内个索引项。索引项有两项内容：关键字项，其值为该块内最大关键字的值；指针项，指示该块中第一个记录在表中最大关键字的值；指针项，指示该块中第一个记录在表中的位置。索引表按关键字有序排列，表或
25、者有序排列或者的位置。索引表按关键字有序排列，表或者有序排列或者分块有序排列。所谓分块有序排列。所谓“分块有序分块有序”指的是后一块表中所有指的是后一块表中所有记录的关键字均大于前一块表中的最大关键字。记录的关键字均大于前一块表中的最大关键字。7.2.4 7.2.4 分块查找分块查找2022年8月3日星期三 分块查找可以分为两步：首先在索引表中确定待查记分块查找可以分为两步：首先在索引表中确定待查记录所在块录所在块(可以用顺序或折半查找法可以用顺序或折半查找法)，然后在块内顺序查，然后在块内顺序查找给定值找给定值(只能用顺序查找法只能用顺序查找法)。主表被分成主表被分成3 3块，每块都含有块，
26、每块都含有6 6个记录，其中每块的最个记录，其中每块的最大关键字分别为大关键字分别为2323、5050、8484，索引表是按关键字非递减有，索引表是按关键字非递减有序排列的。假设给定值序排列的。假设给定值key=38key=38，首先在索引表中顺序查找，首先在索引表中顺序查找，因为第一个索引项的关键字因为第一个索引项的关键字233823385038，此时可判断若关键字为，此时可判断若关键字为3838的记的记录存在，必定在第二块中，第二块的起始位置为录存在，必定在第二块中，第二块的起始位置为7 7，则接，则接着从主表的第着从主表的第7 7个记录向后顺序查找，直到找到关键字为个记录向后顺序查找，直
27、到找到关键字为3838的记录为止。如果此块中没有关键字为的记录为止。如果此块中没有关键字为3838的记录（自第的记录（自第7 7个记录起至第个记录起至第1212个记录的关键字和个记录的关键字和keykey比较都不等），则比较都不等），则查找失败。查找失败。2022年8月3日星期三 需要注意的是，由于索引表是按关键字值有序排列需要注意的是，由于索引表是按关键字值有序排列的，所以确定块的查找既可以用顺序查找，也可以用折的，所以确定块的查找既可以用顺序查找，也可以用折半查找；而块中的记录是任意排列的，则在块内的查找半查找；而块中的记录是任意排列的，则在块内的查找只能是顺序查找。只能是顺序查找。由于分
28、块查找的算法即为这两种查找算法的简单合由于分块查找的算法即为这两种查找算法的简单合并，所以分块查找的平均查找长度为：并，所以分块查找的平均查找长度为：ASLASLsbsb=ASL=ASLb b+ASL+ASLw w 其中，其中，ASLASLb b是在索引表中确定待查记录所在块的平是在索引表中确定待查记录所在块的平均查找长度，均查找长度，ASLASLw w是在块中查找待查记录的平均查找长是在块中查找待查记录的平均查找长度。度。2022年8月3日星期三 假设长度为假设长度为n n的线性表被分成的线性表被分成m m块，每块含有块，每块含有s s个记录，即个记录，即m=m=，并且每个记录的查找概，并且
29、每个记录的查找概率都相等，则在索引表中确定块的概率为率都相等，则在索引表中确定块的概率为1/m1/m，在，在块中查找待查记录的概率为块中查找待查记录的概率为1/s1/s。若采用顺序查找。若采用顺序查找的方法确定待查记录所在块，则分块查找的平均查的方法确定待查记录所在块，则分块查找的平均查找长度为：找长度为：sn/1)(211111ssnjsimASLASLASLsjmiwbsb2022年8月3日星期三 当采用折半查找的方法确定待查记录所在的当采用折半查找的方法确定待查记录所在的块时，则分块查找的平均查找长度为：块时，则分块查找的平均查找长度为：2)1(log211)1(log22ssnsmAS
30、LASLASLwbsb2022年8月3日星期三7.3 7.3 动态查找表动态查找表 静态查找表一旦生成之后，所含记录在查找过程静态查找表一旦生成之后，所含记录在查找过程中一般是固定不变的。而动态查找表在查找过程中经中一般是固定不变的。而动态查找表在查找过程中经常进行插入和删除操作，所含记录一直是在变化的。常进行插入和删除操作，所含记录一直是在变化的。动态查找表能更好地解决在查找过程中表的动态动态查找表能更好地解决在查找过程中表的动态变化问题，此类表常见的有二叉排序树、平衡二叉树、变化问题，此类表常见的有二叉排序树、平衡二叉树、B B-树和树和B B+树等。树等。2022年8月3日星期三7.3.
31、1 7.3.1 二叉排序树二叉排序树 1.1.二叉排序树的定义二叉排序树的定义 二叉排序树是一种特殊的二叉树，它的每个结点的值二叉排序树是一种特殊的二叉树，它的每个结点的值都大于它的左子树上的所有结点的值，并且小于它的右都大于它的左子树上的所有结点的值，并且小于它的右子树上的所有结点的值，同时它的左、右子树也是二叉子树上的所有结点的值，同时它的左、右子树也是二叉排序树。特别地，空树也是二叉排序树。排序树。特别地，空树也是二叉排序树。例如，对应于关键字集合例如，对应于关键字集合L=100L=100，6060，4040，8080，7070，9090，150150，120120，110110，130
32、130，180180，160160，200200的二叉排序的二叉排序树如下图所示。树如下图所示。2022年8月3日星期三 二叉排序树的操作中，使用二叉链表作为存储二叉排序树的操作中，使用二叉链表作为存储结构，其结点结构说明如下：结构，其结点结构说明如下：typedef strict nodetypedef strict node KeyTypeKeyType key;key;/关键字的值关键字的值Strict node Strict node*lchild,lchild,*rchildrchild;/左右指针左右指针BSTNode,BSTNode,*BSTreeBSTree;2022年8月3日
33、星期三 2.2.二叉排序树的查找二叉排序树的查找 在二叉排序树中查找一个关键字值为在二叉排序树中查找一个关键字值为k k的结点的基本的结点的基本思想是：思想是：用给定值用给定值k k与根结点关键字比较，如果与根结点关键字比较，如果k k小于根结点小于根结点关键字的值，则要找的结点只可能在左子树中，所以继关键字的值，则要找的结点只可能在左子树中，所以继续在左子树中查找，否则将继续在右子树中查找，依此续在左子树中查找，否则将继续在右子树中查找，依此方法，查找下去直到查找成功或者查找失败为止。方法，查找下去直到查找成功或者查找失败为止。2022年8月3日星期三 二叉排序树查找的过程如下：二叉排序树查
34、找的过程如下：（1 1）若二叉排序树为空树，则查找失败。）若二叉排序树为空树，则查找失败。（2 2）将给定的值）将给定的值k k与根结点的关键字值比较，如果相与根结点的关键字值比较，如果相等，则查找成功。等，则查找成功。（3 3）若给定的值）若给定的值k k小于根结点的关键字值，则在左子小于根结点的关键字值，则在左子树中继续查找。树中继续查找。（4 4）否则，在右子树中继续查找。）否则，在右子树中继续查找。其递归算法如算法其递归算法如算法7.37.3所示。所示。2022年8月3日星期三BSTree SearchBST(BSTree bst,KeyTypeBSTree SearchBST(BST
35、ree bst,KeyType key)key)/在根指针在根指针bstbst所指的二叉排序树中，递归查找某关键所指的二叉排序树中，递归查找某关键字等于字等于keykey的元素，若查找的元素，若查找/成功，则返回指向该元素的指针，否则返回空指针成功，则返回指向该元素的指针，否则返回空指针if(!bst)if(!bst)retirn NiLLretirn NiLL;else if(bst-key=key)else if(bst-key=key)retirn bstretirn bst;/查找成功查找成功else if(key bstelse if(key key)-key)/在左子树中继续查找在
36、左子树中继续查找retirn SearchBST(bst-lchildretirn SearchBST(bst-lchild,key);,key);elseelseretirn SearchBST(bst-rchildretirn SearchBST(bst-rchild,key);,key);/在右子树中继续查找在右子树中继续查找 算法算法7.37.32022年8月3日星期三 1.1.二叉排序树中插入结点二叉排序树中插入结点 (1)(1)若该值小于根结点的值，则应插入左子树中，若该值小于根结点的值，则应插入左子树中，因此可以通过调用相同的算法（即递归调用插入算法）因此可以通过调用相同的算法（
37、即递归调用插入算法）来实现插入左子树的操作。来实现插入左子树的操作。(2)(2)若该值大于根结点的值，则可以通过递归调用若该值大于根结点的值，则可以通过递归调用插入算法来实现插入右子树的操作。插入算法来实现插入右子树的操作。按照这样的方式递归调用若干次后，总是可以搜按照这样的方式递归调用若干次后，总是可以搜索到一个空子树位置，这就是要插入的位置，可以将索到一个空子树位置，这就是要插入的位置，可以将该结点放在该子树上，作为该子树的根结点并连接到该结点放在该子树上，作为该子树的根结点并连接到其父结点上。其父结点上。7.3.27.3.2 二叉排序树二叉排序树中插入结点和构造二叉中插入结点和构造二叉排
38、序树排序树2022年8月3日星期三【例【例7-27-2】要在如要在如7.3.17.3.1中图所示的二叉排序树中插入值中图所示的二叉排序树中插入值为为7575的结点，所执行的操作过程如下的结点，所执行的操作过程如下：(1)(1)首先和根结点（即值为首先和根结点（即值为100100的结点）比较，由于的结点）比较，由于7575比比100100小，故要递归调用插入算法将其插入左子树（根为小，故要递归调用插入算法将其插入左子树（根为6060）中。中。(2)(2)由于由于7575比比6060大，故要递归调用插入算法将其插入右子大，故要递归调用插入算法将其插入右子树（根为树（根为8080）中。）中。(3)(
39、3)由于由于7575比比8080小，故要递归调用插入算法将其插入左子小，故要递归调用插入算法将其插入左子树（根为树（根为7070）中。）中。2022年8月3日星期三 (4)(4)由于由于7575比比7070大，故要递归调用插入算法将其大，故要递归调用插入算法将其插入右子树中。此时右子树为空，因此可以将该结点插入右子树中。此时右子树为空，因此可以将该结点直接插入到直接插入到7070的右边，作为其右孩子，到此插入操作的右边，作为其右孩子，到此插入操作完毕。完毕。根据上面的描述，插入结点的递归算法，如根据上面的描述，插入结点的递归算法，如算法算法7.47.4所示。所示。2022年8月3日星期三 2.
40、2.构造二叉排序树构造二叉排序树 二叉排序树的构造的算法思想：二叉排序树的构造的算法思想：首先将二叉排序树初始化为一棵空树，然后逐个读首先将二叉排序树初始化为一棵空树，然后逐个读入元素，每读入一个元素，就建立一个新的结点，并插入元素，每读入一个元素，就建立一个新的结点，并插入到当前已经生成的二叉排序树中，即通过多次调用二入到当前已经生成的二叉排序树中，即通过多次调用二叉排序树的插入结点的算法实现，这里需要注意的是，叉排序树的插入结点的算法实现，这里需要注意的是，插入时比较结点的顺序始终是从二叉排序树的根结点开插入时比较结点的顺序始终是从二叉排序树的根结点开始的。始的。2022年8月3日星期三
41、例如，对于关键字集合例如，对于关键字集合L L=45=45，2424，5353，4545，1212，2424，9090，建立一棵二叉排序树。那么建立的过程如下图所，建立一棵二叉排序树。那么建立的过程如下图所示。示。2022年8月3日星期三 二叉排序树的构造算法如算法二叉排序树的构造算法如算法7.57.5所示。所示。void CreateBST(BSTree void CreateBST(BSTree*bstbst)/从键盘输入元素的值，创建相应的二叉排序树从键盘输入元素的值，创建相应的二叉排序树KeyTypeKeyType key;key;*bst=NiLLbst=NiLL;scanfscan
42、f(“%d”,&key);(“%d”,&key);while(key!=ENDKEY)while(key!=ENDKEY)/ENDKEY/ENDKEY为自定义常量为自定义常量InsertBST(bstInsertBST(bst,key);,key);/在二叉排序树在二叉排序树bstbst中插入结点中插入结点keykey scanf scanf(“%d”,&key);(“%d”,&key);算法算法7.57.52022年8月3日星期三 在在二叉排序树中删除一个结点相当于删除有序序二叉排序树中删除一个结点相当于删除有序序列中的一个结点列中的一个结点。二叉排序树的删除的算法基本思想是：二叉排序树的删
43、除的算法基本思想是：首先首先查找要删除的结点，看它是否在二叉排序树查找要删除的结点，看它是否在二叉排序树中，若不在则不做任何操作；否则，假设要删除的结中，若不在则不做任何操作；否则，假设要删除的结点为点为P P，结点，结点P P的双亲结点为的双亲结点为F F，并假设结点，并假设结点P P是结点是结点F F的的左孩子（右孩子的情况类似）。左孩子（右孩子的情况类似）。7.3.3 7.3.3 二叉排序树中删除结点二叉排序树中删除结点2022年8月3日星期三 下面分三种情况讨论：下面分三种情况讨论：(1)(1)若若P P为叶子，则可直接删除：为叶子，则可直接删除：F-lchild=NiLL;F-lch
44、ild=NiLL;free(Pfree(P););(2)(2)若若P P结点只有左子树，或者只有右子树，则可将结点只有左子树，或者只有右子树，则可将P P 的左子的左子树（或者右子树）直接改为其双亲结点树（或者右子树）直接改为其双亲结点F F的左子树（或者的左子树（或者右子树）。即右子树）。即F-lchild=P-lchildF-lchild=P-lchild(或或F-rchild=F-rchild=P-rchild);free(PP-rchild);free(P););(3)(3)若若P P既有左子树，又有右子树，如下图既有左子树，又有右子树，如下图(a)(a)所示。所示。2022年8月3日
45、星期三此时有两种处理方法：此时有两种处理方法：方法方法1 1：首先找到首先找到P P结点在中序遍历序列中的直接前驱结点结点在中序遍历序列中的直接前驱结点S S，如下图如下图(b)(b)所示。所示。2022年8月3日星期三然后将然后将P P的左子树改为的左子树改为F F的左子树，而将的左子树，而将P P的右子树改的右子树改为为S S的右子树。结果如下图的右子树。结果如下图 (c)(c)所示。所示。2022年8月3日星期三 方法方法2 2：首选找到首选找到P P结点在中序遍历序列中的直接前驱结点结点在中序遍历序列中的直接前驱结点S S，然后用然后用S S结点的值替代结点的值替代P P结点的值，再将
46、结点的值，再将S S结点删除，原结点删除，原S S结结点的左子树改为点的左子树改为S S的双亲结点的双亲结点Q Q的右子树。结果如下图的右子树。结果如下图 (d)(d)所示。所示。2022年8月3日星期三 二叉排序树的删除结点的算法如二叉排序树的删除结点的算法如算法算法7.67.6所示。所示。二叉排序树的查找效率和折半查找的效率相差不大，二叉排序树的查找效率和折半查找的效率相差不大，并且在二叉排序树上实现插入和删除结点也很简单。并且在二叉排序树上实现插入和删除结点也很简单。对于那些需要经常进行插入、删除和查找操作的表，对于那些需要经常进行插入、删除和查找操作的表，适宜采用二叉排序树结构。适宜采
47、用二叉排序树结构。二叉排序树的平均查找长度难以确定，因为它不仅和二叉排序树的平均查找长度难以确定，因为它不仅和结点的个数结点的个数n n有关，而且和树的形态有关。有关，而且和树的形态有关。2022年8月3日星期三 二叉排序树越匀称，树的层次越少，平均查找深度越二叉排序树越匀称，树的层次越少，平均查找深度越小，该树的查找效率就越高；反之，二叉排序树不是很匀小，该树的查找效率就越高；反之，二叉排序树不是很匀称，树的层次越多，平均查找难度越大，树的查找效率就称，树的层次越多，平均查找难度越大，树的查找效率就越低。越低。例如一个记录集合中有例如一个记录集合中有7 7个记录，如果由它们组成的个记录，如果
48、由它们组成的二叉排序树是一棵满二叉排序树，如下图二叉排序树是一棵满二叉排序树，如下图(a)(a)所示，则当所示，则当每个结点的查找概率相等的时候，平均查找长度为每个结点的查找概率相等的时候，平均查找长度为(1+2(1+2*2+32+3*4)/7=17/72.434)/7=17/72.432022年8月3日星期三如果它们组成的二叉排序树是一棵单支树，如下图如果它们组成的二叉排序树是一棵单支树，如下图(b)(b)所示。则当每个结点的查找概率相等的情况下，平均所示。则当每个结点的查找概率相等的情况下，平均查找长度为查找长度为(1+2+3+4+5+6+7)/7=28/7=4(1+2+3+4+5+6+7
49、)/7=28/7=4。在随机的情况下，对于一个具有在随机的情况下，对于一个具有n n个结点的二叉排序个结点的二叉排序树，平均查找长度为树，平均查找长度为O(log2n)O(log2n)，在最坏的情况下为，在最坏的情况下为(n+1)/2(n+1)/2。2022年8月3日星期三7.47.4 哈希表哈希表 如果能在记录的存储位置和它的关键字之间建立如果能在记录的存储位置和它的关键字之间建立起某种直接联系，那么在查找时就能不进行比较或者起某种直接联系，那么在查找时就能不进行比较或者只进行很少次数的比较就能找到所要查找的结点。哈只进行很少次数的比较就能找到所要查找的结点。哈希表查找就是基于这种思想提出来
50、的。希表查找就是基于这种思想提出来的。7.4.1 7.4.1 哈希表与哈希方法哈希表与哈希方法2022年8月3日星期三 在查找过程中，最理想的情况是不经过任何比较，在查找过程中，最理想的情况是不经过任何比较，一次存取便能够得到所查的记录，则必须在记录的存一次存取便能够得到所查的记录，则必须在记录的存储位置和它的关键字之间建立一个确定的对应关系储位置和它的关键字之间建立一个确定的对应关系f f，使每个关键字和结构中一个唯一的存储位置相对应。使每个关键字和结构中一个唯一的存储位置相对应。查找时，只要根据这个对应关系查找时，只要根据这个对应关系f f找到给定值找到给定值k k的的象象f(k)f(k)
