1、9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 1数据结构数据结构第九章第九章 查找查找2022年年8月月3日星期三日星期三9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 2第九章第九章 查找查找基本概念基本概念查找表查找表：是由同一类型的数据元素是由同一类型的数据元素(或记录或记录)构成的集合。构成的集合。对查找
2、表经常进行的对查找表经常进行的操作操作:1）查询查询某个某个“特定的特定的”数据元素是否在查找表中；数据元素是否在查找表中；2）检索检索某个某个“特定的特定的”数据元素的各种属性；数据元素的各种属性；3）在查找表中）在查找表中插入插入一个数据元素；一个数据元素；4）从查找表中）从查找表中删去删去某个数据元素。某个数据元素。静态查找表静态查找表 仅作上述仅作上述1）和）和2）操作的查找表）操作的查找表 动态查找表动态查找表 有时在查询之后，还需要将有时在查询之后，还需要将“查询查询”结果为结果为“不在查找表不在查找表中中”的数据元素插入查找表；或者，从查找表中删除其的数据元素插入查找表；或者，从
3、查找表中删除其“查询查询”结果为结果为“在查找表中在查找表中”的数据元素。的数据元素。9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 3第九章第九章 查找查找基本概念基本概念关键字：关键字：是数据元素（或记录）中某个数据项的值，是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）用以标识（识别）一个数据元素（或记录）若此关键字可以识别唯一的一个记录，则称之谓若此关键字可以识别唯一的一个记录，则称之谓“主主关键字关键字”若此关键字能
4、识别若干记录，则称之谓若此关键字能识别若干记录，则称之谓“次关键次关键字字”。查找：查找：根据给定的某个值，在查找表中根据给定的某个值，在查找表中确定一个其关确定一个其关键字等于给定值的数据元素或（记录）键字等于给定值的数据元素或（记录）若查找表中存在这样一个记录，则称若查找表中存在这样一个记录，则称“查找成功查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；的位置；否则称否则称“查找不成功查找不成功”，查找结果：给出，查找结果：给出“空记录空记录”或或“空指针空指针”。9.1 静态查找表 顺序查找有序查找表（折半查找索
5、引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 4第九章第九章 查找查找如何进行查找？如何进行查找？取决于查找表的结构，即：记录在查找表中所处取决于查找表的结构，即：记录在查找表中所处的位置。的位置。然而，查找表本身是一种很松散的结构，因此，然而，查找表本身是一种很松散的结构，因此，为了提高查找的效率，需要在查找表中的元素之间人为为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来地附加某种确定的关系，换句话说，用另外一种结构来表示查找表。表示查找表。本章讨论
6、的重点：本章讨论的重点：查找表的各种表示方法及其相应的查找算法查找表的各种表示方法及其相应的查找算法 9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 59.1 9.1 静态查找表静态查找表 抽象数据类型静态查找表的定义抽象数据类型静态查找表的定义ADT StaticSearchTable 数据对象数据对象D：D是具有相同特性的数据元素的集是具有相同特性的数据元素的集 合。每个数据元素含有类型相同的关键字，可唯一标识合。每个数据元素含有类型相同的关键字，可
7、唯一标识数据元素。数据元素。数据关系数据关系R：数据元素同属一个集合。数据元素同属一个集合。基本操作基本操作P：Create(&ST,n);操作结果：构造一个含操作结果：构造一个含n个数据元素的静态查找表个数据元素的静态查找表 ST。Destroy(&ST);初始条件：静态查找表初始条件：静态查找表ST存在；存在；操作结果：销毁表操作结果：销毁表ST。9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 69.1 9.1 静态查找表静态查找表 抽象数据类型静态
8、查找表的定义抽象数据类型静态查找表的定义Search(ST,key);初始条件：静态查找表初始条件：静态查找表ST存在，存在，key为和查找表中为和查找表中元素的关键字类型相同的给定值；元素的关键字类型相同的给定值；操作结果：若操作结果：若ST中存在其关键字等于中存在其关键字等于key的数据元的数据元素，则函数值为该元素的值或在表中的位置，否则为素，则函数值为该元素的值或在表中的位置，否则为“空空”。Traverse(ST,Visit();初始条件：静态查找表初始条件：静态查找表ST存在，存在，Visit是对元素操作是对元素操作的应用函数；的应用函数；操作结果：按某种次序对操作结果：按某种次序
9、对ST的每个元素调用函数的每个元素调用函数Visit()一次且仅一次，一旦一次且仅一次，一旦Visit()失败，则操作失败。失败，则操作失败。ADT StaticSearchTable9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 7一一 线性表查找线性表查找-顺序查找顺序查找算法思想：算法思想：从表的一端开始，用给定值从表的一端开始，用给定值k与表中各个结点的键值逐个与表中各个结点的键值逐个比较：比较：查找成功查找成功-找出相等键值；找出相等键值；查找
10、失败查找失败-已到达表的另一端（可在此设置一个监视已到达表的另一端（可在此设置一个监视哨，作为下标越界的条件），即表中所有结点的键值都不哨，作为下标越界的条件），即表中所有结点的键值都不等于等于k。监视哨的作用监视哨的作用：作为越界（即已查完）的检测条件，省：作为越界（即已查完）的检测条件，省去在循环中每次均要判定是否越界，从而节省比较的时间。去在循环中每次均要判定是否越界，从而节省比较的时间。9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 8一一 线性
11、表查找线性表查找-顺序查找顺序查找静态查找表顺序查找算法静态查找表顺序查找算法typedef struct ElemType*elem;/数据元素存储空间基址，建数据元素存储空间基址，建表时按实际长度分配，表时按实际长度分配，0号单元留空号单元留空int length;/表的长度表的长度 SSTable;int Search_Seq(SSTable ST,KeyType key)/在顺序表在顺序表ST中顺序查找其关键字等于中顺序查找其关键字等于key的数据元素。的数据元素。若找到，则函数值为该元素在若找到，则函数值为该元素在 表中的位置，否则为表中的位置，否则为0。ST.elem0.key=k
12、ey;/“哨兵哨兵”for(i=ST.length;ST.elemi.key!=key;-i);/从后从后往前找往前找return i;/找不到时，找不到时，i为为0/Search_Seq9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 9一一 线性表查找线性表查找-顺序查找顺序查找回顾顺序表的查找算法：回顾顺序表的查找算法：int location(SqList L,ElemType&e,Status(*compare)(ElemType,ElemTyp
13、e)k=1;p=L.elem;while(k=L.length&!(*compare)(*p+,e)k+;if(k=L.length)return k;else return 0;/location上述算法中的基本操作是：上述算法中的基本操作是：compare，为了避免，为了避免“出出界界”，同时需作，同时需作k1000时，将时，将使算法的执行时间几乎增加一倍。使算法的执行时间几乎增加一倍。为此，改写顺序表的查找算法如上为此，改写顺序表的查找算法如上,算法中附设监视算法中附设监视哨，以避免循环时每一步都要判别是否数组出界。哨，以避免循环时每一步都要判别是否数组出界。9.1 静态查找表 顺序查找
14、有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 10一一 线性表查找线性表查找-顺序查找顺序查找设置哨兵的好处：设置哨兵的好处：i012n-3 n-2n-1n数组数组 ST.elem key8100100713 在顺序表中总可以找到待查结点。否则，必须将判断条在顺序表中总可以找到待查结点。否则，必须将判断条件件 i=0 加进加进 for 语句。语句。e.g:查找查找 key=8 的结点所在的数组元素的下标。的结点所在的数组元素的下标。iiiiiii查找失败，则查找失败，则 i=0;
15、9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 11 其中其中:n 为表长，为表长，Pi 为查找表中第为查找表中第i个记录的概率，且个记录的概率，且 一一 线性表查找线性表查找-顺序查找顺序查找顺序查找的时间性能分析顺序查找的时间性能分析定义：定义：查找算法的查找算法的平均查找长度平均查找长度(Average Search Length):为确定记录在查找表中的位置，需和给定值为确定记录在查找表中的位置，需和给定值进行进行比较的关键字个数的期望值：比较的
16、关键字个数的期望值：niiiCPASL111niiPCi为找到该记录时，曾和给定值比较过的关键字的个数为找到该记录时，曾和给定值比较过的关键字的个数，对顺序表而言对顺序表而言:Ci=n-i+1 ASL=nP1+(n-1)P2+2Pn-1+Pn9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 12一一 线性表查找线性表查找-顺序查找顺序查找顺序查找的时间性能分析顺序查找的时间性能分析在在等概率等概率查找的情况下查找的情况下nPi1顺序表查找的平均查找长度顺序
17、表查找的平均查找长度为：为：21111n)i(nnASLniss在不等概率查找的情况下，在不等概率查找的情况下，ASLss 在在PnPn-1 P2 P1 时取极小值。时取极小值。9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 13一一 线性表查找线性表查找-顺序查找顺序查找顺序查找的优缺点：顺序查找的优缺点：优点：优点：简单且适用面广，对表的结构没有要求，无论简单且适用面广，对表的结构没有要求，无论记录是否按关键字有序都可应用。记录是否按关键字有序都可应
18、用。缺点：缺点：效率低。效率低。上面讨论的前提是每次查找都是上面讨论的前提是每次查找都是“成功成功”的，但实际的，但实际上会产生查找上会产生查找“不成功不成功”的情况，如果查找不成功的情形不的情况，如果查找不成功的情形不容忽视时，查找算法平均查找长度应是查找成功时的平均查容忽视时，查找算法平均查找长度应是查找成功时的平均查找长度与查找不成功时的平均查找长度之和。找长度与查找不成功时的平均查找长度之和。假设查找成功和不成功的概率相等，即均为假设查找成功和不成功的概率相等，即均为1/2，则顺，则顺序查找的平均查找长度为：序查找的平均查找长度为：查找不成功时查找不成功时查找成功时查找成功时)1(43
19、21)1(211 nninnASLni9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 14二二 有序查找表有序查找表 上述顺序查找表的查找算法简单，但平均查找长度上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表较大，特别不适用于表长较大的查找表此时的查找算法可基于此时的查找算法可基于折半查找折半查找来完成来完成二分法的特点：二分法的特点：（1）线性表的表中结点必须按关键字有序；）线性表的表中结点必须按关键字有序；（2）线性表
20、须采用顺序存储结构。）线性表须采用顺序存储结构。二分法思想：二分法思想：（1）用给定的）用给定的k与有序表的中间位置与有序表的中间位置mid上的结点上的结点的关键字比较，若相等，查完；否则：的关键字比较，若相等，查完；否则：（2）若）若rmid.keyk)，则执行（，则执行（3）：）：（3）在右子表中继续进行二分查找。）在右子表中继续进行二分查找。9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 15二二 有序查找表有序查找表折半查找折半查找查找过程查找过
21、程是：是：(1)计算计算中间元素中间元素的序号，并取整：的序号，并取整：(2)中间元素中间元素r mid.key与与k比较比较:若若k=r mid.Key,查找查找成功成功；否则；否则若若kr mid.Key,则则low=mid+1,重复（重复（1）直到查找成功或不成功。直到查找成功或不成功。2highlowmid9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 16二二 有序查找表有序查找表.折半查找（示意）折半查找（示意）3 12 17 22 35 4
22、8 62 74 79 85 94 1 2 3 4 5 6 7 8 9 10 11MidHighLow High MidLow Mid找到找到22为第为第4号元素号元素例如，在有序表（例如，在有序表（3，12，17，22，35，48，62，74，79，85，94）中查找）中查找22的数据元素。的数据元素。9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 17二二 有序查找表有序查找表折半查找（示意）折半查找（示意）e.g:查找查找 key=25 的结点所在的
23、数组元素的下标地址。的结点所在的数组元素的下标地址。失败条件：失败条件：low high;处于间隙中的键值导致这种处于间隙中的键值导致这种情况！情况！3 12 17 22 35 48 62 74 79 85 94 1 2 3 4 5 6 7 8 9 10 11MidHighLow High MidLow MidLow midHigh 9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 18二二 有序查找表有序查找表算法算法:int Search_Bin(SS
24、Table ST,KeyType key)/在有序表在有序表ST中折半查找其关键字等于中折半查找其关键字等于key的数据元素。若找到，则的数据元素。若找到，则函数值为该元素在表中的位置，否则为函数值为该元素在表中的位置，否则为0。low=1;high=ST.length;/置区间初值置区间初值while(low=high)mid=(low+high)/2;if（key=ST.elemmid.key)return mid;/找到待查元素找到待查元素else if(key50)时时,ASLbslog2(n+1)-1折半查找法的优缺点：折半查找法的优缺点：优点：速度快优点：速度快 缺点：只能适用于有
25、序表，且仅限于顺序存储结构。缺点：只能适用于有序表，且仅限于顺序存储结构。1)1(log1212111.nnnjnCPASLhjjniii9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 222.2.索引顺序法索引顺序法（又称）分块查找（又称）分块查找存储方式：存储方式：线性表分成若干块，每个块内的元素的关键字不线性表分成若干块，每个块内的元素的关键字不一定有序（一定有序（“块内无序块内无序”）块与块之间必须按键值有序，即前一块中的最大块与块之间必须按键值
26、有序，即前一块中的最大键值小于后一块中的最小键值（键值小于后一块中的最小键值（“分块有序分块有序”）。）。附加索引表：附加索引表：索引表的一块索引表结点由索引表的一块索引表结点由键域键域、链域链域组成。组成。存放相应块存放相应块的最大键值的最大键值存放指向本块第一存放指向本块第一个结点的指针个结点的指针9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 232.2.索引顺序法索引顺序法索引顺序表索引顺序表=索引索引+顺序表顺序表一般情况下，索引是一个有序表一
27、般情况下，索引是一个有序表查找方法：查找方法：1）由索引确定记录所在区间；）由索引确定记录所在区间；2）在顺序表的某个区间内进行查找。）在顺序表的某个区间内进行查找。所以，这也是一种所以，这也是一种缩小区间缩小区间的查找方法。的查找方法。22171348 8622 12 13 8920 33 42 44 38 24 48 60 58 74 49 86 53索引表索引表最大关键字最大关键字起始地址起始地址 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 189.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡
28、二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 242.2.索引顺序法索引顺序法索引顺序表的平均查找长度索引顺序表的平均查找长度为在索引中进行查找为在索引中进行查找的平均查找长度和在顺序表中进行查找的平均查找长的平均查找长度和在顺序表中进行查找的平均查找长度之和。即：度之和。即：ASL Lb+Lw一般情况下，为进行分块查找，可将长度为一般情况下，为进行分块查找，可将长度为n的的表均匀地分成表均匀地分成b块，每块含有块，每块含有s个记录，即个记录，即b=n/s；再；再假定表中每个记录的查找概率相等，则每块查找的概假定表中每个记录的查找概率相等，则每块查找的概
29、率为率为1/b，块中每个记录的查找概率为，块中每个记录的查找概率为1/s。9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 252.2.索引顺序法索引顺序法性能分析：性能分析：1、索引表、顺序表皆顺序查找：、索引表、顺序表皆顺序查找：ASL=Lb+Lw b s =(j/b)+(i/s)j=1 i=1 =(b+1)/2+(s+1)/2 =(b+s)/2+1 当当 s=sqrt(n)时，时，ASL极小极小 ASL=sqrt(n)+1注意：注意：b:块数块数 s
30、:块内元素数，块内元素数，b=n/s2、索引表二分查找、顺序表顺序查找：、索引表二分查找、顺序表顺序查找：ASL=log2(n/s+1)+s/29.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 269.2.9.2.动态查找表动态查找表1 二叉排序树二叉排序树特点特点：用于频繁进行插入、删除、查找的所谓动：用于频繁进行插入、删除、查找的所谓动态查找表。态查找表。二叉排序树二叉排序树(Binary Sort Tree)或者是一棵空二叉树或者是一棵空二叉树；或者
31、具有下列性质的二叉树：；或者具有下列性质的二叉树：A，若它的左子树不空，则左子树上所有结点，若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；的值均小于它的根结点的值；B，若它的右子树不空，则右子树上所有结点，若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；的值均大于它的根结点的值；C，它的左右子树也分别为二叉排序树。，它的左右子树也分别为二叉排序树。实际上，折半查找法的判定树就是一棵二叉实际上，折半查找法的判定树就是一棵二叉排序树。排序树。二叉排序树又称二叉分类树。二叉排序树又称二叉分类树。9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表
32、二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 271 1 二叉排序树二叉排序树6391471025811122250300110200991052302169.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 281 1 二叉排序树二叉排序树二叉排序树的存储结构：二叉排序树的存储结构：typedef struct BinNodeKeyType key;/*结点的关键码字段结点的关键码字段*/D
33、ataType other;/*结点的属性字段结点的属性字段*/struct BinNode*llink,*rlink;/*二叉树的二叉树的左、右指针左、右指针*/BinNode,*PBinNode,BinTree,*PBinTree;9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 29二叉排序树的检索算法二叉排序树的检索算法BOOL searchNode(PBinTree ptree,KeyType key,PBinNode*position)/*若若
34、ptree中存在其关键字等于中存在其关键字等于key的数的数据元素，则函数值为真，否则为假据元素，则函数值为真，否则为假*/p=q=ptree;while(p!=NULL)q=p;if(p-key=key)/*检索成功检索成功*/*position=p;return(TRUE);else if(p-key key)/*进入左子树继续检索进入左子树继续检索*/p=p-llink;else/*进入右子树继续检索进入右子树继续检索*/p=p-rlink;*position=q;/*返回结点插入位置返回结点插入位置*/return(FALSE);/*检索失败检索失败*/9.1 静态查找表 顺序查找有序
35、查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 302.2.二叉排序树结点的插入二叉排序树结点的插入当树中不存在关键字等于给定值的结点时，需要生当树中不存在关键字等于给定值的结点时，需要生成新结点并插入到二叉树中。而新插入的结点必定是成新结点并插入到二叉树中。而新插入的结点必定是一个叶子结点，并且是查找不成功时查找路径上访问一个叶子结点，并且是查找不成功时查找路径上访问的最后一个结点左孩子或右孩子结点。的最后一个结点左孩子或右孩子结点。算法如下：算法如下：1.如果二叉排序树为空，则新结
36、点作为根结点。如果二叉排序树为空，则新结点作为根结点。2.如果二叉排序树非空，则将新结点的关键码与根结点如果二叉排序树非空，则将新结点的关键码与根结点的关键码比较，若小于根结点的关键码，则将新结点的关键码比较，若小于根结点的关键码，则将新结点插入到根结点的左子树中；否则，插入到右子树中。插入到根结点的左子树中；否则，插入到右子树中。3.子树中的插入过程和树中的插入过程相同，如此进行子树中的插入过程和树中的插入过程相同，如此进行下去，直到找到该结点，或者直到新结点成为叶子结下去，直到找到该结点，或者直到新结点成为叶子结点为止。点为止。9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.
37、2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 312.2.二叉排序树结点的插入二叉排序树结点的插入算法算法void InsertNode(PBinTree*T,KeyType key)/*若若T中不存在中不存在其关键字等于其关键字等于e.key的数据元素，则插入的数据元素，则插入e到到T。*/PBinTreeNode p,s;if(!SearchBST(*T,key,&p);s=(PBinTreeNode)malloc(sizeof(BinTreeNode);s-key=key;s-llink=s-rlink=N
38、ULL;if(!p)*T=s;else if(Compare(key,p-key)llink=s;/*作为左孩子作为左孩子*/elsep-rlink=s;/*作为右孩子作为右孩子*/return TRUE;else return FALSE;9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 322.2.二叉排序树结点的插入二叉排序树结点的插入建立二叉排序树建立二叉排序树若从空树出发，经过一系列的查找插入操作以后，若从空树出发，经过一系列的查找插入操作以后，
39、可生成一棵二叉树。设查找的关键字序列为可生成一棵二叉树。设查找的关键字序列为45,24,53,45,12,24,90,则生成二叉树的过程如下：则生成二叉树的过程如下：454524452453452453124524531290一个无序序列可以通过构造一棵二叉排序树而变成一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列。每次插入的新结点都是树中一个叶子结点，一个有序序列。每次插入的新结点都是树中一个叶子结点，因此在进行插入时不必移动其他结点。因此二叉排序树既因此在进行插入时不必移动其他结点。因此二叉排序树既有折半查找的特性，又采用了链表作存储结构。有折半查找的特性，又采用了链表作存储结构
40、。9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 333.3.二叉排序树结点的删除二叉排序树结点的删除和插入相反，删除在查找成功之后进行，并且要和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。可分排序树的特性。可分三种情况三种情况讨论：讨论：（1）被删除的结点）被删除的结点是叶子是叶子；（2）被删除的结点）被删除的结点只有左子树只有左子树或者或者只有右子树
41、只有右子树；（3）被删除的结点）被删除的结点既有左子树，也有右子树既有左子树，也有右子树。3.3.二叉排序树结点的删除二叉排序树结点的删除假设指针假设指针p指向要删除的结点指向要删除的结点,指针指针f指向指向*p的父结点，并且假设的父结点，并且假设*p是是*f的左孩子。的左孩子。A，若若*p是叶子结点，是叶子结点，由于由于删除叶子删除叶子结点不破坏整棵树的结点不破坏整棵树的结构，因此，只需要结构，因此，只需要修改其双亲结点的指针修改其双亲结点的指针即可。即可。B，若若*p只有左子树只有左子树PL或只有右子树或只有右子树PR，此时，只要，此时，只要令令PL或或PR直接成为其双亲结点直接成为其双亲
42、结点*f的左子树的左子树即可。（为什么？即可。（为什么？C,若若*p的左右子树的左右子树均不空均不空，在删除，在删除*p之前，中序遍历该之前，中序遍历该二叉树得到的序列为二叉树得到的序列为CLCQLQSLSPPRF删除删除*p之后，为保持其他元素之间的相对位置不变，可以有两之后，为保持其他元素之间的相对位置不变，可以有两种做法：种做法：其一是令其一是令*p的左子树为的左子树为*f的左子树，而的左子树，而*p的右子树为的右子树为*s（*p的直接前驱）的右子树的直接前驱）的右子树，如下图，如下图c；FPCCLQSPRQLSLfpcsqFCSSLPRCLfc(c)3.3.二叉排序树结点的删除二叉排序
43、树结点的删除其二是其二是令令*p的直接前驱（或直接后继）替代的直接前驱（或直接后继）替代*p，然后，然后从二叉排序树中删除它的直接前驱（或直接后继）从二叉排序树中删除它的直接前驱（或直接后继），如图，如图d所示，当以所示，当以*s代替代替*p时，由于时，由于*s只有左子树只有左子树SL，则删除，则删除*s之之后，只要令后，只要令SL为为*s的双亲结点的双亲结点*q的右子树即可。的右子树即可。FPPLPRfp(a)FPCCLQSPRQLSLfpcsq(b)FCSSLPRCLfc(c)FSfCQQLSLpcCLPRq(d)9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表
44、二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 36二叉排序树结点的删除算法二叉排序树结点的删除算法void Delete(PBinTree*p)/*删除删除*p所指向的结点，并重所指向的结点，并重接它的左右子树接它的左右子树*/if(!(*p)-rlink)/*右子树空，重接左子树右子树空，重接左子树*/q=*p;*p=(*p)-llink;free(q);else if(!(*p)-llink)/*左子树空，重接右子树左子树空，重接右子树*/q=*p;*p=(*p)-rlink;free(q);else/*左右子树均不空左右
45、子树均不空*/q=*p;s=(*p)-llink;while(s-rlink)/*向右走到尽头向右走到尽头*/q=s;s=s-rlink;(*p)-data=s-data;/*用用s替换替换p*/if(q!=*p)q-rlink=s-llink;elseq-llink=s-llink;free(s);9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 37二叉排序树结点的删除算法（递归）二叉排序树结点的删除算法（递归）Status DeleteBST(PBi
46、nTree*T,KeyType key)/*若二叉树中存在关键字等于若二叉树中存在关键字等于key的元素时，则删除的元素时，则删除该元素该元素*/if(!(*T)return FALSE;elseif(EQ(key,(*T)-data.key)Delete(T);else if(LT(key,(*T)-data.key)DeleteBST(&(*T)-llink,key);elseDeleteBST(&(*T)-rlink,key);9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理
47、方法Hash表的检索及分析 38二叉排序树结点的删除算法（非递归）二叉排序树结点的删除算法（非递归）void deleteNode(PBinTree*ptree,KeyType key)PBinNode parentp,p,parentr,r;p=*ptree;parentp=NULL;while(p!=NULL)/*本循环用来查找关键字本循环用来查找关键字*/if(p-key=key)break;/*找到了关键码为找到了关键码为key的结点的结点*/parentp=p;if(p-keykey)p=p-llink;/*进入左子树进入左子树*/else p=p-rlink;/*进入右子树进入右子
48、树*/if(p=NULL)return;/*二叉排序树中无关键码为二叉排序树中无关键码为key的的结点结点*/9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 39if(p-llink=NULL)/*结点结点*p无左子树无左子树*/if(parentp=NULL)*ptree=p-rlink;/*被删除的结被删除的结点是原二叉排序树的根结点点是原二叉排序树的根结点*/else if(parentp-llink=p)/*p是其父结点的左子女是其父结点的左子女
49、*/parentp-llink=p-rlink;/*将将*p的右子树链到其父的右子树链到其父结点的左链上结点的左链上*/else parentp-rlink=p-rlink;/*将将*p的右子树链的右子树链到其父结点的右链上到其父结点的右链上*/else/*结点结点*p有左子树有左子树*/r=p-llink;/*进入左子树进入左子树*/while(r-rlink!=NULL)r=r-rlink;/*在在*p的左子的左子树中找最右下结点树中找最右下结点*r*/r-rlink=p-rlink;/*用用*r的右指针指向的右指针指向*p的右子女的右子女*/if(parentp=NULL)*ptree=
50、p-llink;else if(parentp-llink=p)/*用用*p的左子女代替的左子女代替*p*/parentp-llink=p-llink;elseparentp-rlink=p-llink;free(p);/*释放被删除结点释放被删除结点*/9.1 静态查找表 顺序查找有序查找表（折半查找索引顺序法9.2.动态查找表二叉排序树最佳二叉排序树平衡二叉树B-树和B树9.3 哈希表哈希函数的构造方法碰撞处理方法Hash表的检索及分析 40二叉排序树结点查找二叉排序树结点查找性能分析性能分析在二叉排序树上查找关键字实际上是走了一条从根结在二叉排序树上查找关键字实际上是走了一条从根结点到某
