第七章 查找1.ppt

1第七章 查找n查找的基本概念查找的基本概念n顺序表、有序表和索引表的查找顺序表、有序表和索引表的查找n二叉平衡树，二叉平衡树，B-树、树、B+树的查找树的查找n散列表的查找散列表的查找2有关概念与术语n关关键键字字n数据元素中的一个数据项，可以标识数据元素数据元素中的一个数据项，可以标识数据元素n主关键字，次关键字主关键字，次关键字n查查找表找表n具有同一属性的数据元素的集合具有同一属性的数据元素的集合n分分为为静静态查态查找表找表和和动态查动态查找表找表两两类类n查查找找n给定关键字值给定关键字值K K，在表中找出关键字等于给定值，在表中找出关键字等于给定值K K的结点的结点n若找到，则查找成功，返回该结点的信息或该结点在表中若找到，则查找成功，返回该结点的信息或该结点在表中的位置的位置n否则查找失败，返回相关的指示信息否则查找失败，返回相关的指示信息3typedefstruct KeyTypekey；/关键字字段关键字字段 /其它字段其它字段 ElemType；数据元素类型说明4n查查找效率找效率n占用存占用存储储空空间间多少多少n算法本身复算法本身复杂杂程度程度n平均平均查查找找长长度度ASL(AverageSearchLength)n为为确定确定记录记录在表中的位置，需和在表中的位置，需和给给定定值进值进行行比比较较的关的关键键字的个数的期望字的个数的期望值值查找方法评价5n静态查找问题静态查找问题n查找过程中数据是不变的查找过程中数据是不变的n静静态查态查找表找表结结构构n顺顺序表序表n线线性性链链表表静态查找表6顺顺序存序存储储：typedefstructelemtype*v；/数数组组基址基址intlength；/表长度表长度S；S*data;data=(S*)malloc(sizeof(S);data-v=(elemtype*)malloc(sizeof(elemtype)*N);静态查找表的存储结构链链式存式存储储：typedefstructnodeelemtypeelem;structnode*next;nodetype；顺顺序存序存储储：#defineMAXSIZE1024typedefstructelemtypevMAXSIZE；intlength；S；Sdata;7查查找找过过程程从表的一端开始从表的一端开始逐个逐个进进行行记录记录的关的关键键字和字和给给定定值值的比的比较较i找找640123456789101151319213756647580889264监视哨监视哨iiii比较次数比较次数=5比较的次数：比较的次数：查找第查找第n个元素：个元素：1查找第查找第n-1个元素：个元素：2.查找第查找第1个元素：个元素：n查找第查找第i个元素：个元素：n-i+1查找失败查找失败：n+1顺序查找8顺序查找的ASLn查找成功时，平均查找长度约为元素个数的一半查找成功时，平均查找长度约为元素个数的一半9顺序查找算法分析n顺序查找的优点顺序查找的优点n算法简单算法简单n顺序表或用链表均适用顺序表或用链表均适用n结点是否按关键字有序，都同样适用结点是否按关键字有序，都同样适用n顺序查找的缺点顺序查找的缺点n查找效率低查找效率低n提高顺序查找的效率提高顺序查找的效率n合理安排节点位置，使访问越频繁的数据，合理安排节点位置，使访问越频繁的数据，比较的次数越少比较的次数越少 10n二分二分查查找找n条件条件n顺顺序表序表n表中数据元素表中数据元素按关按关键键字有序字有序 n基本思想基本思想n每次将待每次将待查记录查记录所在区所在区间缩间缩小一半小一半折半查找1105，13，19，21，37，56，64，75，80，88，92查找的关键字查找的关键字K=21。n05，13，19，21，37，56，64，75，80，88，92n05，13，19，21，37，56，64，75，80，88，92n05，13，19，21，37，56，64，75，80，88，9212 mid=mid=折半查找的基本思想n基本思想基本思想n(1)确定查找区间的中点确定查找区间的中点midn(2)将待查的将待查的K值与值与seqlistmid.key比较比较n(3)若相等，若相等，查找成功并返回查找成功并返回此位置此位置n(4)若不相等，确定新的查找区间若不相等，确定新的查找区间,返回返回(1),n重新开始二分法查找重新开始二分法查找n(5)当上下界相等时当上下界相等时,结束查找过程结束查找过程13二分查找算法分析n二分查找过程可用二叉树来描述二分查找过程可用二叉树来描述n已知表中有已知表中有n个结点个结点n以当前查找区间的中点为作为根以当前查找区间的中点为作为根n左半区和右半区中的结点分别作为根的左子树左半区和右半区中的结点分别作为根的左子树和右子树。和右子树。n由此得到的二叉树，称为二分查找的由此得到的二叉树，称为二分查找的判定树判定树(DecisionTree)或或比较树比较树(ComparisonTree)14二分查找算法分析92888075645637211913512345678910116910781152413n二分查找的判定树二分查找的判定树nO(log2(n)内部结点内部结点内部结点内部结点外部结点外部结点外部结点外部结点15二分查找的优点和缺点n虽然二分查找的效率高，但是要将表按关键字排序虽然二分查找的效率高，但是要将表按关键字排序 n只适用于顺序存储结构只适用于顺序存储结构n为保持表的有序性，在顺序结构里插入和删除都必为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点须移动大量的结点 n适用于表结点比较稳定的，很少做插入或删除操作适用于表结点比较稳定的，很少做插入或删除操作的顺序表的顺序表n不适用于链表不适用于链表16分块查找（索引顺序查找）n查查找找过过程程n将表分成几将表分成几块块，块块内无序，内无序，块间块间有序有序n先确定待先确定待查记录查记录所在所在块块，再在，再在块块内内查查找找n适用条件适用条件n后一个子表中后一个子表中,所有所有记录记录的关的关键键字均大于前一个字均大于前一个子表中的最大关子表中的最大关键键字字n算法算法实现实现n顺顺序存序存储储待待查记录查记录,每个数据元素包含关每个数据元素包含关键键字域字域n建立索引表，每个索引表建立索引表，每个索引表结结点含有最大关点含有最大关键键字字域和指向本域和指向本块块第一个第一个结结点的指点的指针针17分块查找分块查找表存储结构分块查找表存储结构分块查找表由分块查找表由“分块有序分块有序”的线性表和索引表组成的线性表和索引表组成块间有序，块内无序块间有序，块内无序索引表有序索引表有序221283920334244382448605874498653061222488618分块查找#definen3/定义块数定义块数typedefstruct intkey;/索引键值索引键值intaddr;/块起始位置块起始位置idtable;/索引表结点索引表结点idtableidn;typedefstructnodekeytypekey；/KeyType由用户定义由用户定义infotypeotherinfo；/此类型依赖于应用此类型依赖于应用NODE；/数据表结点数据表结点NODEDATA100;19算法思想算法思想首先查找索引表首先查找索引表索引表是有序表，可采用二分查找或顺序查找，索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块以确定待查的结点在哪一块若找不到索引块，则待查结点不在表内若找不到索引块，则待查结点不在表内否则，在已确定的块中进行顺序查找否则，在已确定的块中进行顺序查找块内无序，只能用顺序查找块内无序，只能用顺序查找在块起始地址到块在块起始地址到块结束地址结束地址之间进行查找之间进行查找分块查找算法20分块查找算法分析分块查找是两次查找过程，其平均查找长度是两次查分块查找是两次查找过程，其平均查找长度是两次查找的平均查找长度之和找的平均查找长度之和以二分查找来确定块以二分查找来确定块，分块查找成功时的平均查找长，分块查找成功时的平均查找长度度(b:块数块数,s:块中结点个数块中结点个数)ASLblk=ASLbn+ASLsqlog2(b)+(s+1)/2log2(n/s)+s/2以顺序查找确定块以顺序查找确定块，分块查找成功时的平均查找长度，分块查找成功时的平均查找长度ASLblk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)当当s=n1/2,ASLblk取极小值取极小值1+n1/221分块查找算法分析表中有表中有10000个结点个结点顺序查找顺序查找平均比较平均比较5000次次二分查找二分查找平均比较平均比较10次次分块查找分块查找将其分成将其分成100个数据块，每块含个数据块，每块含100个数据元素个数据元素顺序查找确定块，块内顺序查找，平均比较顺序查找确定块，块内顺序查找，平均比较100次次分块查找的效率于顺序和二分查找之间分块查找的效率于顺序和二分查找之间并不一定要将块分成均等大小并不一定要将块分成均等大小一个学校的学生登记表一个学校的学生登记表可以班为块，将各块存放于不可以班为块，将各块存放于不同的顺序表同的顺序表(或单链表或单链表)中中利用索引表访问各班利用索引表访问各班22查找方法的比较顺序查找顺序查找折半查找折半查找分块查找分块查找ASL最大最大最小最小两者之间两者之间表结构表结构有序表有序表无序表无序表有序表有序表分块有序表分块有序表存储结构存储结构顺序存储顺序存储线性链表线性链表顺序存储顺序存储顺序存储顺序存储线性链表线性链表23n插值查找通过下列公式求取中点，插值查找通过下列公式求取中点，n其中其中low和和high分别为表的两个端点下标，分别为表的两个端点下标，kx为给为给定值。定值。n若若 kxtbl.elemmid.key，则则low=mid+1，继续继续右半区查找；右半区查找；n若若 kx=tbl.elemmid.key，查找成功。查找成功。静态查找有序表的插值查找思想24静态查找有序表的斐波那契查找n斐波那契查找通过斐波那契数列对有序表进行分斐波那契查找通过斐波那契数列对有序表进行分割割n查找区间的两个端点和中点都与斐波那契数有关查找区间的两个端点和中点都与斐波那契数有关n斐波那契数列定义如下：斐波那契数列定义如下：25静态查找有序表的斐波那契查找n分割的思想分割的思想n对对于表于表长为长为F(i)-1的有序表，以相的有序表，以相对对low偏移量偏移量F(i-1)-1取中点，即取中点，即mid=low+F(i-1)-1，对对表表进进行行分割分割n则则左子表表左子表表长为长为F(i-1)-1，右子表表，右子表表长为长为F(i)-1-F(i-1)-1-1=F(i-2)-1n可可见见，两个子表表，两个子表表长长也都是某个斐波那契数也都是某个斐波那契数-1，因而，可以因而，可以对对子表子表继续继续分割。分割。26动态查找表 二叉排序树n二叉排序二叉排序树树定定义义n二叉排序二叉排序树树或者是一棵空或者是一棵空树树；或者；或者满满足如下性足如下性质质n若左子若左子树树不空，不空，则则左子左子树树上所有上所有结结点的点的值值均小于均小于根根结结点的点的值值n若右子若右子树树不空，不空，则则右子右子树树上所有上所有结结点的点的值值均大于均大于根根结结点的点的值值n左右子左右子树树本身也都是二叉排序本身也都是二叉排序树树n按中序遍历该树得到的序列是递增有序的按中序遍历该树得到的序列是递增有序的27n以二叉以二叉链链表作表作为为二叉排序二叉排序树树的存的存储结储结构构typedefintKeyType；typedefcharInfoType;typedefstructnodeKeyTypekey；/结点的键值结点的键值InfoTypeotherinfo；/结点的其他信息结点的其他信息structnode*lchild，*rchild；/孩子指针孩子指针bstnode；二叉排序树的存储结构28二叉排序树的生成n二叉排序树生成二叉排序树生成n从空树出发，经过一系列的从空树出发，经过一系列的插入操作插入操作之后，可生之后，可生成一棵二叉排序树成一棵二叉排序树n插入原则插入原则n若二叉排序树为空，则插入结点应为新的根结点若二叉排序树为空，则插入结点应为新的根结点n否则，在其左、右子树上查找，直至某个结点的否则，在其左、右子树上查找，直至某个结点的左子树或右子树为空为止，则插入结点应为该结左子树或右子树为空为止，则插入结点应为该结点的左孩子或右孩子点的左孩子或右孩子29二叉排序树的生成n输入结点序列输入结点序列(5(5，3 3，7 7，2 2，4 4，8)8)n生成二叉排序树的过程生成二叉排序树的过程 n中序遍历后得到结点的递增中序遍历后得到结点的递增(递减递减)序列序列55325375372537425374830练习题2015301711219n已知结点序列，构造二叉排序树已知结点序列，构造二叉排序树n20,15,30,21,11,9,1731二叉排序树的查找算法n二叉排序二叉排序树树的的查查找找过过程程n 若若查查找找树为树为空，空，查查找失找失败败。n 查查找找树树非空，将非空，将给给定定值值kx与与查查找找树树的根的根结结点点关关键键字比字比较较。n 若相等，若相等，查查找成功，找成功，结结束束查查找找过过程，否程，否则则n当当给给kx小于根小于根结结点关点关键键字，字，查查找将在以左孩找将在以左孩子子为为根的子根的子树树上上继续进继续进行，行，转转n当当给给kx大于根大于根结结点关点关键键字，字，查查找将在以右孩找将在以右孩子子为为根的子根的子树树上上继续进继续进行，行，转转32二叉排序树的查找算法和二分查找类似，是逐步缩小查找范围的过程：和二分查找类似，是逐步缩小查找范围的过程：bstnode*search(bstnode*t，KeyTypekey)if(t=NULL|key=t-key)returnt；if(keykey)returnsearch(t-lchild，key)；elsereturnsearch(t-rchild，key)；33二叉排序树的查找算法分析n平均查找长度和二叉树的形态有关平均查找长度和二叉树的形态有关n二叉排序树是把表的二叉排序树是把表的n个结点依次插入生成的个结点依次插入生成的n最坏情况，二叉排序树是深度为最坏情况，二叉排序树是深度为n的单支树，其平均查的单支树，其平均查找长度和顺序查找相同，是找长度和顺序查找相同，是(n+1)/2n5,4,3,2,1n最好情况，生成的二叉排序树，其形态比较匀称，得最好情况，生成的二叉排序树，其形态比较匀称，得到与二分查找的判定树形态相似的二叉排序树到与二分查找的判定树形态相似的二叉排序树n9,5,11,7,4,10n此时平均查找长度大约是此时平均查找长度大约是log2n。n插入、删除和查找算法的时间复杂度均为插入、删除和查找算法的时间复杂度均为O(log2n)。34n原原则则n从二叉排序树中删除一个结点，不能把以该结点从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，为根的子树都删去，n要保证删除后所得的二叉树仍然满足要保证删除后所得的二叉树仍然满足BST性质性质n算法思想算法思想n查找待删除结点查找待删除结点n若树中找不到被删结点则返回，否则删除结点若树中找不到被删结点则返回，否则删除结点p二叉排序树的删除35二叉排序树的删除n删除结点删除结点pn删除时，应将删除时，应将p的子树的子树(若有若有)仍连接在树上，且仍连接在树上，且保持保持BST性质不变。性质不变。n删除结点删除结点p的三种情况的三种情况np是叶子是叶子(左右孩子均为空左右孩子均为空)np没有子树，只需将没有子树，只需将p的双亲的双亲parent中指向中指向p的的指针域置空即可指针域置空即可np有一个孩子有一个孩子n将将child和和p的双亲连接，即可删去的双亲连接，即可删去*p。36np有两个孩子有两个孩子n令令q=p，将被删结点的地址保存在，将被删结点的地址保存在q中中n找找p的中序后继结点的中序后继结点fn在查找过程中用在查找过程中用parent记住记住f的双亲的双亲np的中序后继结点，是的中序后继结点，是p的右子树中最左下的结的右子树中最左下的结点，它无左子树。点，它无左子树。n此时，将删去此时，将删去p的操作变成删去的操作变成删去p的中序后继的中序后继f的的操作操作n将将f的值复制到的值复制到p中中n删除结点删除结点f删除二叉排序树中的p结点的讨论37S SQQP PL LP P中序遍历：中序遍历：Q S PQ S PL L P PS SQQP PL L中序遍历：中序遍历：Q S PQ S PL L(2)(2)S SP PP PL LQQ中序遍历：中序遍历：P PL L P S Q P S QS SP PL LQQ中序遍历：中序遍历：P PL L S Q S Q(1)(1)38中序遍历：中序遍历：P PP PR R S Q S QS SP PR RQQ中序遍历：中序遍历：P PR R S Q S Q(3)(3)S SP PP PR RQQ中序遍历：中序遍历：Q S P PQ S P PR RS SQQP PR R中序遍历：中序遍历：Q S PQ S PR R(4)(4)S SQQP PR RP P39F FP PC CP PR RC CL LQQQQL LS SS SL L中序遍历：中序遍历：C CL L C Q C QL L Q S Q SL L S P P S P PR R F FF FS SC CP PR RC CL LQQQQL LS SL L中序遍历：中序遍历：C CL L C Q C QL L Q S Q SL L S P S PR R F F(5)(5)F FP PC CP PR RC CL L中序遍历：中序遍历：C CL L C P P C P PR R F FF FC CP PR RC CL L中序遍历：中序遍历：C CL L C P C PR R F F(6)(6)40例例例例808050501201206060110110150150555570705353删除删除删除删除505080806060120120110110150150555570705353删除删除删除删除6060808055551201201101101501505353707010104 425258 813135 54 4删除删除删除删除10108 84 425255 513134 4删除删除删除删除5 58 84 425254 41313二叉排序树的删除41二叉排序树的查找算法分析n平均时间性能平均时间性能,二叉排序树的查找和二分查找差不多二叉排序树的查找和二分查找差不多n就维护表的有序性而言，二叉排序树无须移动结点，就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且其平均的只需修改指针即可完成插入和删除操作，且其平均的执行时间均为执行时间均为O(log2n)，因此更有效。，因此更有效。n二分查找涉及的有序表是顺序表，插入和删除操作中，二分查找涉及的有序表是顺序表，插入和删除操作中，为维护表的有序性所花的代价是为维护表的有序性所花的代价是O(n)n当有序表是静态查找表时，宜用顺序表作为存储结构，当有序表是静态查找表时，宜用顺序表作为存储结构，采用二分查找实现查找操作采用二分查找实现查找操作n若有序表是动态查找表，则应选择二叉排序树作为其若有序表是动态查找表，则应选择二叉排序树作为其存储结构。存储结构。42n对给对给定序列建立二叉排序定序列建立二叉排序树树n若若左左右右子子树树均均匀匀分分布布，则则其其查查找找过过程程类类似似于于有有序表的折半序表的折半查查找。找。n若若给给定定序序列列原原本本有有序序，则则建建立立的的二二叉叉排排序序树树就就蜕蜕化化为单链为单链表，其表，其查查找效率同找效率同顺顺序序查查找一找一样样n需需对对均均匀匀的的二二叉叉排排序序树树进进行行插插入入或或删删除除结结点点后后，应应对对其其调调整，使其依然保持均匀。整，使其依然保持均匀。平衡二叉树的引入43n平平衡衡二二叉叉树树或或者者是是一一棵棵空空树树，或或者者是是具具有有下下列列性性质质的二叉排序的二叉排序树树n它的左子它的左子树树和右子和右子树树都是平衡二叉都是平衡二叉树树n左左子子树树和和右右子子树树高高度度之之差差的的绝绝对对值值(平平衡衡因因子子)不超不超过过1 1平衡二叉树(AVL树)的定义4445非平衡二叉树的调整n在在平平衡衡二二叉叉树树上上插插入入或或删删除除结结点点后后，可可能能使使树树失失去去平平衡衡，因因此此，需需要要对对失失去去平平衡衡的的树树进进行行平平衡衡化化调调整整n调调整的原整的原则则n应应该该是是处处理理与与扦扦入入点点最最近近的的、而而平平衡衡因因子子又又比比1大或比大或比-1小的小的结结点。点。46n左左单单旋旋转转（LL型的型的处处理）理）n右右单单旋旋转转（RR型的型的处处理）理）n先左后右双向旋先左后右双向旋转转（LR型的型的处处理）理）n先右后左双向旋先右后左双向旋转转（RL型的型的处处理）理）非平衡二叉树的调整47非平衡二叉树的调整 平衡处理平衡处理平衡处理平衡处理 1 A B C 0 2 C B A 0 0 0 LLLL型平衡处理型平衡处理型平衡处理型平衡处理 nLL型的处理型的处理(左左型左左型)n在在C的左孩子的左孩子B上扦入一个左孩子结点上扦入一个左孩子结点A，使，使C的的平衡因子由平衡因子由1变成了变成了2，成为不平衡的二叉树序树。，成为不平衡的二叉树序树。这时的平衡处理为：将这时的平衡处理为：将C顺时针旋转，成为顺时针旋转，成为B的的右子树，而原来右子树，而原来B的右子树则变成的右子树则变成C的左子树，的左子树，待扦入结点待扦入结点A作为作为B的左子树。的左子树。48非平衡二叉树的调整nLR型的处理型的处理(左右型左右型)n在在C的左孩子的左孩子A上扦入一个右孩子上扦入一个右孩子B，使，使C的平衡的平衡因子由因子由1变成了变成了2，成为不平衡的二叉排序树。这，成为不平衡的二叉排序树。这是的平衡处理为：将是的平衡处理为：将B变到变到A与与C之间，使之成之间，使之成为为LL型，然后按第型，然后按第(1)种情形种情形LL型处理。型处理。0 0-1 1 C C A A B B 2 2 B B 0 0 0 0 C C A A 0 0 平衡处理平衡处理平衡处理平衡处理 旋转旋转旋转旋转 0 0 1 1 C C A A B B 2 2 LRLR型平衡处理型平衡处理型平衡处理型平衡处理 49非平衡二叉树的调整nRR型的处理型的处理(右右型右右型)n在在A的右孩子的右孩子B上扦入一个右孩子上扦入一个右孩子C，使，使A的平衡因的平衡因子由子由-1变成变成-2，成为不平衡的二叉排序树。这时的，成为不平衡的二叉排序树。这时的平衡处理为：将平衡处理为：将A逆时针旋转，成为逆时针旋转，成为B的左子树，的左子树，而原来而原来B的左子树则变成的左子树则变成A的右子树，待扦入结点的右子树，待扦入结点C成为成为B的右子树。的右子树。平衡处理平衡处理平衡处理平衡处理 C C B B A A 0 0 0 0 0 0 -1 1 C C B B A A 0 0-2 2 RRRR型平衡处理型平衡处理型平衡处理型平衡处理50非平衡二叉树的调整nRL型的处理型的处理(右左型右左型)n在在A的右孩子的右孩子C上扦入一个左孩子上扦入一个左孩子B，使，使A的平衡因的平衡因子由子由-1变成变成-2，成为不平衡的二叉排序树。这时的，成为不平衡的二叉排序树。这时的平衡处理为：将平衡处理为：将B变到变到A与与C之间，使之成为之间，使之成为RR型，型，然后按第然后按第(3)种情形种情形RR型处理。型处理。平衡处理平衡处理平衡处理平衡处理 C C B B A A 0 0 0 0 0 0 -1 1-2 2 C C B B A A 旋转旋转旋转旋转 B B 0 0 1 1-2 2 A A C C RLRL型平衡处理型平衡处理型平衡处理型平衡处理51非平衡二叉树的生成举例n给定一个关键字序列给定一个关键字序列4,5,7,2,1,3,6，试生成一棵，试生成一棵平衡二叉树。平衡二叉树。n分析分析n平衡二叉树实际上也是一棵二叉排序树，故可平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树的思想建立，在建立的过以按建立二叉排序树的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。最后就可以建成一棵平衡二叉树。52非平衡二叉树的生成举例 (c)(c)插入插入插入插入 7 7 RRRR型型型型 (a)(a)插入插入插入插入 4 4 4 4 0 0(b)(b)插入插入插入插入 5 5 4 4 5 5 0 0-1 1 7 7 4 4 5 5-2 2-1 1 0 0 0 0 0 0 4 4 5 5 7 7 0 0 53 LLLL型型型型(e e)插入插入插入插入 11 4 4 2 2 5 5 7 7 1 1 0 0 0 0 0 0 0 0 0 0 4 4 2 2 5 5 7 7 1 1 0 0 0 0 1 1 2 2 2 2 (d d)插入插入插入插入 2 2 4 4 2 2 5 5 7 7 0 0 0 0 1 1 1 1 非平衡二叉树的生成举例54 -1 1 5 5 2 2 1 1 4 4 3 3 7 7 2 2 0 0 1 1 0 0 0 0 5 5 2 2 1 1 4 4 3 3 7 7-1 1 0 0 0 0 0 0 0 0 0 0 LRLR型型型型 (f f)插入插入插入插入 3 3 非平衡二叉树的生成举例55非平衡二叉树的生成举例 5 5 2 2 1 1 4 4 3 3 7 7-2 2-1 1 0 0 1 1 0 0 0 0 6 6 0 0 RLRL型型型型 0 0 6 6 2 2 1 1 4 4 3 3 7 7 0 0 0 0 0 0 0 0 0 0 5 5 0 0(g g)插入插入插入插入6 6 56平衡二叉树的查找及性能分析n平衡二叉平衡二叉树树本身就是一棵二叉排序本身就是一棵二叉排序树树，故它的，故它的查查找与二叉排序找与二叉排序树树完全相同完全相同n但它的但它的查查找找性能性能优优于二叉排序于二叉排序树树，不像二叉排序，不像二叉排序树树一一样样，会出，会出现现最坏的最坏的时间时间复复杂杂度度O(n)n它的它的时间时间复复杂杂度与二叉排序度与二叉排序树树的最好的最好时间时间复复杂杂相相同，都同，都为为O(log2n)。57平衡二叉树的查找及性能分析n对给定的关键字序列对给定的关键字序列4,5,7,2,1,3,6，试用二叉排，试用二叉排序树和平衡二叉树两种方法查找，给出查找序树和平衡二叉树两种方法查找，给出查找6的的次数及成功的平均查找长度。次数及成功的平均查找长度。58平衡二叉树的查找性能优于二叉排序树。平衡二叉树的查找性能优于二叉排序树。平衡二叉树的查找性能优于二叉排序树。平衡二叉树的查找性能优于二叉排序树。平衡二叉树的查找及性能分析n从上图的二叉排序树可知，查找从上图的二叉排序树可知，查找6需需4次，平均次，平均查找长度查找长度nASL=(1+2+2+3+3+3+4)/7=18/72.57。n从上图的平衡二叉树可知，查找从上图的平衡二叉树可知，查找6需需2次，平均次，平均查找长度查找长度nASL=(1+2+2+3+3+3+3)=17/72.43。59第七章 查找n查找的基本概念查找的基本概念n顺序表、有序表和索引表的查找顺序表、有序表和索引表的查找n二叉平衡树二叉平衡树nB-树、树、B+树的查找树的查找n散列表的查找散列表的查找60学习要点n熟练掌握顺序表和有序表的查找方法。熟练掌握顺序表和有序表的查找方法。n熟悉静态查找树的构造方法和查找算法，理解静熟悉静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系。态查找树和折半查找的关系。n熟练掌握二叉排序树的构造和查找方法。熟练掌握二叉排序树的构造和查找方法。n理解二叉平衡树的维护平衡方法。理解二叉平衡树的维护平衡方法。n理解理解B-树，树，B+树的特点以及它们的建树过程。树的特点以及它们的建树过程。n熟练掌握哈希表的构造方法，深刻理解哈希表与熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。其它结构的表的实质性的差别。n掌握计算各种查找方法在等概率情况下查找成功掌握计算各种查找方法在等概率情况下查找成功时的平均查找长度。时的平均查找长度。