《数据结构-第三部分.ppt》由会员分享，可在线阅读，更多相关《数据结构-第三部分.ppt（440页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三部分第三部分集合集合集合中的元素互相之间没有关系集合中的元素互相之间没有关系集合的存储：借用其他容器集合的存储：借用其他容器集合的操作：查找和排序集合的操作：查找和排序这一部分将介绍这一部分将介绍查找表查找表排序算法排序算法散列表散列表不相交集不相交集1第第7章章集合与静态查找表集合与静态查找表集合的基本概念集合的基本概念查找的基本概念查找的基本概念无序表的查找无序表的查找有序表的查找有序表的查找STLSTL中的静态表中的静态表2集合的基本概念集合的基本概念集合中的数据元素除了属于同一集合之外，集合中的数据元素除了属于同一集合之外，没有任何逻辑关系。没有任何逻辑关系。在集合中，每个数据元素
2、有一个区别于其他在集合中，每个数据元素有一个区别于其他元素的唯一标识，通常称为键值或关键字值元素的唯一标识，通常称为键值或关键字值集合的主要运算：集合的主要运算：查找某一元素是否存在查找某一元素是否存在将集合中的元素按照它的唯一标识排序将集合中的元素按照它的唯一标识排序3集合的存储集合的存储任何容器都能存储集合任何容器都能存储集合常用的表示形式是借鉴于线性表或树常用的表示形式是借鉴于线性表或树唯一一个仅适合于存储和处理集合的数唯一一个仅适合于存储和处理集合的数据结构是散列表据结构是散列表 4第第7章章集合与静态查找表集合与静态查找表集合的基本概念集合的基本概念查找的基本概念查找的基本概念无序表
3、的查找无序表的查找有序表的查找有序表的查找STLSTL中的静态表中的静态表5查找的基本概念查找的基本概念用于查找的集合称之为查找表用于查找的集合称之为查找表 查找表的分类：查找表的分类：静态查找表静态查找表 动态查找表动态查找表 内部查找内部查找外部查找外部查找6静态查找表的存储静态查找表的存储静态查找表可以用顺序表存储。静态查找表可以用顺序表存储。如如C+C+的标准模板库中的类模板的标准模板库中的类模板vectorvector，或第，或第二章中定义的二章中定义的seqListseqList，或直接存储在，或直接存储在C+C+的原始数组中。的原始数组中。查找函数应该是一个函数模板。模板参查找函
4、数应该是一个函数模板。模板参数是数据元素的类型。数是数据元素的类型。7第第7章章集合与静态查找表集合与静态查找表集合的基本概念集合的基本概念查找的基本概念查找的基本概念无序表的查找无序表的查找有序表的查找有序表的查找STLSTL中的静态表中的静态表8无序表的查找无序表的查找无序表：数组中的元素是无序的无序表：数组中的元素是无序的无序表的查找：毫无选择只能做线性的无序表的查找：毫无选择只能做线性的顺序查找顺序查找 templateintseqSearch(vector&data,constType&x)data0=x;for(inti=data.size()-1;x!=datai;-i);ret
5、urni;9第第7章章集合与静态查找表集合与静态查找表集合的基本概念集合的基本概念查找的基本概念查找的基本概念无序表的查找无序表的查找有序表的查找有序表的查找STLSTL中的静态表中的静态表10有序表的查找有序表的查找顺序查找顺序查找二分查找二分查找插值查找插值查找分块查找分块查找11顺序查找顺序查找与无序表的顺序查找类似，只是当被查与无序表的顺序查找类似，只是当被查元素在表中不存在时，不需要查到表尾元素在表中不存在时，不需要查到表尾templateintseqSearch(vector&data,constType&x)data0=x;for(inti=data.size()-1;xdata
6、i;-i);if(i=0|x!=datai)return0;elsereturni;12有序表的查找有序表的查找顺序查找顺序查找二分查找二分查找插值查找插值查找分块查找分块查找13二分查找二分查找每次检查待查数据中排在最中间的那个每次检查待查数据中排在最中间的那个元素元素如中间元素等于要查找的元素，则查找如中间元素等于要查找的元素，则查找完成完成否则，确定要找的数据是在前一半还是否则，确定要找的数据是在前一半还是在后一半，然后缩小范围，在前一半或在后一半，然后缩小范围，在前一半或后一半内继续查找。后一半内继续查找。14查找查找x=8012mid=4 但但 key=9 10,向左向左key 4
7、8 9 10 11 13 1934567high=7low=1012mid=2 找到找到key 4 8 9 10 11 13 1934567high=7low=115templateintbinarySearch(constvector&data,constType&x)intlow=1,high=data.size()-1,mid;while(low=high)/查找区间存在查找区间存在mid=(low+high)/2;/计算中间位置计算中间位置if(x=datamid)returnmid;if(xdatamid)high=mid-1;elselow=mid+1;return0;16有序表的
8、查找有序表的查找顺序查找顺序查找二分查找二分查找插值查找插值查找分块查找分块查找17插值查找插值查找适用于数据的分布比较均匀的情况适用于数据的分布比较均匀的情况查找位置的估计查找位置的估计 缺点：计算量大缺点：计算量大18插值查找适用情况插值查找适用情况访问一个数据元素必须比一个典型的指令访问一个数据元素必须比一个典型的指令费时得多。例如，数组可能在磁盘里而不费时得多。例如，数组可能在磁盘里而不是在内存里，而且每次比较都需要访问一是在内存里，而且每次比较都需要访问一次磁盘。次磁盘。这些数据必须不仅有序，而且分布相当均这些数据必须不仅有序，而且分布相当均匀，这可以使每次估计都相当准确，可以匀，这
9、可以使每次估计都相当准确，可以将大量的数据排除出查找范围。这样，花将大量的数据排除出查找范围。这样，花费这些计算代价是值得的费这些计算代价是值得的 19有序表的查找有序表的查找顺序查找顺序查找二分查找二分查找插值查找插值查找分块查找分块查找20分块查找分块查找分块查找也称为索引顺序块的查找。分块查找也称为索引顺序块的查找。是处理大量数据查找的一种方法。是处理大量数据查找的一种方法。它把整个有序表分成若干块，块内的数它把整个有序表分成若干块，块内的数据元素可以是有序存储，也可以是无序据元素可以是有序存储，也可以是无序的，但块之间必须是有序的。的，但块之间必须是有序的。21块内最大关键字块内最大关
10、键字171744446060块起始地址块起始地址0 06 61414369101417192334373940424446485158600123456789101112131415161718查找由两个阶段组成：查找索引和查找块查找由两个阶段组成：查找索引和查找块22第第7章章集合与静态查找表集合与静态查找表集合的基本概念集合的基本概念查找的基本概念查找的基本概念无序表的查找无序表的查找有序表的查找有序表的查找STLSTL中的静态表中的静态表23STLSTL中的静态表中的静态表对应于顺序查找和二分查找，对应于顺序查找和二分查找，C+C+的标准模板库中提供的标准模板库中提供两个模板函数：两个模
11、板函数：findfind和和binary_searchbinary_search。这两个函数模。这两个函数模板都位于标准库板都位于标准库algorithmalgorithm中中 findfind函数顺序查找一个序列函数顺序查找一个序列findfind有两个模板参数。第一个模板参数是对应于存储集合数有两个模板参数。第一个模板参数是对应于存储集合数据的容器的迭代器。第二个模板参数是集合元素的类型。据的容器的迭代器。第二个模板参数是集合元素的类型。函数有三个形式参数。第一、二个形式参数是两个迭代器对函数有三个形式参数。第一、二个形式参数是两个迭代器对象，指出查找的范围。第三个参数是需要查找的对象值。
12、象，指出查找的范围。第三个参数是需要查找的对象值。findfind函数的返回值是一个迭代器对象，指出了被查找的元素函数的返回值是一个迭代器对象，指出了被查找的元素在容器中的位置。在容器中的位置。24binary_searchbinary_searchbinary_search函数用二分查找的方式查找一个有函数用二分查找的方式查找一个有序序列。序序列。它也有两个模板参数。第一个模板参数是对应于存它也有两个模板参数。第一个模板参数是对应于存储集合数据的容器的迭代器。第二个模板参数是集储集合数据的容器的迭代器。第二个模板参数是集合元素的类型。合元素的类型。函数也有三个形式参数。第一、二个形式参数是两
13、函数也有三个形式参数。第一、二个形式参数是两个迭代器对象，指出查找的范围。第三个参数是需个迭代器对象，指出查找的范围。第三个参数是需要查找的对象值。要查找的对象值。函数的返回值是函数的返回值是boolbool类型的，指出了被查找的元素类型的，指出了被查找的元素在容器中是否存在。如果存在，返回在容器中是否存在。如果存在，返回truetrue，否则，否则，返回返回falsefalse。25应用实例应用实例#include#include#includeusingnamespacestd;intmain()inta=2,4,7,8,10,12,13,15,16,19,20;vectorv;vecto
14、r:iteratoritr;for(inti=0;i11;+i)v.push_back(ai);if(binary_search(v.begin(),v.end(),13)cout13存在存在n;elsecout13不存在不存在n;itr=find(v.begin(),v.end(),13);cout*itrendl;return0;26总结总结本章介绍了集合关系的基本概念，以及本章介绍了集合关系的基本概念，以及集合类型的数据结构中的基本操作。集合类型的数据结构中的基本操作。针对静态的集合，介绍了查找操作的实针对静态的集合，介绍了查找操作的实现。包括顺序查找、二分查找、插值查现。包括顺序查找、
15、二分查找、插值查找和分块查找。找和分块查找。最后还介绍了最后还介绍了STLSTL中的查找函数：中的查找函数：findfind和和binary_searchbinary_search。findfind实现了顺序查找，实现了顺序查找，binary_searchbinary_search实现了二分查找。实现了二分查找。27第第8章章动态查找表动态查找表二叉查找树二叉查找树AVLAVL树树红黑树红黑树AAAA树树伸展树伸展树B B树和树和B+B+树树STLSTL中的动态查找表中的动态查找表既要支持快速查找，又要支持插入删除，通常选用树既要支持快速查找，又要支持插入删除，通常选用树作为存储的载体作为存储
16、的载体28二叉查找树二叉查找树二叉查找树的定义二叉查找树的定义二叉查找树的操作二叉查找树的操作二叉查找树的性能二叉查找树的性能二叉查找树类的实现二叉查找树类的实现 29二叉查找树二叉查找树如果如果p p的左子树若非空，则左子树上的所有结的左子树若非空，则左子树上的所有结点的关键字值均小于点的关键字值均小于p p结点的关键字值。结点的关键字值。如果如果p p的右子树若非空，则右子树上的所有结的右子树若非空，则右子树上的所有结点的关键字值均大于点的关键字值均大于p p结点的关键字值。结点的关键字值。结点结点p p的左右子树同样是二叉查找树。的左右子树同样是二叉查找树。二叉查找树是二叉树在查找方面的
17、重要应用。二叉二叉查找树是二叉树在查找方面的重要应用。二叉查找树或者为空，或者具有如下性质：对任意一个查找树或者为空，或者具有如下性质：对任意一个结点结点p p而言而言30e e、g g：二叉查找树：二叉查找树 LNPEMCY1222503001102009910523021631二叉查找树二叉查找树二叉查找树的定义二叉查找树的定义二叉查找树的操作二叉查找树的操作二叉查找树的性能二叉查找树的性能二叉查找树类的实现二叉查找树类的实现 32二叉查找树的操作二叉查找树的操作特定节点在树上是否存在特定节点在树上是否存在插入一个节点插入一个节点删除一个节点删除一个节点由于树是递归定义的，因此这些操作往往
18、也用递由于树是递归定义的，因此这些操作往往也用递归实现。因为二叉树的平均高度为归实现。因为二叉树的平均高度为logNlogN，这些操，这些操作的时间复杂度也是作的时间复杂度也是O(logNO(logN)33查找过程查找过程若根结点的关键字值等于查找的关键字，若根结点的关键字值等于查找的关键字，成功。成功。否则，若关键字值小于根结点，查其左子否则，若关键字值小于根结点，查其左子树。若关键字值大于根结点，查其右子树。树。若关键字值大于根结点，查其右子树。在左右子树上的操作类似。在左右子树上的操作类似。3412225030011020099105230216如：查找如：查找122，查找查找110，查
19、找查找230，查找查找22535查找过程的递归描述查找过程的递归描述如果树为空，返回如果树为空，返回falsefalse如果根节点等于被查结点，返回如果根节点等于被查结点，返回truetrue如果被查节点小于根节点，递归查找左如果被查节点小于根节点，递归查找左子树，否则递归查找右子树子树，否则递归查找右子树36插入操作插入操作若二叉树为空。则新插入的结点成为根结点。若二叉树为空。则新插入的结点成为根结点。如二叉树非空如二叉树非空首先执行查找算法，找出被插结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被判断被插结点是其父亲结点的左、右儿子。将被
20、插结点作为叶子结点插入。插结点作为叶子结点插入。注意：新插入的结点总是叶子结点注意：新插入的结点总是叶子结点37将数的序列：将数的序列：122、99、250、110、300、280 作为二叉作为二叉查查找找树的结点的关键字值，生成二叉树的结点的关键字值，生成二叉查找查找树。树。1222503001102809938插入操作的递归实现插入操作的递归实现如果当前树为空，插入值作为树的根节如果当前树为空，插入值作为树的根节点，返回点，返回如果插入值小于根节点，插入到左子树，如果插入值小于根节点，插入到左子树，否则插入到右子树。否则插入到右子树。39 执行实例：插入值为执行实例：插入值为 280 的结
21、点的结点 12225030011099Tf：null12225030011099fTKey=28012225030011099fTKey=280f12225030011099T:nullKey=280f1222503001109928040删除操作删除操作删除叶结点删除叶结点删除有一个儿子的结点删除有一个儿子的结点删除有两个儿子的结点删除有两个儿子的结点41删除叶结点删除叶结点 直接删除，更改它的父亲结点的相应指针字段为直接删除，更改它的父亲结点的相应指针字段为空。这不会改变二叉查找树的特性。如：删除数空。这不会改变二叉查找树的特性。如：删除数据字段为据字段为 1515、70 70 的结点。的
22、结点。1560703020506030205042删除操作删除操作删除叶结点删除叶结点删除有一个儿子的结点删除有一个儿子的结点删除有两个儿子的结点删除有两个儿子的结点43只有一个儿子只有一个儿子12225030020011010523021640045050099被删结点被删结点4412225011020099105330316400450500300被删结点被删结点45若被删结点只有一个唯一的儿子，将此若被删结点只有一个唯一的儿子，将此儿子取代被删结点的位置。即，如被删儿子取代被删结点的位置。即，如被删结点是其父结点的左孩子，那么将他的结点是其父结点的左孩子，那么将他的儿子作为父结点的左孩子
23、；如被删结点儿子作为父结点的左孩子；如被删结点是其父结点的有孩子，那么将他的孩子是其父结点的有孩子，那么将他的孩子作为父结点的右孩子。作为父结点的右孩子。能保持二查查找树的有序性能保持二查查找树的有序性46删除操作删除操作删除叶结点删除叶结点删除有一个儿子的结点删除有一个儿子的结点删除有两个儿子的结点删除有两个儿子的结点47被删结点有两个儿子被删结点有两个儿子通常的做法：选取通常的做法：选取“替身替身”取代被删结点。取代被删结点。有资格充当该替身的是谁哪？有资格充当该替身的是谁哪？替身的要求：维持二叉查找树的特性不变。因替身的要求：维持二叉查找树的特性不变。因此，只有在中序周游中紧靠着被删结点
24、的结点此，只有在中序周游中紧靠着被删结点的结点才有资格作为才有资格作为“替身替身”，即，即，左子树中最大左子树中最大的结点的结点 或或 右子树中最小的结点。右子树中最小的结点。删除这个结点会使其他结点从树上脱离。删除这个结点会使其他结点从树上脱离。4825030020099105330316400450500被删结点被删结点替身替身做法：将替身做法：将替身110的数据字段复制到被删结点的数据字段。的数据字段复制到被删结点的数据字段。将结点将结点 110 的左儿子作为的左儿子作为 99 的右儿子。的右儿子。用左子树中的最大值做替身用左子树中的最大值做替身12211049 250300110991
25、05330316400450500被删结点被删结点替身替身做法：将替身的数据字段复制到被删结点的数据字段。做法：将替身的数据字段复制到被删结点的数据字段。用右子树的最小值做替身用右子树的最小值做替身12220050 12225030011020099105230216400450500被删结点被删结点替身替身替身替身结论：结论：先将替身的数据字段复制先将替身的数据字段复制到被删结点到被删结点将原替身的另一儿子作为将原替身的另一儿子作为它的父亲结点的儿子，究它的父亲结点的儿子，究竟是作为左儿子还是右儿竟是作为左儿子还是右儿子依原替身结点和其父亲子依原替身结点和其父亲结点的关系而定结点的关系而定释
26、放原替身结点的空间。释放原替身结点的空间。51删除总结删除总结FP被删结点被删结点PRPLFPRPL、PR皆皆 空，空，直接删除直接删除。PL或或PR为空为空 PL为空，删除后的为空，删除后的情况。情况。52FP被删结点被删结点CCLPRQQLSSLFSCCLPRQQLSL用左子树的最大值代替用左子树的最大值代替53删除的递归实现删除的递归实现如果是空树，返回如果是空树，返回如果被删节点小于根节点，递归在左子树上删除如果被删节点小于根节点，递归在左子树上删除如果被删节点大于根节点，递归在右子树删除如果被删节点大于根节点，递归在右子树删除如果被删节点等于根节点如果被删节点等于根节点如果根节点有两
27、个儿子，将右子树的最小值放入根节点，如果根节点有两个儿子，将右子树的最小值放入根节点，在右子树上删除最小节点在右子树上删除最小节点如果只有左子树，左子树取代根节点，删除原来的根节点如果只有左子树，左子树取代根节点，删除原来的根节点如果只有右子树，右子树取代根节点，删除原来的根节点如果只有右子树，右子树取代根节点，删除原来的根节点54二叉查找树二叉查找树二叉查找树的定义二叉查找树的定义二叉查找树的操作二叉查找树的操作二叉查找树的性能二叉查找树的性能二叉查找树类的实现二叉查找树类的实现 55二叉查找树性能二叉查找树性能二叉查找树的操作（包括二叉查找树的操作（包括insertinsert、findf
28、ind和和deletedelete等）的代价正比于操作过程中要访问等）的代价正比于操作过程中要访问的结点数。如果所操作的二叉查找树是完全的结点数。如果所操作的二叉查找树是完全平衡的，那么访问的代价将是对数级别的平衡的，那么访问的代价将是对数级别的 在最坏的请况下，二叉查找树会退化为一个在最坏的请况下，二叉查找树会退化为一个单链表。时间复杂度是单链表。时间复杂度是O(N)O(N)。56平均性能平均性能n n 个结点二叉查找树的可能有个结点二叉查找树的可能有n n种形态，如果这种形态，如果这些形态出现的概率是相等的。设些形态出现的概率是相等的。设P P（n n）为查找）为查找n n个结点的二叉查找
29、树的平均查找时间，则个结点的二叉查找树的平均查找时间，则57二叉查找树二叉查找树二叉查找树的定义二叉查找树的定义二叉查找树的操作二叉查找树的操作二叉查找树的性能二叉查找树的性能二叉查找树类的实现二叉查找树类的实现 58二叉排序树类的设计二叉排序树类的设计采用标准的二叉链表存储一棵二叉查找树需采用标准的二叉链表存储一棵二叉查找树需要一个指向根节点的数据成员要一个指向根节点的数据成员公有的成员函数：公有的成员函数：findfind、insertinsert和和remove remove 以及构造、析构函数以及构造、析构函数二叉查找树的插入、删除和查找都是通过递二叉查找树的插入、删除和查找都是通过递
30、归实现的，而这三个公有函数的参数表中并归实现的，而这三个公有函数的参数表中并不需要包含递归参数。为此，对于每个公有不需要包含递归参数。为此，对于每个公有的成员函数都定义了一个对应的带有递归参的成员函数都定义了一个对应的带有递归参数的私有的成员函数数的私有的成员函数 59二叉排序树类的定义二叉排序树类的定义templateclassBinarySearchTreeprivate:structBinaryNodeTypedata;BinaryNode*left;BinaryNode*right;BinaryNode(constType&thedata,BinaryNode*lt,BinaryNod
31、e*rt):data(thedata),left(lt),right(rt);BinaryNode*root;60public:BinarySearchTree(BinaryNode*t=NULL)root=t;BinarySearchTree();boolfind(constType&x)const;voidinsert(constType&x);voidremove(constType&x);private:voidinsert(constType&x,BinaryNode*&t)const;voidremove(constType&x,BinaryNode*&t)const;boolfi
32、nd(constType&x,BinaryNode*t)const;voidmakeEmpty(BinaryNode*&t);61二叉排序树类的设计特点二叉排序树类的设计特点一个内嵌的一个内嵌的BinaryNodeBinaryNode类类数据成员只有一个，树根数据成员只有一个，树根公有的成员函数通过调用私有的递归函公有的成员函数通过调用私有的递归函数完成相应的功能数完成相应的功能62find函数的实现函数的实现templateboolBinarySearchTree:find(constType&x)constreturnfind(x,root);templateboolBinarySearc
33、hTree:find(constType&x,BinaryNode*t)constif(t=NULL)returnfalse;elseif(xdata)returnfind(x,t-left);elseif(t-dataright);elsereturntrue;63insert函数的实现函数的实现templatevoidBinarySearchTree:insert(constType&x)insert(x,root);templatevoidBinarySearchTree:insert(constType&x,BinaryNode*&t)if(t=NULL)t=newBinaryNode
34、(x,NULL,NULL);elseif(xdata)insert(x,t-left);elseif(t-dataright);64insert函数设计说明函数设计说明私有的私有的insertinsert函数的第二个形式参数，它函数的第二个形式参数，它是一个指向结点的指针的非常量引用。是一个指向结点的指针的非常量引用。这个引用符号不能省略。正是这个引用，这个引用符号不能省略。正是这个引用，使得新插入的结点和它的父结点之间关联使得新插入的结点和它的父结点之间关联了起来。了起来。65remove函数的实现函数的实现templatevoidBinarySearchTree:remove(constT
35、ype&x)remove(x,root);66templatevoidBinarySearchTree:remove(constType&x,BinaryNode*&t)if(t=NULL)return;if(xdata)remove(x,t-left);elseif(t-dataright);elseif(t-left!=NULL&t-right!=NULL)BinaryNode*tmp=t-right;while(tmp-left!=NULL)tmp=tmp-left;t-data=tmp-data;remove(t-data,t-right);elseBinaryNode*oldNode
36、=t;t=(t-left!=NULL)?t-left:t-right;deleteoldNode;67remove函数设计说明函数设计说明同样请注意私有的同样请注意私有的removeremove函数的参数，函数的参数，它的第二个参数也是指向结点的指针的它的第二个参数也是指向结点的指针的引用。引用。与插入过程一样，这个引用也不能去掉。与插入过程一样，这个引用也不能去掉。正是这个引用使得被删结点的父结点和正是这个引用使得被删结点的父结点和被删结点的儿子连接起来。被删结点的儿子连接起来。68二叉查找树类的使用二叉查找树类的使用intmain()inta=10,8,6,21,87,56,4,0,11,
37、3,22,7,5,34,1,2,9;BinarySearchTreetree;for(inti=0;i17;+i)tree.insert(ai);coutendlfind2is(tree.find(2)?true:false)endl;tree.remove(2);coutafterdelete2,find2is(tree.find(2)?true:false)endl;coutfind3is(tree.find(3)?true:false)endl;tree.remove(3);coutafterdelete3,find3is(tree.find(3)?true:false)endl;cou
38、tfind21is(tree.find(21)?true:false)endl;tree.remove(21);coutafterdelete21,find21is(tree.find(21)?true:false)endl;return0;691021879118760431256223470第第8章章动态查找表动态查找表二叉查找树二叉查找树AVLAVL树树红黑树红黑树AAAA树树伸展树伸展树B B树和树和B+B+树树STLSTL中的动态查找表中的动态查找表71AVLAVL树树AVLAVL树的定义树的定义AVLAVL树的插入操作树的插入操作AVLAVL树的删除树的删除AVLAVL树类的实现树
39、类的实现 72平衡二叉查找树平衡二叉查找树当树退化为链表时，树的优点荡然无存。要使查找树的性能尽当树退化为链表时，树的优点荡然无存。要使查找树的性能尽可能好，就要使得树尽可能丰满。要构造一个丰满树很困难，可能好，就要使得树尽可能丰满。要构造一个丰满树很困难，一种替代的方案是平衡树。一种替代的方案是平衡树。DGEDABCFEGBACF73二叉平衡树二叉平衡树二叉平衡树就是满足某种平衡条件的二二叉平衡树就是满足某种平衡条件的二叉查找树叉查找树平衡条件：平衡条件：容易维护容易维护保证树的高度是保证树的高度是O(logNO(logN)74平衡条件平衡条件最简单的想法是让左右子树有同样的高度。最简单的想
40、法是让左右子树有同样的高度。但它并不能保证树是矮胖的。但它并不能保证树是矮胖的。另一个想法是要求每个节点的左右子树都有另一个想法是要求每个节点的左右子树都有同样的高度。这个条件能保证树是矮胖的，同样的高度。这个条件能保证树是矮胖的，但这个条件太苛刻，只有满二叉树才满足这但这个条件太苛刻，只有满二叉树才满足这个条件。个条件。将上述条件稍微放宽一些就是二叉平衡查找将上述条件稍微放宽一些就是二叉平衡查找树。树。75平衡树的定义平衡树的定义平衡因子（平衡度）：结点的平衡度是结点平衡因子（平衡度）：结点的平衡度是结点的左子树的高度右子树的高度。的左子树的高度右子树的高度。空树的高度定义为空树的高度定义为
41、-1-1。平衡二叉树：每个结点的平衡因子都为平衡二叉树：每个结点的平衡因子都为 1 1、1 1、0 0 的二叉树。或者说每个结点的左右的二叉树。或者说每个结点的左右子树的高度最多差子树的高度最多差1 1的二叉树。的二叉树。可以证明平衡树的高度至多约为：可以证明平衡树的高度至多约为：1.44log(N+2)-1.3281.44log(N+2)-1.32876是平衡树不是丰满树是平衡树不是丰满树不是平衡树不是平衡树141253928635360501718730+1+1-1-1-100000000145392863536050171830+1+2-1-100000+1-177平衡二叉树的查找性能平
42、衡二叉树的查找性能定理：具有定理：具有 N N 个结点的平衡树，高度个结点的平衡树，高度 h h 满足：满足：loglog2 2(N+1)=h=1.44log(N+1)=h=1.44log2 2(N+1)-0.328;(N+1)-0.328;与二叉树的高度成正比与二叉树的高度成正比因此，平衡二叉树的操作都是因此，平衡二叉树的操作都是O(logNO(logN)78AVLAVL树树AVLAVL树的定义树的定义AVLAVL树的插入操作树的插入操作AVLAVL树的删除树的删除AVLAVL树类的实现树类的实现 79插入操作插入操作插入过程与二叉查找树的插入相同，只是插入过程与二叉查找树的插入相同，只是插
43、入后可能出现两种情况：插入后可能出现两种情况：插入后，不破坏平衡性，只是改变了树根到插插入后，不破坏平衡性，只是改变了树根到插入点的路径上的某些结点的平衡度，因此需要入点的路径上的某些结点的平衡度，因此需要自底向上修改节点的平衡度自底向上修改节点的平衡度破坏了路径上的某些结点的平衡性，需要向上破坏了路径上的某些结点的平衡性，需要向上调整树的结构调整树的结构80141253928635360501718730+1+1-1-1-100000000只改变了某些结点的平衡度，需要自底向上的调整。只改变了某些结点的平衡度，需要自底向上的调整。只要有一个节点的平衡度不变，它上面的节点的平衡只要有一个节点的
44、平衡度不变，它上面的节点的平衡度也不变。调整可以结束。度也不变。调整可以结束。插入插入29029+1081141253928635360501718730+1+1-1-1-100000000平衡树平衡树141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为 0危机结点危机结点插入插入2以后，变得不平衡了。如何用最简单、最有效的办法以后，变得不平衡了。如何用最简单、最有效的办法保持平衡分类二叉树的性质不变？保持平衡分类二叉树的性质不变？82调整要求：调整要求：希望不涉及到危机结希望不涉及到危机结点的父亲结点，即以危点的父亲结点，即以
45、危机结点为根的子树的高机结点为根的子树的高度应保持不变。调整可度应保持不变。调整可以到此结束。以到此结束。仍应保持分类二叉树仍应保持分类二叉树的性质不变的性质不变141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡原平衡度为度为 0危机结点危机结点83重新平衡重新平衡如果节点原来的平衡度为如果节点原来的平衡度为0 0，则插入后不可能，则插入后不可能失衡，重新计算平衡度，继续往上回溯失衡，重新计算平衡度，继续往上回溯如果节点原来的平衡度非如果节点原来的平衡度非0 0，可能成为失衡节，可能成为失衡节点点重新计算平衡度重新计算平衡度如果平衡度在合法
46、范围，调整结束如果平衡度在合法范围，调整结束如果失去平衡，重新调整树的结构，调整结束如果失去平衡，重新调整树的结构，调整结束从插入位置向根回溯从插入位置向根回溯84引起节点不平衡的情况引起节点不平衡的情况原结点的左子树高，在结点的左孩子的左子树上插入（原结点的左子树高，在结点的左孩子的左子树上插入（LL）原结点的左子树高，在结点左孩子的右子树上插入（原结点的左子树高，在结点左孩子的右子树上插入（LR）原结点的右子树高，在结点的右孩子的左子树上插入（原结点的右子树高，在结点的右孩子的左子树上插入（RL）原结点的左子树高，在结点的右孩子的右子树上插入（原结点的左子树高，在结点的右孩子的右子树上插入
47、（RR）85引起不平衡的情况引起不平衡的情况LLRR：LL的镜像对称的镜像对称LRRL：LR的镜像对称的镜像对称AB+1h-10+2+1hh-1h-1BLBRAR危危机机结点结点AB+1h-10+2-1h-1 BL AR BRh危危机机结点结点86LL和和RR问题问题通过单旋转来解决。即危机结点和引起危机的通过单旋转来解决。即危机结点和引起危机的儿子的角色转换。儿子的角色转换。如果是如果是LLLL问题，将危机结点的左儿子作为根，问题，将危机结点的左儿子作为根，原来的根结点作为他的右子树，原先的右儿子原来的根结点作为他的右子树，原先的右儿子作为原先根的左儿子。作为原先根的左儿子。如果是如果是RR
48、RR问题，将危机结点的右儿子作为根，问题，将危机结点的右儿子作为根，原来的根结点作为他的左子树，原先的左儿子原来的根结点作为他的左子树，原先的左儿子作为原先根的右儿子作为原先根的右儿子87LL问题问题保持了树的有序性保持了树的有序性保持了原先的高度保持了原先的高度AB+1h-10+2+1hh-1h-1BLBRAR危危机机结点结点ABh-1hh-1h-1BLBRAR88在下列树中插入在下列树中插入4，将会使得，将会使得9失去平衡。这是在失去平衡。这是在9的左孩子的左子树上插入引起失衡，是的左孩子的左子树上插入引起失衡，是LL情况情况141253928635360501718730+1+1-1-1
49、-100000000141253928635360501718730+1+1-1-1-100000000489旋转后的结果旋转后的结果141253928635360501718730+1-1-1-100004保持了树的有序性保持了树的有序性保持了原先的高度保持了原先的高度90LR和和RL问题问题通过双旋转来解决，即两次单旋转。先通过双旋转来解决，即两次单旋转。先对危机结点的儿子和孙子进行一次单旋对危机结点的儿子和孙子进行一次单旋转，使孙子变成儿子。然后是危机结点转，使孙子变成儿子。然后是危机结点和新的儿子进行一次单旋转。和新的儿子进行一次单旋转。91LR问题问题AB+1h-10+2-1h-1
50、BL AR BRh危危机机结点结点有一个结点被插入到有一个结点被插入到B的右子树的事实保证了的右子树的事实保证了B的右子的右子树不会是空的，因此我们可以假定树不会是空的，因此我们可以假定B的右子树为的右子树为C，它，它有一个根和两棵子树（当然可能是空的）组成有一个根和两棵子树（当然可能是空的）组成AB+1h-10+2-1h-1 BL AR CL危危 机机结点结点C CR92保持了树的有序性保持了树的有序性保持了原先的高度保持了原先的高度ABh-1h-1 BL AR CLC CRLR旋转可以看成有两个单选转组成：先对旋转可以看成有两个单选转组成：先对B执执行行RR旋转，再对旋转，再对A执行执行L