1、 基本概念基本概念 查找表：查找表：由同一类型的由同一类型的（或记录）构成的集合。（或记录）构成的集合。对查找表经常进行的操作：对查找表经常进行的操作：1、某个某个“特定的特定的”数据元素是否在查找表中；数据元素是否在查找表中；2、某个某个“特定的特定的”数据元素的各种属性；数据元素的各种属性；3、在查找表中、在查找表中插入插入一个数据元素；一个数据元素；4、删除删除查找表中的某个数据元素。查找表中的某个数据元素。静态查找表：静态查找表：作作“”（检索）操作的查找表。（检索）操作的查找表。动态查找表：动态查找表：作作“插入插入”和和“删除删除”操作的查找表。操作的查找表。具有相同的可辨认特性。
2、具有相同的可辨认特性。关键字关键字(key)：数据元素中某个数据项的值，用它可以数据元素中某个数据项的值，用它可以（识别）一个数据元素。（识别）一个数据元素。主关键字：主关键字：可以可以标示一个数据元素的关键字。标示一个数据元素的关键字。不同记录的主关键字不同。不同记录的主关键字不同。次关键字：次关键字：可标示若干个数据元素的关键字。可标示若干个数据元素的关键字。查找（检索）：查找（检索）：根据给定的某个值，在查找表中确定一个根据给定的某个值，在查找表中确定一个 关键字等于给定值的记录或数据元素。关键字等于给定值的记录或数据元素。例：例：学号学号 例：例：性别性别 查找成功：查找成功：即找到满
3、足条件的记录。即找到满足条件的记录。此时作为结果可报告该记录在查找表中的位置，此时作为结果可报告该记录在查找表中的位置，也可给出该记录的全部信息。也可给出该记录的全部信息。查找不成功查找不成功：即未找到满足条件的记录。即未找到满足条件的记录。作为结果可给出一个作为结果可给出一个“空空”记录或记录或“空空”指针。指针。用集合表示查找表：用集合表示查找表：数据元素之间的关系不作限定数据元素之间的关系不作限定 查询时无规律可循，只能对集查询时无规律可循，只能对集 合中的元素一一加以辨认合中的元素一一加以辨认。用其它结构表示查找表用其它结构表示查找表 （对查找表的元素人为对查找表的元素人为 地附加上某
4、种关系地附加上某种关系）问题：问题：如何进行查找如何进行查找 查找方法取决于查找表的结构。查找方法取决于查找表的结构。有序表：有序表：字典字典 索引表：索引表：电话号码表电话号码表 散列表散列表 树树 表表 9.1 静态查找表静态查找表 静态查找表的存储结构静态查找表的存储结构 顺顺 序序 表表线性链表线性链表 存储结构不同，实现查找操作的方法则不同。存储结构不同，实现查找操作的方法则不同。顺序查找顺序查找#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量线性表存储空间的初始分配量 typedef struct ElemType*elem;/数组指针，指示线性表
5、的基地址数组指针，指示线性表的基地址 int length;/当前长度当前长度 int listsize;/当前分配的存储容量当前分配的存储容量(以以sizeof(ElemType)为单位为单位)SqList;typedef struct ElemType *elem;int length;/表长度表长度 SSTable;静态查找表的顺序存储结构静态查找表的顺序存储结构 9.1.1 顺序表的查找（顺序查找）顺序表的查找（顺序查找）顺序查找：顺序查找：从表的一端开始，逐个进行记录的关从表的一端开始，逐个进行记录的关 键字和给定值的比较。键字和给定值的比较。查找过程：查找过程：0 1 2 3 4
6、5 6 7 8 9 10 11找找64 5 37 19 21 13 56 64 92 88 80 75 64 优点：优点：算法简单，适应面广。算法简单，适应面广。缺点：缺点：顺序查找顺序查找 算法描述：算法描述：int Search_Seq(SSTable ST,KeyType key)找找60ST.elem0.key=key;0 1 2 3 4 5 6 7 8 9 10 11 5 37 19 21 13 56 64 92 88 80 75 当当 ST.length=1000 时，此改进能使进行时，此改进能使进行 一次查找所需的平均一次查找所需的平均 时间几乎减少一半。时间几乎减少一半。60
7、监视哨监视哨 for(i=ST.length;ST.elemi.key!=key;-i)if(i=0)break;return i;查找方法评价：查找方法评价：；空间复杂度；算法本身复杂程度。；空间复杂度；算法本身复杂程度。因为因为查找算法的基本操作为：查找算法的基本操作为：将记录的关键字同给定值比较。将记录的关键字同给定值比较。平均查找长度平均查找长度 ASL(Average Search Length)所以所以以以期望值期望值作为衡量查找算法好坏的依据。作为衡量查找算法好坏的依据。找到第找到第 i 个记录个记录 需比较的次数。需比较的次数。niiiCPASL1对含有对含有 n 个记录的表，
8、查找个记录的表，查找时：时：第第 i 个记录被个记录被 查找的概率。查找的概率。11 niiP0 1 2 3 4 5 6 7 8 9 10 11 5 37 19 21 13 56 64 92 88 80 75 11 10 9 8 7 6 5 4 3 2 1 顺序查找的平均查找长度：顺序查找的平均查找长度：ASL=nP1+(n-1)P2+2Pn-1+Pn 假设每个记录的查找概率相等：假设每个记录的查找概率相等：Pi=1/n 则：则：niniiiSSninnCPASL1121)1(1 查找查找时，关键字的比较次数总是时，关键字的比较次数总是 n+1 次。次。0 1 2 3 4 5 6 7 8 9
9、10 11 5 37 19 21 13 56 64 92 88 80 75 11 10 9 8 7 6 5 4 3 2 1 假设：假设：1、查找成功与不成功的、查找成功与不成功的概率相同概率相同。2、每个记录被查找的、每个记录被查找的概率相同概率相同。则：则：平均查找长度（成功与不成功的平均查找长度之和）平均查找长度（成功与不成功的平均查找长度之和）为为 nnninnASL1iSS4)1(3)1(21)1(21 1、记录的查找概率不相等时如何提高查找效率？、记录的查找概率不相等时如何提高查找效率？查找表存储记录原则：查找表存储记录原则：1)、查找概率越高比较次数越少；查找概率越高比较次数越少；
10、2)、查找概率越低，比较次数较多。、查找概率越低，比较次数较多。2、记录的查找概率无法测定时如何提高查找效率？、记录的查找概率无法测定时如何提高查找效率？方法：方法：1)、在每个记录中设一个访问频度域；在每个记录中设一个访问频度域；2)、始终保持记录按非递增有序的次序排列；、始终保持记录按非递增有序的次序排列；3)、每次查找后均将刚查到的记录直接移至表头。、每次查找后均将刚查到的记录直接移至表头。9.1.2 有序表的查找（折半查找）有序表的查找（折半查找）有序表表示静态查找表有序表表示静态查找表 查找过程：查找过程：1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 5
11、6 64 75 80 88 92 找找21lowmidhigh 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找找63 lowhighmidHigh low 折半查找折半查找 算法描述：算法描述：int Search_Bin(SSTable ST,KeyType key)low=1;high=ST.length;/置区间初值置区间初值 while(low=high)mid=(low+high)/2;if(ST.elemmid.key=key)return mid;/找到待查元素找到待查元素 else if(key ST.elem
12、mid.key)high=mid-1;/继续在前半区间进行查找继续在前半区间进行查找 else low=mid+1;/继续在后半区间进行查找继续在后半区间进行查找 return 0;/顺序表中不存在待查元素顺序表中不存在待查元素 /Search_Bin 性能分析：性能分析：1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 1 2 2 3 3 3 3 4 4 4 4 Ci i 6 3 9 1 4 7 10 2 5 8 11 判定树判定树 表中一个记录表中一个记录 比较次数比较次数=路径上的结点数路径上的结点数 比较次数比较次数=结点结
13、点 4 的层数的层数 比较次数比较次数 树的深度树的深度 log2n +1 比较次数比较次数=路径上的内部结点数路径上的内部结点数 比较次数比较次数 log2n +1 -13-46-79-10 1-22-34-55-67-88-910-1111-平均查找长度平均查找长度ASL（成功时）：（成功时）：)50(1)1(log1)1(log1211221111 n n nnn jncncpASLhjjniiniiibs：则则 设表长设表长 n=2h 1，则，则 h=log2(n+1)（此时，判定树为（此时，判定树为 深度深度=h的满二叉树），且表中每个记录的查找概率相等：的满二叉树），且表中每个记录
14、的查找概率相等：Pi=1/n。第第 j 层的每个结点要比较的次数层的每个结点要比较的次数 第第 j 层层 结点数结点数 第第 j 层要比层要比 较的总次数较的总次数 21SSnASL折半查找折半查找：效率比顺序查找高。效率比顺序查找高。折半查找折半查找：只适用于只适用于，且限于，且限于。查查389.1.4 索引顺序表的查找（分块查找）索引顺序表的查找（分块查找）1、将表分成几块，且表或者有序，或者将表分成几块，且表或者有序，或者；1 7 1322 48 86索引表索引表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 查找过程：查找过程：先确定待查记录
15、所在块（顺序或折半查找），先确定待查记录所在块（顺序或折半查找），再在块内查找（顺序查找）。再在块内查找（顺序查找）。若若 i j，则第，则第 j 块中所块中所 有记录的关键字均大于有记录的关键字均大于 第第 i 块中的最大关键字块中的最大关键字 2、建立、建立“索引表索引表”（每个结点含有最大关键字域和指（每个结点含有最大关键字域和指 向本块第一个结点的指针，且按关键字有序）。向本块第一个结点的指针，且按关键字有序）。22 12 138920 33 42 44 38 24 48 60 58 74 57 86 53性能分析：性能分析：平均查找长度：平均查找长度：ASLbs=Lb+Lw 在块中查
16、找元素的平均查找长度在块中查找元素的平均查找长度 在索引表中查找所在块的平均查找长度在索引表中查找所在块的平均查找长度 1)(2121211111 ssnsbisjbASLsibjbs 若将长度为若将长度为 n 的表均分成的表均分成 b 块，每块含块，每块含 s 个记录个记录(b=n/s)；并设表中每个记录的查找概率相等，则每块查找的概率为并设表中每个记录的查找概率相等，则每块查找的概率为 1/b，块中块中每个记录的查找概率为每个记录的查找概率为 1/s。2)1(log211)1(log22ssnsbASLbs 。取取最最小小值值时时，取取可可以以证证明明，当当1 nASL n s bs(1)
17、、用顺序查找确定所在块：、用顺序查找确定所在块：(2)、用折半查找确定所在块：、用折半查找确定所在块：查找方法比较查找方法比较 顺序查找顺序查找折半查找折半查找分块查找分块查找ASL 最大最大最小最小中间中间表结构表结构有序表、无序表有序表、无序表有序表有序表分块有序分块有序存储结构存储结构顺序表、线性链表顺序表、线性链表顺序表顺序表顺序表、线性链表顺序表、线性链表9.1.3 静态树表的查找静态树表的查找 如果表中各个记录被查找的如果表中各个记录被查找的概率不同概率不同，那么折半查找，那么折半查找 是否是在有序表中进行查找的最好选择呢？是否是在有序表中进行查找的最好选择呢？关键字关键字:A B
18、 C D E Pi:0.2 0.3 0.05 0.3 0.15 Ci:2 3 1 2 3 例：例：CADBEBADCEASL=2 0.2+3 0.3+1 0.05+2 0.3+3 0.15=改变查找顺序（即：改变改变查找顺序（即：改变 Ci 的值）的值）Ci：2 1 3 2 3 ASL=2 0.2+1 0.3+3 0.05+2 0.3+3 0.15=1.9 若只考虑查找成功的情况，并为讨论方便起见引入常若只考虑查找成功的情况，并为讨论方便起见引入常 量量 c，令令 wi=cpi (i=1,2,n)，（，（pi 为结点被查找的概为结点被查找的概 率），则称率），则称 wi 为结点的为结点的“权权
19、”，并且称：，并且称：为为带权内路径长度之和带权内路径长度之和。其中：其中：n 为二叉树（判定树）上的结点个数（即：有序表为二叉树（判定树）上的结点个数（即：有序表 的长度）；的长度）；hi 为第为第 i 个结点在二叉树上的层次。个结点在二叉树上的层次。niiihwPH1 称称 PH 值取最小的二叉树为值取最小的二叉树为“”(Static Optimal Nearly Search Tree)。若某个二叉树的若某个二叉树的 PH 值在所有具有同样权值的二叉树值在所有具有同样权值的二叉树 中近似为最小，则称它为中近似为最小，则称它为“”(Nearly Optimal Search Tree)。（
20、近似近似最优查找树）最优查找树）假设按关键字从小到大有序排列的记录序列为：假设按关键字从小到大有序排列的记录序列为：(rl,rl+1,rh)其中其中 rl.key rl+1.key data.key)return(T);else if(key data.key)return(SearchBST(T-lchild,key);/在左子树中继续查找在左子树中继续查找 else return(SearchBST(T-rchild,key);/在右子树中继续查找在右子树中继续查找/SearchBST2.二叉排序树的插入和删除二叉排序树的插入和删除 1)、若二叉排序树为空树，则新插入的结点为根结点；、若二
21、叉排序树为空树，则新插入的结点为根结点；2)、若二叉排序树非空，则新插入的结点必为一个新、若二叉排序树非空，则新插入的结点必为一个新 的叶子结点，并且是查找不成功时查找路径上访的叶子结点，并且是查找不成功时查找路径上访 问的最后一个结点的左孩子或右孩子结点。问的最后一个结点的左孩子或右孩子结点。例：例：插入插入 40，插入插入 50，40 50 45 12 53 3 37 61 99 24 90 78 二叉排序树的插入二叉排序树的插入 是是 37 的右孩子。的右孩子。是是 53 的左孩子。的左孩子。修改修改53结点的左指针域结点的左指针域指向插入结点指向插入结点查找失败时，需要获得查找失败时，
22、需要获得插入结点双亲的指针插入结点双亲的指针查找算法：查找算法：Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree&p)/在根指针在根指针 T 所指二叉排序树中递归地查找其关键字等于所指二叉排序树中递归地查找其关键字等于 key /的数据元素，若查找成功，则指针的数据元素，若查找成功，则指针 p 指向该数据元素结点，指向该数据元素结点，/并返回并返回 TRUE，否则指针，否则指针 p 指向查找路径上访问的最后一个指向查找路径上访问的最后一个 /结点并返回结点并返回 FALSE，指针，指针 f 指向指向 T 的双亲，其初始调用值的双亲，其初
23、始调用值 /为为NULL。if(!T)p=f;return FALSE;/查找不成功查找不成功 else if(key=T-data.key)p=T;return TRUE;/查找成功查找成功 else if(key data.key)SearchBST(T-lchild,key,T,p);/在左子树中查找在左子树中查找 else SearchBST(T-rchild,key,T,p);/在右子树中查找在右子树中查找 /SearchBST 插入算法：插入算法：Status Insert BST(BiTree&T,ElemType e)/当二叉排序树当二叉排序树 T 中不存在关键字等于中不存在关
24、键字等于 e.key 的数据元素时，的数据元素时，/插入插入 e 并返回并返回 TRUE，否则返回，否则返回 FALSE if(!SearchBST(T,e.key,NULL,p)/查找不成功查找不成功 s=(BiTree)malloc(sizeof(BiTNode);s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;/插入插入 s 为新的根结点为新的根结点 else if(e.key data.key)p-lchild=s;/插入插入 s 为左孩子为左孩子 else p-rchild=s;/插入插入 s 为右孩子为右孩子 return TRUE;else r
25、eturn FALSE;/树中已有关键字相同的结点，不再插入树中已有关键字相同的结点，不再插入 /Insert BST 例：例：设查找的关键字序列为设查找的关键字序列为 45,24,53,45,12,24,90，生成的二叉排序树为：生成的二叉排序树为：1、中序遍历中序遍历二叉排序树二叉排序树可得到可得到一个关键字的一个关键字的有序序列有序序列。二叉排序树生成：二叉排序树生成：从空树出发，经过一系列的查找、插入从空树出发，经过一系列的查找、插入 操作之后，可生成一棵二叉排序树。操作之后，可生成一棵二叉排序树。4553249012 2、一个无序序列可通过构造二叉排序树而变成一个有序序列。、一个无序
26、序列可通过构造二叉排序树而变成一个有序序列。构造构造二叉排序树二叉排序树的过程就是对无序序列进行排序的过程。的过程就是对无序序列进行排序的过程。3、插入的结点均为叶子结点，故无需移动其他结点。、插入的结点均为叶子结点，故无需移动其他结点。相当于相当于在有序序列上插入记录而无需移动其他记录在有序序列上插入记录而无需移动其他记录。二叉排序树既有类似于折半查找的特性，二叉排序树既有类似于折半查找的特性，又采用了链表作存储结构。又采用了链表作存储结构。分析：分析：二叉排序树的删除二叉排序树的删除 在删除某个结点之后，仍然保持二叉排序树的特性。在删除某个结点之后，仍然保持二叉排序树的特性。删除二叉排序树
27、中的删除二叉排序树中的 p 结点，分三种情况讨论：结点，分三种情况讨论：1)、p 为叶子结点。为叶子结点。删除叶子结点不破坏树的结构，删除叶子结点不破坏树的结构，只需修改只需修改 p 双亲双亲 f 的指针：的指针：f-lchild=NULL 或或 f-rchild=NULL SPT 2)、p 只有左子树或右子树：只有左子树或右子树：中序遍历：中序遍历：PL S T 中序遍历：中序遍历：PL S T SPPLTSPLT中序遍历：中序遍历：Q S PL 中序遍历：中序遍历：Q S PL SPPLQSPLQ p 只有左子树，用只有左子树，用 p 的左孩子代替的左孩子代替 p；p 只有右子树，用只有右
28、子树，用 p 的右孩子代替的右孩子代替 p；SPPRTSPRT中序遍历：中序遍历：PR S T 中序遍历：中序遍历：PR S T 中序遍历：中序遍历：Q S PR 中序遍历：中序遍历：Q S PR SPPRQSPRQ中序：中序：CL C QL Q SL S PR F 中序：中序：CL C QL Q SL S PR F 3)、p 左、右子树均非空：左、右子树均非空：FPCPRCLQQLSSLFCPRCLQQLSSL用用 p 的直接前驱取代的直接前驱取代 p。FCPRCLQQLSSL 用用 p 的直接后继取代的直接后继取代 p。若若 p 的左子树的左子树无右子树，无右子树，用用 p 的左子树的左子
29、树取代取代 p。中序遍历：中序遍历：CL C PR F 中序遍历：中序遍历：CL C PR F FPCPRCLFCPRCLFPCPRCLQQLSSLFCPRCLQQLSSL中序：中序：CL C QL Q SL S PR F 中序：中序：CL C QL Q SL S PR F 作业：作业：9.2、9.3、9.8、9.9 3、二叉排序树的查找分析、二叉排序树的查找分析 二叉排序树上查找某关键字二叉排序树上查找某关键字 等于给定值的结点过程，其等于给定值的结点过程，其 实就是走了一条从根到该结实就是走了一条从根到该结 点的路径。点的路径。30802090854035883250查找关键字：查找关键字
30、：35 35比较的关键字次数比较的关键字次数 此结点所在层次数此结点所在层次数 最多的比较次数最多的比较次数 树的深度树的深度 二叉排序树的平均查找长度：二叉排序树的平均查找长度：452412375393(45,24,53,12,37,93)614)333221(61 ASL534512243793614)333221(61 ASL折半查找折半查找 判定树判定树(12,24,37,45,53,93)371245245393二叉排序树二叉排序树 452412375393621)654321(61 ASL最坏情况：最坏情况：插入的插入的 n 个元素从一开始就有序，个元素从一开始就有序，变成单支树的
31、形态！变成单支树的形态！此时树的深度为此时树的深度为 n;ASL=(n+1)/2 查找效率与顺序查找情况相同查找效率与顺序查找情况相同。含有含有 n 个结点的二叉排序树的个结点的二叉排序树的平均查找长度平均查找长度和树的和树的形态形态有关有关 最好情况：最好情况：ASL=log 2(n+1)1;树的深度为：树的深度为：log 2n +1;与折半查找中的判定树相同。与折半查找中的判定树相同。（形态比较均衡）。（形态比较均衡）。452412375393452412375393有有 n 个关键字的二叉排序树的平均查找长度个关键字的二叉排序树的平均查找长度 不失一般性，假设某个序列中有不失一般性，假设
32、某个序列中有 k 个关键字小于第一个个关键字小于第一个 关键字，即有关键字，即有 n k 1 个关键字大于第一个关键字，由它构个关键字大于第一个关键字，由它构 造的二叉排序树如下所示：造的二叉排序树如下所示：n-k-1k其平均查找长度是其平均查找长度是 n 和和 k 的函数：的函数：P(n,k)(0kn 1)设每种树态出现概率相同（即：设每种树态出现概率相同（即：n 个关键字可能出现个关键字可能出现 的的 n!种排列的可能性相同），则含种排列的可能性相同），则含 n 个关键字的二叉排个关键字的二叉排 序树的平均查找长度为：序树的平均查找长度为：10),(1)(nkknPnnPASLniinii
33、iCnCpknP111),(在在每个关键字每个关键字等概率查找等概率查找的情况下，的情况下，RiLirootniiCCCnCnknP11),(1 )1)1()(1()1)(11 knPknkPkn )1()1()(11 knPknkPkn由此由此 10)1()1()(111)(nkknPknkPknnnP 112)(21nkkPknCnnnnP log12)(可类似于解差分方程，可类似于解差分方程，此递归方程有解：此递归方程有解：有有 n 个关键字的二叉排序树的平均查找长度个关键字的二叉排序树的平均查找长度 设每种树态出现概率相同，查找每个关键字也是等概率的，设每种树态出现概率相同，查找每个关
34、键字也是等概率的，则二叉排序树的则二叉排序树的 nnASLlog)11(2 由此可见，在由此可见，在随机随机的情况下，二叉排序树的的情况下，二叉排序树的 ASL 和和 log n 是是等数量级等数量级的。的。如何提高如何提高形态不均衡的形态不均衡的二叉排序树的查找效率？二叉排序树的查找效率？做做“平衡化平衡化”处理，即尽量让二叉树的形状均衡！处理，即尽量让二叉树的形状均衡！4、平衡二叉树、平衡二叉树 平衡二叉树平衡二叉树又称又称 AVL 树，它是具有如下性质的二叉树：树，它是具有如下性质的二叉树：为了方便起见，给每个结点附加一个为了方便起见，给每个结点附加一个数字数字=该结点左子树与该结点左子
35、树与 右子树的深度差右子树的深度差。这个数字称为结点的。这个数字称为结点的。这样，可以得。这样，可以得 到到 AVL 树的其它性质（可以证明）：树的其它性质（可以证明）：即：即：|左子树深度右子树深度左子树深度右子树深度|1 左、右子树是平衡二叉树；左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值所有结点的左、右子树深度之差的绝对值 1。任一结点的平衡因子只能取：任一结点的平衡因子只能取：-1、0 或或 1；如果树中任意一个如果树中任意一个 结点的平衡因子的绝对值大于结点的平衡因子的绝对值大于 1，则这棵二叉树就失去平衡。，则这棵二叉树就失去平衡。对于一棵有对于一棵有 n 个结点的
36、个结点的 AVL 树，其树，其深度深度和和 log n 同数量级，同数量级，ASL 也和也和 log n 同数量级。同数量级。非平衡二叉树非平衡二叉树 例：例：判断下列二叉树是否判断下列二叉树是否 AVL 树？树？1-100-110平衡二叉树平衡二叉树 0012-10 如果在一棵如果在一棵 AVL 树中插入一个新结点后造成失衡，则树中插入一个新结点后造成失衡，则 必须必须，使之恢复平衡。，使之恢复平衡。我们称此调整平衡的过程为我们称此调整平衡的过程为。平衡旋转的类别平衡旋转的类别 LL 平衡旋转平衡旋转 RR 平衡旋转平衡旋转 LR 平衡旋转平衡旋转 RL 平衡旋转平衡旋转 若在若在 C 的的
37、左子树的左子树上插入左子树的左子树上插入 结点，使结点，使 C 的平衡因子从的平衡因子从 1 增加增加 至至 2，需要进行一次需要进行一次顺时针旋转顺时针旋转。(以以 B 为旋转轴）为旋转轴）A若在若在 A 的的右子树的右子树上插入右子树的右子树上插入 结点，使结点，使 A 的平衡因子从的平衡因子从-1 改变改变为为-2，需要进行一次，需要进行一次逆时针旋转逆时针旋转。(以以 B 为旋转轴）为旋转轴）2)RR 平衡旋转：平衡旋转：C1)LL 平衡旋转：平衡旋转：CBCABA若在若在 A 的的右子树的左子树上插入右子树的左子树上插入 结点，使结点，使 A 的平衡因子从的平衡因子从-1 改变改变
38、为为-2，需要，需要先进行顺时针旋转，先进行顺时针旋转，再逆时针旋转。再逆时针旋转。(以插入的结点以插入的结点 B 为旋转轴）为旋转轴）4)RL 平衡旋转：平衡旋转：C若在若在 C 的的左子树的右子树上插入左子树的右子树上插入 结点，使结点，使 C 的平衡因子从的平衡因子从 1 增加增加 至至 2，需要需要先进行逆时针旋转，先进行逆时针旋转，再顺时针旋转。再顺时针旋转。(以插入的结点以插入的结点 B 为旋转轴）为旋转轴）C3)LR 平衡旋转：平衡旋转：调整必须保证二叉排序树的特性不变调整必须保证二叉排序树的特性不变 CBABCCABABBACCBA013037024例：例：请将下面序列构成一棵
39、平衡二叉排序树：请将下面序列构成一棵平衡二叉排序树：(13,24,37,90,53)013037-113024-124-213090-124-137053190-237需要需要 RR 平衡平衡 旋转旋转(绕绕 24 逆逆转，转，24 为根为根)需要需要 RL 平衡平衡旋转（绕旋转（绕 53 先顺后逆）先顺后逆）-224037090053053037090-1249.2.2 B-树和树和 B+树树 1.B-树的定义树的定义 一棵一棵 m 阶的阶的 B-树，或为空树或为满足下列特性的树，或为空树或为满足下列特性的 m 叉树：叉树：F111271FF391991F6453473FFFFFFFF181
40、78432351t a b c d e f g h(1)、树中每个结点至多有、树中每个结点至多有 m 棵子树；棵子树；(2)、若根结点不是叶子结点，则至少有两棵子树；、若根结点不是叶子结点，则至少有两棵子树；(3)、除根之外的所有非终端结点至少有、除根之外的所有非终端结点至少有 m/2 棵子树；棵子树；阶阶 m 可以事先任意指定，可以事先任意指定，一旦指定后就固定不变。一旦指定后就固定不变。(4)、所有的非终端结点的结构为：（、所有的非终端结点的结构为：（n,A0,K1,A1,K2,A2,Kn,An）其中，其中，Ki(i=1,n)为按升序排列的关键字；为按升序排列的关键字；Ai (i=0,n)
41、为指向子树为指向子树 根结点的指针，且根结点的指针，且 Ai 所指子树中所有结点的关键字均小于所指子树中所有结点的关键字均小于 ki，An 所指子树所指子树 中所有结点的关键字均大于中所有结点的关键字均大于 kn，n(对于根结点对于根结点 1nm 1,对于其它结点对于其它结点 m/2 1 n m 1)为关键字的个数（或为关键字的个数（或 n+1 为子树个数）。为子树个数）。(5)、所、所有叶子结点在同一个层次上，且不含有任何信息。（可有叶子结点在同一个层次上，且不含有任何信息。（可 以看作是外部结点或查找失败的结点，实际上这些结点不以看作是外部结点或查找失败的结点，实际上这些结点不 存在，指向
42、这些结点的指针为空）。存在，指向这些结点的指针为空）。B-树特点树特点 平衡平衡 多路多路 查找查找 树中所有叶子结点均不带信息且在树的同一层次上；树中所有叶子结点均不带信息且在树的同一层次上；根结点或为叶子结点，或至少含有两棵子树；根结点或为叶子结点，或至少含有两棵子树；所有非叶子结点均含有所有非叶子结点均含有 n（m/2 nm）棵棵子树。子树。在在 m 阶的阶的 B-树上，每个非终端结点可能含有：树上，每个非终端结点可能含有：n 个关键字个关键字 Ki（1in）n m n 个指向记录的指针个指向记录的指针 Di（1in）n+1 个指向子树的指针个指向子树的指针 Ai（0in）非叶子结点中的
43、非叶子结点中的均均有序排列；有序排列；Ai-1 所指子树上所有关键字均小于所指子树上所有关键字均小于 Ki ；Ai 所指子树上所有关键字均大于所指子树上所有关键字均大于 Ki 。2.B-树的查找树的查找 F111271FF391991F6453473FFFFFFFF18178432351t a b c d e f g h 47 47 从根结点出发，沿指针从根结点出发，沿指针搜索结点搜索结点和在和在顺序（或折顺序（或折 半）半）两个过程交叉进行。两个过程交叉进行。若若查找成功查找成功，则，则返回指向返回指向被查关键字所在被查关键字所在结点的指针结点的指针和和关键关键 字在结点中的位置字在结点中的
44、位置；若若则则9.3 哈希表（散列表）哈希表（散列表）9.3.1 什么是哈希表什么是哈希表 以上讨论的表示查找表的各种结构的共同特点：以上讨论的表示查找表的各种结构的共同特点：记录在表中记录在表中 的的位置位置和它的和它的关键字关键字之间不存在一个确定的关系。之间不存在一个确定的关系。1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 顺序表：顺序表：0001 李李 0007 钱钱 0013 孙孙 0019 王王 0025 吴吴 0031 赵赵 0037 郑郑 0043 周周 0043 0013 0001 NULL 0037 0007
45、 0019 0025链表：链表：45 12 53 3 37 61 99 24 90 78 二叉排序树（可用二叉链表存储）：二叉排序树（可用二叉链表存储）：查找过程：查找过程：给定值依次和关键字集合中各关键字进行给定值依次和关键字集合中各关键字进行。查找的效率查找的效率取决于和给定值进行比较的关键字个数。取决于和给定值进行比较的关键字个数。用这类方法表示的查找表，用这类方法表示的查找表，。不同的表示方法，其差别在于：不同的表示方法，其差别在于：1)、关键字和给定值进行比关键字和给定值进行比较的顺序不同。较的顺序不同。2)、比较的结果不同：顺序查找有两种可能比较的结果不同：顺序查找有两种可能“=”
46、与与“”；其他查找有三种可能其他查找有三种可能“”。只有一个办法：只有一个办法：预先知道所查关键字在表中的位置。预先知道所查关键字在表中的位置。对于频繁使用的查找表，希望对于频繁使用的查找表，希望 ASL=0。即，要求：即，要求：记录在表中的位置和其关键字之间存在一种确定记录在表中的位置和其关键字之间存在一种确定 的关系。的关系。若以下标为若以下标为000 999 的有序顺序表表示之，则查找过程可以的有序顺序表表示之，则查找过程可以 简单进行：取给定值（学号）的后三位，不需要经过比较便可直简单进行：取给定值（学号）的后三位，不需要经过比较便可直 接从顺序表中找到待查关键字。接从顺序表中找到待查
47、关键字。例如：例如：为每年招收的为每年招收的 1000 名新生建立一张查找表，其关键名新生建立一张查找表，其关键 字为学号，其值的范围为字为学号，其值的范围为 xx000 xx999（前两位为年份）。（前两位为年份）。上例表明，记录的上例表明，记录的与记录在表中的与记录在表中的之间存在之间存在 一种对应（函数）关系。若记录的关键字为一种对应（函数）关系。若记录的关键字为 key，记录在表中的，记录在表中的 位置位置（称为称为）为为 f(key)，则称此函数，则称此函数 f(key)为为。hao,ian,un,i,u,hen,an,e,ai 例如：例如：对于如下对于如下 9 个关键字：个关键字：
48、设哈希函数设哈希函数 f(key)=(Ord(关键字首字母关键字首字母)-Ord(A)+1)/2 若添加关键字若添加关键字 Zhou，会出现什么情况，会出现什么情况 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Dai Chen Zhao Qian Sun Li Wu Han Ye 从这个例子可见：从这个例子可见：1)哈希函数是一个映像，即：哈希函数是一个映像，即：将关键字的集合映射到某个地址将关键字的集合映射到某个地址 集合上集合上。它的设置很灵活，只要使得关键字的哈希函数值都。它的设置很灵活，只要使得关键字的哈希函数值都 落在表长允许的范围之内即可；落在表长允许的范围之内
49、即可；2)由于哈希函数是一个由于哈希函数是一个，因此，在一般情况下，很容，因此，在一般情况下，很容 易产生易产生“”现象，即：现象，即：key1 key2，而，而 f(key1)=f(key2)。这种具有相同函数值的关键字称为这种具有相同函数值的关键字称为。3)很难找到一个不产生冲突的哈希函数。一般情况下，只能很难找到一个不产生冲突的哈希函数。一般情况下，只能 选择恰当的哈希函数，使冲突尽可能少地产生。选择恰当的哈希函数，使冲突尽可能少地产生。因此：在构造这种特殊的因此：在构造这种特殊的“查找表查找表”时，除了需要选择一个时，除了需要选择一个“好好”（其原则是尽可能地使任意一组关键字的哈希地址
50、其原则是尽可能地使任意一组关键字的哈希地址 分布在整个地址空间中，即用任意关键字作为哈希函数的自变分布在整个地址空间中，即用任意关键字作为哈希函数的自变 量其计算结果量其计算结果，以尽可能少产生冲突，以尽可能少产生冲突）的哈希函数之）的哈希函数之外；还需要找到一种外；还需要找到一种“处理冲突处理冲突”的方法。的方法。哈希表的定义：哈希表的定义：根据设定的哈希函数根据设定的哈希函数H(key)和所选中的处理冲突的方法建立和所选中的处理冲突的方法建立 的的。其基本思想是：以记录的关键字为自变量，根据哈希。其基本思想是：以记录的关键字为自变量，根据哈希 函数，计算出对应的哈希地址，并在此存储该记录的
