1、第九章第九章一、查找表一、查找表( (Search Table)Search Table)2第一节查找的概念第一节查找的概念n查找表是由同一类型的数据元素查找表是由同一类型的数据元素( (或记录或记录) )构成构成的集合的集合n对查找表的操作对查找表的操作: :1.1.查询某个查询某个“特定的特定的”数据元素是否在查找表中；数据元素是否在查找表中；2.2.检索某个检索某个“特定的特定的”数据元素的各种属性；数据元素的各种属性；3.3.在查找表中插入一个数据元素；在查找表中插入一个数据元素；4.4.从查找表中删去某个数据元素从查找表中删去某个数据元素第第10章查找章查找一、查找表一、查找表( (
2、分类分类) )3第一节查找的概念第一节查找的概念n静态查找表静态查找表仅作查询和检索操作的查找表。仅作查询和检索操作的查找表。n动态查找表动态查找表在查找过程中同时在查找过程中同时插入插入查找表中不存在的数据查找表中不存在的数据元素，或者从查找表中元素，或者从查找表中删除删除已存在的某个数据已存在的某个数据元素元素第第10章查找章查找二、关键字二、关键字( (Key)Key)4第一节查找的概念第一节查找的概念n关键字关键字是数据元素（或记录）中某个数据项的是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）值，用以标识（识别）一个数据元素（或记录）n主关键字：可以识别唯
3、一的一个记录的关键字主关键字：可以识别唯一的一个记录的关键字n次关键字：能识别若干记录的关键字次关键字：能识别若干记录的关键字第第10章查找章查找三、查找三、查找( (Searching)Searching)5第一节查找的概念第一节查找的概念n查找查找是根据给定的某个值，在查找表中确定一是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。个其关键字等于给定值的数据元素（或记录）。 n查找成功：在查找表中查找到指定的记录查找成功：在查找表中查找到指定的记录n查找不成功：在查找表中没有找到指定记录查找不成功：在查找表中没有找到指定记录第第10章查找章查找四、衡量查找算法的
4、标准四、衡量查找算法的标准6第一节查找的概念第一节查找的概念n时间复杂度时间复杂度n空间复杂度空间复杂度n平均查找长度平均查找长度ASLASL第第10章查找章查找五、平均查找长度五、平均查找长度( (ASL)ASL)7第一节查找的概念第一节查找的概念n平均查找长度定义为确定记录在表中的位置所平均查找长度定义为确定记录在表中的位置所进行的和关键字比较的次数的平均值进行的和关键字比较的次数的平均值 n n ASL = ASL = P Pi iC Ci i i=1 i=1nn n为查找表的长度，即表中所含元素的个数为查找表的长度，即表中所含元素的个数nP Pi i为查找第为查找第i i个元素的概率个
5、元素的概率( (PPi i=1=1) )nC Ci i是查找第是查找第i i个元素时同给定值个元素时同给定值K K比较的次数比较的次数第第10章查找章查找一、顺序查找一、顺序查找8第二节静态查找表第二节静态查找表n顺序查找算法是顺序表的查找方法顺序查找算法是顺序表的查找方法n在顺序查找算法中，以顺序表或线性链表表示在顺序查找算法中，以顺序表或线性链表表示静态查找表静态查找表第第10章查找章查找一、顺序查找一、顺序查找( (算法算法) )9第二节静态查找表第二节静态查找表n顺序查找算法：顺序查找算法：1.1.从表中最后一个记录开始从表中最后一个记录开始2.2.逐个进行记录的关键字和给定值的比较逐
6、个进行记录的关键字和给定值的比较3.3.若某个记录比较相等，则查找成功若某个记录比较相等，则查找成功4.4.若直到第若直到第1 1个记录都比较不等，则查找不成功个记录都比较不等，则查找不成功第第10章查找章查找一、顺序查找一、顺序查找( (算法实现算法实现) )第二节静态查找表第二节静态查找表int Search_Seq(SSTable ST, KeyType key) / 若查找成功，返回位置ST.elem0.key = key; / “哨兵”，for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前找return i; / 找不到时,i=0 / Se
7、arch_Seq设置“哨兵”的目的是省略对下标越界的检查，提高算法执行速度第第10章查找章查找一、顺序查找一、顺序查找( (举例举例) )第二节静态查找表第二节静态查找表第第10章查找章查找i=11找找64监视哨监视哨i=7i=8i=9i=10比较次数比较次数=5比较次数：比较次数：查找第查找第n个元素：个元素： 1查找第查找第n-1个元素：个元素：2.查找第查找第1个元素：个元素： n查找第查找第i个元素：个元素： n+1-i查找失败查找失败： n+1 0 1 2 3 4 5 6 7 8 9 10 1164513192137566475808892一、顺序查找一、顺序查找( (算法性能分析算
8、法性能分析) )12第二节静态查找表第二节静态查找表n对顺序表而言，对顺序表而言，C Ci i=n-i+1=n-i+1n在等概率查找的情况下，在等概率查找的情况下，P Pi i=1/n=1/nnASL=nASL=n* *P P1 1 +(n-1)P +(n-1)P2 2 + + 2P+ 2Pn-1n-1+ + P Pn n = (n+1)/2 = (n+1)/2第第10章查找章查找一、顺序查找一、顺序查找( (不等概率不等概率) )13第二节静态查找表第二节静态查找表n如果被查找的记录概率不等时，取如果被查找的记录概率不等时，取 P Pn nPPn-1n-1PP2 2PP1 1n若查找概率无法
9、事先测定，则查找过程采取的若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上的记录直接移至表尾的位置上第第10章查找章查找一、顺序查找一、顺序查找( (特点特点) )14第二节静态查找表第二节静态查找表n优点：优点：1.1.简单简单2.2.适应面广适应面广( (对表的结构无任何要求对表的结构无任何要求) )n缺点：缺点：1.1.平均查找长度较大平均查找长度较大2.2.特别是当特别是当n n很大时，查找效率很低很大时，查找效率很低第第10章查找章查找二、折半查找二、折半查找15第二节静态查找表第二节静
10、态查找表n折半查找算法是折半查找算法是有序表有序表的查找方法的查找方法n在折半查找算法中，静态查找表按关键字大小在折半查找算法中，静态查找表按关键字大小的次序，有序地存放在顺序表中的次序，有序地存放在顺序表中n折半查找的原理是：折半查找的原理是：1.1.先确定待查记录所在的范围先确定待查记录所在的范围( (前部分或后部分前部分或后部分) )2.2.逐步缩小逐步缩小( (一半一半) )范围直到找范围直到找( (不不) )到该记录为止到该记录为止第第10章查找章查找二、折半查找二、折半查找( (算法算法) )16第二节静态查找表第二节静态查找表1.n1.n个对象从小到大存放在有序顺序表个对象从小到
11、大存放在有序顺序表STST中中，k k为给定为给定值值2.2.设设lowlow、highhigh指向待查元素所在区间的下界、上界，指向待查元素所在区间的下界、上界，即即low=1, high=nlow=1, high=n3.3.设设midmid指向待区间的中点，即指向待区间的中点，即mid=(low+high)/2mid=(low+high)/24.4.让让k k与与midmid指向的记录比较指向的记录比较 若若k=k=STmid.keySTmid.key，查找成功查找成功 若若kkkSTmid.keySTmid.key，则则low=mid+1low=mid+1 下半区间下半区间 5.5.重复
12、重复3,43,4操作，直至操作，直至lowhighlowhigh时，查找失败。时，查找失败。第第10章查找章查找二、折半查找二、折半查找( (举例成功举例成功) )17第二节静态查找表第二节静态查找表第第10章查找章查找找找641 2 3 4 5 6 7 8 9 10 11513192137566475808892Low=1High=11mid=61 2 3 4 5 6 7 8 9 10 11513192137566475808892Low=7High=11mid=91 2 3 4 5 6 7 8 9 10 11513192137566475808892Low=7mid=7High=8二、折半
13、查找二、折半查找( (举例不成功举例不成功) )18第二节静态查找表第二节静态查找表n当下界当下界lowlow大于上界大于上界highhigh时，说明有序表中没时，说明有序表中没有关键字等于有关键字等于K K的元素，查找不成功的元素，查找不成功第第10章查找章查找1 2 3 4 5 6 7 8 9 10 11513192137566475808892High=6 Low=7找找59二、折半查找二、折半查找( (判定树判定树) )第二节静态查找表第二节静态查找表n判定树：描述查找过程的二叉树。判定树：描述查找过程的二叉树。n有有n n个结点的判定树的深度为个结点的判定树的深度为 loglog2
14、2n n +1+1n折半查找法在查找过程中进行的折半查找法在查找过程中进行的 比较次数最多不超过比较次数最多不超过 loglog2 2n n +1+1n有有1111个元素的表的例子个元素的表的例子第第10章查找章查找i123456789 10 11Ci342341342346391425781011二、折半查找二、折半查找( (性能分析性能分析) )第二节静态查找表第二节静态查找表n设有序表的长度设有序表的长度n=2n=2h h-1-1（即即h=h=loglog2 2(n+1)(n+1)）, ,则描则描述折半查找的判定树是深度为述折半查找的判定树是深度为h h的满二叉树的满二叉树n树中层次为树
15、中层次为1 1的结点有的结点有1 1个，层次为个，层次为2 2的结点有的结点有2 2个，层次为个，层次为h h的结点有的结点有2 2h-1h-1个个n假设表中每个记录的查找概率相等，则查找成假设表中每个记录的查找概率相等，则查找成功时折半查找的平均查找长度功时折半查找的平均查找长度第第10章查找章查找1)1(log12112111nnnjnCnASLhjjniibs二、折半查找二、折半查找( (特点特点) )第二节静态查找表第二节静态查找表n折半查找的效率比顺序查找高折半查找的效率比顺序查找高( (特别是在静态特别是在静态查找表的长度很长时查找表的长度很长时) )n折半查找只能适用于有序表，并
16、且以顺序存储折半查找只能适用于有序表，并且以顺序存储结构存储结构存储第第10章查找章查找三、分块查找三、分块查找22第二节静态查找表第二节静态查找表n分块查找是一种索引顺序表分块查找是一种索引顺序表( (分块有序表分块有序表) )查找查找方法，是折半查找和顺序查找的简单结合方法，是折半查找和顺序查找的简单结合n索引顺序表索引顺序表( (分块有序表分块有序表) )将整个表分成几块，将整个表分成几块，块内无序，块间有序块内无序，块间有序n所谓块间有序是指后一块表中所有记录的关键所谓块间有序是指后一块表中所有记录的关键字均大于前一块表中的最大关键字字均大于前一块表中的最大关键字第第10章查找章查找三
17、、分块查找三、分块查找( (分块有序表分块有序表) )23第二节静态查找表第二节静态查找表n主表：用数组存放待查记录主表：用数组存放待查记录, ,每每个数据元素至少含有关键字域个数据元素至少含有关键字域n索引表：每个结点含有最大关索引表：每个结点含有最大关键字域和指向本块第一个结点键字域和指向本块第一个结点的指针的指针第第10章查找章查找1 2 3 4 5 6 7 8 9 10 11519132175566437888092211755929主表索引表三、分块查找三、分块查找( (举例举例) )24第二节静态查找表第二节静态查找表n采用折半查找方法在索引表中找到块采用折半查找方法在索引表中找到
18、块 第第2 2块块 n用顺序查找方法在主表对用顺序查找方法在主表对 应块中找到记录应块中找到记录 第第3 3记录记录 第第10章查找章查找1 2 3 4 5 6 7 8 9 10 11519132175566437888092找找64211755929主表索引表三、分块查找三、分块查找( (性能分析性能分析) )25第二节静态查找表第二节静态查找表n若将长度为若将长度为n n的表分成的表分成b b块，每块含块，每块含s s个记录，个记录，并设表中每个记录查找概率相等并设表中每个记录查找概率相等n用折半查找方法在索引表中查找索引块，用折半查找方法在索引表中查找索引块，ASLASL块间块间logl
19、og2 2(n/s+1)(n/s+1)n用顺序查找方法在主表对应块中查找记录，用顺序查找方法在主表对应块中查找记录，ASLASL块内块内= =s/2s/2nASLASLloglog2 2(n/s+1) + s/2(n/s+1) + s/2第第10章查找章查找一、动态查找表一、动态查找表26第三节动态查找表第三节动态查找表n表结构本身是在查找过程中动态生成的表结构本身是在查找过程中动态生成的n若表中存在其关键字等于给定值若表中存在其关键字等于给定值keykey的记录的记录, ,表表明查找成功；明查找成功；n否则插入关键字等于否则插入关键字等于keykey的记录。的记录。第第10章查找章查找二、二
20、叉排序树二、二叉排序树27第三节动态查找表第三节动态查找表n空树或者是具有如下特性的二叉树：空树或者是具有如下特性的二叉树：. .若它的左子树不空，则左子树上所有结点的若它的左子树不空，则左子树上所有结点的值均小于根结点的值；值均小于根结点的值；. .若它的右子树不空，则右子树上所有结点的若它的右子树不空，则右子树上所有结点的值均大于根结点的值；值均大于根结点的值；. .它的左、右子树也都分别是二叉排序树。它的左、右子树也都分别是二叉排序树。第第10章查找章查找二、二叉排序树二、二叉排序树( (举例举例) )28第三节动态查找表第三节动态查找表第第10章查找章查找二叉排序树非二叉排序树5664
21、5923788198021137556645923788198021137560二、二叉排序树二、二叉排序树( (查找查找) )29第三节动态查找表第三节动态查找表n二叉排序树又称二叉查找树二叉排序树又称二叉查找树n查找算法：查找算法： 给定值与根结点比较：给定值与根结点比较：1.1.若相等，查找成功若相等，查找成功2.2.若小于，查找左子树若小于，查找左子树3.3.若大于，查找右子树若大于，查找右子树第第10章查找章查找在二叉排序树中查找关在二叉排序树中查找关键字值等于键字值等于3737, ,8888, ,9494566459237881980211375二、二叉排序树二、二叉排序树( (插
22、入插入) )30第三节动态查找表第三节动态查找表n二叉排序树是一种动态树表二叉排序树是一种动态树表n当树中不存在查找的结点时，作插入操作当树中不存在查找的结点时，作插入操作n新插入的结点一定是叶子结点（只需改动一个新插入的结点一定是叶子结点（只需改动一个结点的指针）结点的指针）n该叶子结点是查找不成功时路径上访问的最后该叶子结点是查找不成功时路径上访问的最后一个结点左孩子或右孩子一个结点左孩子或右孩子( (新结点值小于或大新结点值小于或大于该结点值于该结点值) )第第10章查找章查找二、二叉排序树二、二叉排序树( (插入举例插入举例) )31第三节动态查找表第三节动态查找表n插入结点插入结点9
23、494第第10章查找章查找56645923788198021137594二、二叉排序树二、二叉排序树( (生成举例生成举例) )32第三节动态查找表第三节动态查找表n画出在初始为空的二叉排序树中依次插入画出在初始为空的二叉排序树中依次插入56,64,92,80,88,7556,64,92,80,88,75时该树的生长全过程时该树的生长全过程第第10章查找章查找566492888056649280566492566456566492888075二、二叉排序树二、二叉排序树( (中序遍历中序遍历) )33第三节动态查找表第三节动态查找表n中序遍历二叉排序树，可得到一个关键字的有中序遍历二叉排序树，
24、可得到一个关键字的有序序列序序列, ,如如5,13,19,21,37,56,64,92,75,80,885,13,19,21,37,56,64,92,75,80,88第第10章查找章查找566459237881980211375二、二叉排序树二、二叉排序树( (删除删除) )34第三节动态查找表第三节动态查找表n删除二叉排序树中的一个结点后，必须保持二删除二叉排序树中的一个结点后，必须保持二叉排序树的特性（左子树的所有结点值小于根叉排序树的特性（左子树的所有结点值小于根结点，右子树的所有结点值大于根结点）结点，右子树的所有结点值大于根结点）n也即保持中序遍历后，输出为有序序列也即保持中序遍历后
25、，输出为有序序列第第10章查找章查找二、二叉排序树二、二叉排序树( (删除删除) )35第三节动态查找表第三节动态查找表n被删除结点具有以下三种情况：被删除结点具有以下三种情况：1.1.是叶子结点是叶子结点2.2.只有左子树或右子树只有左子树或右子树3.3.同时有左、右子树同时有左、右子树第第10章查找章查找二、二叉排序树二、二叉排序树( (删除删除) )36第三节动态查找表第三节动态查找表1.1.被删除结点是叶子结点被删除结点是叶子结点n直接删除结点，并让其父结点指向该结点的指直接删除结点，并让其父结点指向该结点的指针变为空针变为空第第10章查找章查找56645923788198021137
26、5删除结点88二、二叉排序树二、二叉排序树( (删除删除) )第三节动态查找表第三节动态查找表2.2.被删除结点只有左子树或右子树被删除结点只有左子树或右子树n删除结点删除结点, ,让其父结点指向该结点的指针指向其左子让其父结点指向该结点的指针指向其左子树树( (或右子树或右子树),),即用孩子结点替代被删除结点即可即用孩子结点替代被删除结点即可第第10章查找章查找56645928819802113755659237881980211375删除结点64(只有右子树)删除结点37(只有左子树)566459237881980211375原图二、二叉排序树二、二叉排序树( (删除删除) )38第三节
27、动态查找表第三节动态查找表3.3.被删除结点被删除结点p p既有左子树，既有左子树，又有右子树又有右子树n以中序遍历时的直接前驱以中序遍历时的直接前驱s s替代被删除结点替代被删除结点p p，然后然后再删除该直接前驱（只可再删除该直接前驱（只可能有左孩子）能有左孩子）第第10章查找章查找PCpFPRfCLQSLQLSqs二、二叉排序树二、二叉排序树( (删除删除) )39第三节动态查找表第三节动态查找表3.3.被删除结点既有左子树，又有右子树被删除结点既有左子树，又有右子树( (举例举例) )第第10章查找章查找56645923788198021137556649237881980215753
28、764592218880191375原图删除结点13删除结点56二、二叉排序树二、二叉排序树( (性能分析性能分析) )40第三节动态查找表第三节动态查找表n在最好的情况下，二叉排序树为一近似完全二在最好的情况下，二叉排序树为一近似完全二叉树时，其查找深度为叉树时，其查找深度为loglog2 2n n量级，即其时间量级，即其时间复杂性为复杂性为O(logO(log2 2n)n)第第10章查找章查找755619645372180138892二、二叉排序树二、二叉排序树( (性能分析性能分析) )第三节动态查找表第三节动态查找表n在最坏的情况下，二叉在最坏的情况下，二叉排序树为近似线性表时排序树为
29、近似线性表时( (如以升序或降序输入如以升序或降序输入结点时结点时) )，其查找深度，其查找深度为为n n量级，即其时间复量级，即其时间复杂性为杂性为O(nO(n) )第第10章查找章查找41808892647521191356375二、二叉排序树二、二叉排序树( (特性特性) )42第三节动态查找表第三节动态查找表n一个无序序列可以通过构造一棵二叉排序树而一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列（通过中序遍历）变成一个有序序列（通过中序遍历）n插入新记录时，只需改变一个结点的指针，相插入新记录时，只需改变一个结点的指针，相当于在有序序列中插入一个记录而不需要移动当于在有序序列
30、中插入一个记录而不需要移动其它记录其它记录n二叉排序树既拥有类似于折半查找的特性，又二叉排序树既拥有类似于折半查找的特性，又采用了链表作存储结构采用了链表作存储结构第第10章查找章查找二、二叉排序树二、二叉排序树( (特性特性) )43第三节动态查找表第三节动态查找表n但当插入记录的次序但当插入记录的次序不当时不当时( (如升序或降如升序或降序序) )，则二叉排序树深，则二叉排序树深度很深度很深(11)(11)，增加了，增加了查找的时间查找的时间第第10章查找章查找808892647521191356375三、平衡二叉树三、平衡二叉树 AVL(AVL(定义定义) )44第三节动态查找表第三节动
31、态查找表n平衡二叉树是二叉排序平衡二叉树是二叉排序( (查找查找) )树的另一种形式树的另一种形式n平衡二叉树又称平衡二叉树又称AVLAVL树树( (Adelsen-VelskiiAdelsen-Velskii and Landis) and Landis)n其特点为：树中每个结点的左、右子树深度之其特点为：树中每个结点的左、右子树深度之差的绝对值不大于差的绝对值不大于1 1，即，即| |h hL L-h-hR R| |1 1第第10章查找章查找566459237881980211375AVL树非AVL树565641913753780928821三、平衡二叉树三、平衡二叉树 AVLAVL( (
32、平衡因子平衡因子) )45第三节动态查找表第三节动态查找表n每个结点附加一个数字每个结点附加一个数字, , 给出该结点左子树的给出该结点左子树的高度减去右子树的高度所得的高度差高度减去右子树的高度所得的高度差, ,这个数这个数字即为结点的平衡因子字即为结点的平衡因子balance balance nAVLAVL树任一结点平衡因子只能取树任一结点平衡因子只能取 -1, 0, 1 -1, 0, 1第第10章查找章查找56564191375378092882100-10-1000100三、平衡二叉树三、平衡二叉树 AVLAVL( (平衡化旋转平衡化旋转) )46第三节动态查找表第三节动态查找表n如果
33、在一棵平衡的二叉查找树中插入一个新结如果在一棵平衡的二叉查找树中插入一个新结点，造成了不平衡。此时必须调整树的结构，点，造成了不平衡。此时必须调整树的结构，使之平衡化。使之平衡化。n平衡化旋转平衡化旋转( (处理处理) )有两类：有两类：1.1.单向旋转单向旋转 ( (单向右旋和单向左旋单向右旋和单向左旋) )2.2.双向旋转双向旋转 ( (先左后右旋转和先右后左旋转先左后右旋转和先右后左旋转) )第第10章查找章查找三、平衡二叉树三、平衡二叉树 AVL(AVL(平衡化旋转平衡化旋转) )47第三节动态查找表第三节动态查找表n每插入一个新结点时每插入一个新结点时, , AVLAVL树中相关结点
34、的平树中相关结点的平衡状态会发生改变。衡状态会发生改变。n在插入一个新结点后，需要从插入位置沿通向在插入一个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子。根的路径回溯，检查各结点的平衡因子。n如果在某一结点发现高度不平衡，停止回溯。如果在某一结点发现高度不平衡，停止回溯。n从发生不平衡的结点起，沿刚才回溯的路径取从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。直接下两层的结点。第第10章查找章查找三、平衡二叉树三、平衡二叉树 AVLAVL( (平衡化单向旋转平衡化单向旋转) )48第三节动态查找表第三节动态查找表n如果这三个结点处于一条直线上如果这三个结点处于一条
35、直线上(“/”(“/”型或型或“”“”型型) )，则采用单向旋转进行平衡化，则采用单向旋转进行平衡化n单向旋转分为单向右旋单向旋转分为单向右旋(“/”(“/”型型) )和单向左旋和单向左旋(“”(“”型型) )第第10章查找章查找ACBCBA单向左旋ACBABC单向右旋三、平衡二叉树三、平衡二叉树 AVLAVL( (平衡化双向旋转平衡化双向旋转) )49第三节动态查找表第三节动态查找表n如果这三个结点处于一条折线上如果这三个结点处于一条折线上(“”(“”“”型型) )，则采用双向旋转进行平衡化。，则采用双向旋转进行平衡化。n双旋转分为先左后右双旋转分为先左后右(“”(“”(“”型型) )第第1
36、0章查找章查找ACB先左后右旋转BCA先右后左旋转ACBACBABCABC三、平衡二叉树三、平衡二叉树 AVLAVL( (单向右旋单向右旋) )50第三节动态查找表第三节动态查找表n在在B B左子树左子树B BL L上插入新结点使其高度增上插入新结点使其高度增1 1，导致，导致结点结点A A的平衡因子增到的平衡因子增到 +2 +2，造成不平衡。，造成不平衡。第第10章查找章查找hhhAARBRBBLhh+1BAARBRBLhhh+1ARBRABBLh三、平衡二叉树三、平衡二叉树 AVLAVL( (单向右旋单向右旋) )51第三节动态查找表第三节动态查找表n为使树恢复平衡，从为使树恢复平衡，从A
37、 A沿插入路径连续取沿插入路径连续取3 3个结个结点点A A、B B和和B BL L(“/”(“/”型型) )n以结点以结点B B为旋转轴，将结点为旋转轴，将结点A A顺时针顺时针( (右右) )旋转。旋转。第第10章查找章查找hhhAARBRBBLhh+1BAARBRBLhhh+1ARBRABBLh三、平衡二叉树三、平衡二叉树 AVLAVL( (单向左旋单向左旋) )52第三节动态查找表第三节动态查找表n在在B B右子树右子树B BR R中插入新结点，该子树高度增中插入新结点，该子树高度增1 1导导致结点致结点A A的平衡因子变成的平衡因子变成-2-2，出现不平衡。，出现不平衡。第第10章查
38、找章查找hhhABBRALBLhhh+1ALABBRBLhhh+1BBRAALBL三、平衡二叉树三、平衡二叉树 AVLAVL( (单向左旋单向左旋) )53第三节动态查找表第三节动态查找表n沿插入路径检查三个结点沿插入路径检查三个结点A A、B B和和B BR R(“”(“”型型) )n以结点以结点B B为旋转轴，让结点为旋转轴，让结点A A反时针反时针( (左左) )旋转旋转第第10章查找章查找hhhABBRALBLhhh+1ALABBRBLhhh+1BBRAALBL三、平衡二叉树三、平衡二叉树 AVLAVL( (先左后右双向旋转先左后右双向旋转) )54第三节动态查找表第三节动态查找表n在
39、在C C的子树的子树C CL L或或C CR R中插入新结点，该子树的高度中插入新结点，该子树的高度增增1 1。结点。结点A A的平衡因子变为的平衡因子变为+2+2，发生了不平衡，发生了不平衡第第10章查找章查找hhAARCBLh-1h-1BCLCRhhAh-1hARCBLBCLCR三、平衡二叉树三、平衡二叉树 AVLAVL( (先左后右双向旋转先左后右双向旋转) )55第三节动态查找表第三节动态查找表n从结点从结点A A起沿插入路径选取起沿插入路径选取3 3个结点个结点A A、B B和和C(“”C(“”D(“”型型) )n以结点以结点B B为旋转轴，作单向右旋为旋转轴，作单向右旋第第10章查
40、找章查找hhABBRh-1hALCLCRChhABhALCLCRh-1CBR三、平衡二叉树三、平衡二叉树 AVLAVL( (先右后左双向旋转先右后左双向旋转) )59第三节动态查找表第三节动态查找表n再以结点再以结点C C为旋转轴，作单向左旋为旋转轴，作单向左旋第第10章查找章查找hhABBRh-1hALCLCRChhAh-1hBBRCALCLCR三、平衡二叉树三、平衡二叉树 AVLAVL( (举例举例) )60第三节动态查找表第三节动态查找表n画出在初始为空的画出在初始为空的AVLAVL树中依次插入树中依次插入64,5,13,21,19,80,75,37,5664,5,13,21,19,80
41、,75,37,56时该树的生长过时该树的生长过程，并在有旋转时说出旋转的类型。程，并在有旋转时说出旋转的类型。第第10章查找章查找64645645左右双旋564521641234三、平衡二叉树三、平衡二叉树 AVLAVL( (续例续例) )61第三节动态查找表第三节动态查找表n继续插入继续插入19,80,75,37,5619,80,75,37,56时该树的生长过程，时该树的生长过程，并在有旋转时说出旋转的类型。并在有旋转时说出旋转的类型。第第10章查找章查找556421195641921三、平衡二叉树三、平衡二叉树 AVLAVL( (续例续例) )62第三节动态查找表第三节动态查找表n继续插入
42、继续插入19,80,75,37,5619,80,75,37,56时该树的生长过程，时该树的生长过程，并在有旋转时说出旋转的类型。并在有旋转时说出旋转的类型。第第10章查找章查找652180196456419132180三、平衡二叉树三、平衡二叉树 AVLAVL( (续例续例) )63第三节动态查找表第三节动态查找表n继续插入继续插入19,80,75,37,5619,80,75,37,56时该树的生长过程，时该树的生长过程，并在有旋转时说出旋转的类型。并在有旋转时说出旋转的类型。第第10章查找章查找713519758021647564135802119三、平衡二叉树三、平衡二叉树 AVLAVL(
43、 (续例续例) )64第三节动态查找表第三节动态查找表n继续插入继续插入19,80,75,37,5619,80,75,37,56时该树的生长过程，时该树的生长过程，并在有旋转时说出旋转的类型。并在有旋转时说出旋转的类型。第第10章查找章查找8755136437801921三、平衡二叉树三、平衡二叉树 AVLAVL( (续例续例) )65第三节动态查找表第三节动态查找表n继续插入继续插入19,80,75,37,5619,80,75,37,56时该树的生长过程，时该树的生长过程，并在有旋转时说出旋转的类型。并在有旋转时说出旋转的类型。第第10章查找章查找9565756413371921807513
44、5216456803719三、平衡二叉树三、平衡二叉树( (删除删除) )66第三节动态查找表第三节动态查找表n如果被删结点如果被删结点A A最多只有一个孩子，那么将结最多只有一个孩子，那么将结点点A A从树中删去，并将其双亲指向它的指针指从树中删去，并将其双亲指向它的指针指向它的唯一的孩子，并作平衡化处理向它的唯一的孩子，并作平衡化处理n如果被删结点如果被删结点A A没有孩子，则直接删除之，并没有孩子，则直接删除之，并作平衡化处理作平衡化处理n如果被删结点如果被删结点A A有两个子女，则用该结点的直有两个子女，则用该结点的直接前驱接前驱S S替代被删结点，然后对直接前驱替代被删结点，然后对直
45、接前驱S S作删作删除处理除处理( (S S只有一个孩子或没有孩子只有一个孩子或没有孩子) )第第10章查找章查找四、四、B-/B+B-/B+树树67第三节动态查找表第三节动态查找表n移至移至1717周上周上第第10章查找章查找一、哈希表一、哈希表( (散列表散列表) )68第四节哈希表第四节哈希表n哈希哈希( (Hash)Hash)表又称散列表表又称散列表n散列表是一种直接计算记录存放地址的方法，散列表是一种直接计算记录存放地址的方法，它在关键码与存储位置之间直接建立了映象。它在关键码与存储位置之间直接建立了映象。第第10章查找章查找一、哈希表一、哈希表( (函数函数) )69第四节哈希表第
46、四节哈希表n哈希函数是从关键字空间到存储地址空间的一哈希函数是从关键字空间到存储地址空间的一种映象种映象n哈希函数在记录的关键字与记录的存储地址之哈希函数在记录的关键字与记录的存储地址之间建立起一种对应关系。可写成：间建立起一种对应关系。可写成：addr(aaddr(ai i)= )= H(keyH(keyi i) )nH(H() )为哈希函数为哈希函数nkeykeyi i是表中元素是表中元素a ai i关键字关键字, ,addr(aaddr(ai i) )是存储地址是存储地址第第10章查找章查找一、哈希表一、哈希表( (查找查找) )70第四节哈希表第四节哈希表n哈希查找也叫散列查找，是利用
47、哈希函数进行哈希查找也叫散列查找，是利用哈希函数进行查找的过程。查找的过程。n首先利用哈希函数及记录的关键字计算出记录首先利用哈希函数及记录的关键字计算出记录的存储地址的存储地址n然后直接到指定地址进行查找然后直接到指定地址进行查找n不需要经过比较，一次存取就能得到所查元素不需要经过比较，一次存取就能得到所查元素第第10章查找章查找一、哈希表一、哈希表( (冲突冲突) )71第四节哈希表第四节哈希表n不同的记录，其关键字通过哈希函数的计算，不同的记录，其关键字通过哈希函数的计算，可能得到相同的地址可能得到相同的地址n把不同的记录映射到同一个散列地址上，这种把不同的记录映射到同一个散列地址上，这
48、种现象称为冲突现象称为冲突第第10章查找章查找一、哈希表一、哈希表( (定义定义) )72第四节哈希表第四节哈希表n根据设定的根据设定的哈希函数哈希函数 H(keyH(key) ) 和所选中的和所选中的处理处理冲突冲突的方法的方法n将一组关键字映象到一个有限的、地址连续的将一组关键字映象到一个有限的、地址连续的地址集地址集 ( (区间区间) ) 上上n并以关键字在地址集中的并以关键字在地址集中的“象象”作为相应记录作为相应记录在表中的存储位置在表中的存储位置n如此构造所得的查找表称之为如此构造所得的查找表称之为“哈希表哈希表”第第10章查找章查找二、哈希函数二、哈希函数( (均匀性均匀性) )
49、73第四节哈希表第四节哈希表n哈希函数实现的一般是从一个大的集合（部分哈希函数实现的一般是从一个大的集合（部分元素，空间位置上一般不连续）到一个小的集元素，空间位置上一般不连续）到一个小的集合（空间连续）的映射合（空间连续）的映射n一个好的哈希函数，对于记录中的任何关键字，一个好的哈希函数，对于记录中的任何关键字，将其映射到地址集合中任何一个地址的概率应将其映射到地址集合中任何一个地址的概率应该是相等的该是相等的n即关键字经过哈希函数得到一个即关键字经过哈希函数得到一个“随机的地址随机的地址”第第10章查找章查找二、哈希函数二、哈希函数( (要求要求) )74第四节哈希表第四节哈希表n哈希函数
50、应是简单的，能在较短的时间内计算哈希函数应是简单的，能在较短的时间内计算出结果。出结果。n哈希函数的定义域必须包括需要存储的全部关哈希函数的定义域必须包括需要存储的全部关键字，如果散列表允许有键字，如果散列表允许有 m m 个地址时，其值个地址时，其值域必须在域必须在 0 0 到到 m-1 m-1 之间。之间。 n散列函数计算出来的地址应能均匀分布在整个散列函数计算出来的地址应能均匀分布在整个地址空间中地址空间中第第10章查找章查找二、哈希函数二、哈希函数( (直接定址法直接定址法) )75第四节哈希表第四节哈希表n直接定址法中，哈希函数取关键字的线性函数直接定址法中，哈希函数取关键字的线性函
