《树的相关知识.pptx》由会员分享，可在线阅读，更多相关《树的相关知识.pptx（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、树树树的定义：树的定义：树是具有以下性质的有限结点集合：树是具有以下性质的有限结点集合：(1)有一个被称为有一个被称为“根根”的结点。的结点。(2)根的所有孩子都是一颗子树的根。根的所有孩子都是一颗子树的根。第1页/共83页树的相关术语树的相关术语结点的度（结点的度（degree）：该结点拥有的）：该结点拥有的子数数目。右图中：子数数目。右图中：degree(A)=3,degree(F)=0叶子（叶子（leaf）：度为）：度为0的结点的结点双亲（双亲（parent）：拥有子树的结点）：拥有子树的结点孩子（孩子（child）：某个双亲结点的子树）：某个双亲结点的子树的根的根兄弟（兄弟（sibli
2、ng）：拥有同一个双亲结）：拥有同一个双亲结点的孩子点的孩子祖先（祖先（ancestor）：从某一个结点往）：从某一个结点往上一直到根经过的所有结点上一直到根经过的所有结点后代（后代（descendants）：子树的所有）：子树的所有结点结点层次（层次（level）：双亲的层次）：双亲的层次+1;根根的层次的层次=1.高度（高度（height）/深度（深度（depth）：）：maxlevels.ACBDGFEHIJMLK3421Level第2页/共83页树的表示（列表表示法）树的表示（列表表示法）ACBDGFEHIJMLK3421Level(A)(A(B,C,D)(A(B(E,F),C(G),
3、D(H,I,J)(A(B(E(K,L),F),C(G),D(H(M),I,J)树的结点的大小将会随着其子树的数目不同而变化，这对我们来说显然不是一个很好的方法。第3页/共83页树的表示（孩子兄弟表示法）树的表示（孩子兄弟表示法）ACBDGFEHIJMLKNACBNDENKN NFN NGHNIN NJN NLN NMleft childright siblingdata第5页/共83页二叉树二叉树二叉树是度不超过2的树二叉树的特性：第i层的最大结点数为2i1，高度为k的二叉树的最大结点数为2k1斜二叉树ABCDABCD左斜右斜完全二叉树ACGBDHEFI第6页/共83页二叉树的表示（数组表示法
4、）二叉树的表示（数组表示法）ABCDEFGHIACGBDHEFI123456789对于用数组表示的完全二叉树，对于任意结点i，有：第7页/共83页二叉树的表示（孩子表示法）二叉树的表示（孩子表示法）常用的存储结构typebitree=nodenode=recorddata:datatype;lchild,rchild:bitree;end;第8页/共83页二叉树的遍历二叉树的遍历遍历(先序遍历,中序遍历,后序遍历)Procpreorder(bt:bitree);ifbtNilthenvisit(bt)preorder(bt.lchild);preorder(bt.rchild);endP第9页
5、/共83页二叉树的性质二叉树的性质在二叉树的第i层上最多有2i-1个结点深度为K的二叉树最多有2k-1个结点在二叉树中,叶子结点的总数总比为度数为2的结点多1有n个结点的完全二叉树的结点按层序编号,则对任意一结点i,有(1)如果i=1,则结点i是二查树的根，无双亲；如果i1，则双亲是i/2(2)如果2in，则结点i无左孩子，否则左孩子为2i(3)如果2i+1n，则结点i无右孩子，否则右孩子为2i+1第10页/共83页树与二叉树的转换树与二叉树的转换任意一棵树的孩子兄弟表示法都有唯一对应的一颗二叉树任意一棵树的孩子兄弟表示法都有唯一对应的一颗二叉树NACBNDENKNNFNNGHNINNJNNL
6、NNMNACBNDENKNNFNNGHNINNJNNLNNM45 left childright childdata左孩子右孩子根结点的右孩子总是为空第11页/共83页森林转化为二叉树森林转化为二叉树用用“孩子兄弟表示法孩子兄弟表示法”可以将任意一棵树转化为可以将任意一棵树转化为二叉树的形式二叉树的形式森林转化为二叉树森林转化为二叉树如果如果F=T1,T2,Tm是森林，则可按如下规则是森林，则可按如下规则转化为一棵二叉树。转化为一棵二叉树。1)若若F为空，即为空，即m=0,则则B为空树为空树2)若若F非空，即非空，即m0,则则B的根的根root即为森林中即为森林中第一棵树的根第一棵树的根roo
7、t(T1),B的左子树为从的左子树为从T1中子树中子树森林森林F1=T11,T12,T1i转换而成的二叉树；其转换而成的二叉树；其右子树右子树Rb是从森林是从森林F=T2,Tm中转换出来的中转换出来的二叉树二叉树第12页/共83页二叉排序树二叉排序树(BinarySortTree)二叉排序树又称为二叉查找(搜索)树(BST)它或者是一颗空树，或者是具有如下性质的二叉树：1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值3)它左右子树分别为二叉排序树。第13页/共83页BST的特点的特点（1）二叉排序树中任一结点二叉排
8、序树中任一结点x，其左，其左(右右)子树中任一结点子树中任一结点y(若若存在存在)的关键字必小的关键字必小(大大)于于x的关键字。的关键字。（2）二叉排序树中，各结点关键字是惟一的。实际应用中，二叉排序树中，各结点关键字是惟一的。实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中将二叉排序树定义中BST性质性质(1)里的里的小于小于改为改为大于等于大于等于，或将或将BST性质性质(2)里的里的大于大于改为改为小于等于小于等于，甚至可同时修改，甚至可同时修改这两个性质。这两个性质。（3）按中序遍历该树所得到的
9、中序序列是一个递增有序序列。按中序遍历该树所得到的中序序列是一个递增有序序列。第14页/共83页二叉排序树二叉排序树在二叉树中，边有两种：红边：表示是父亲的左儿子蓝边：表示是父亲的右儿子第15页/共83页实例实例第16页/共83页BST的查找的查找FUNCbstsrch(t:bitreptr;K:keytype):bitreeif(t=nil)or(t.key=K)thenreturn(t)elseift.keyKthenreturn(bstsrch(t.lchild,k)elsereturn(bstsrch(t.rchild,k)endF第17页/共83页BST的插入的插入在二叉排序树中插入
10、新结点，要保证插入后仍满足在二叉排序树中插入新结点，要保证插入后仍满足BST性性质。其插入过程是：质。其插入过程是：(a)若二叉排序树若二叉排序树T为空，则为待插入的关键字为空，则为待插入的关键字key申请一申请一个新结点，并令其为根；个新结点，并令其为根；(b)若二叉排序树若二叉排序树T不为空，则将不为空，则将key和根的关键字比较：和根的关键字比较：(i)二者相等，则说明树中已有此关键字二者相等，则说明树中已有此关键字key，无须插入。，无须插入。(ii)keyTkey，则将它插入根的右子树中。，则将它插入根的右子树中。子树中的插入过程与上述的树中插入过程相同。如此进行子树中的插入过程与上
11、述的树中插入过程相同。如此进行下去，直到将下去，直到将key作为一个新的叶结点的关键字插入到二作为一个新的叶结点的关键字插入到二叉排序树中，或者直到发现树中已有此关键字为止。叉排序树中，或者直到发现树中已有此关键字为止。第18页/共83页BST插入的递归算法插入的递归算法PROCins_bstree(varbst:bitree;k:keytp);采用链式存储结构beginnew(s);s.key:=k;s.lchild:=nil;s.rchild:=nil;ifbst=nilthenbst:=s;elseifKfkeythenf.lchild:=s;elsef.rchild:=send;第19
12、页/共83页BST的生成为进行不断插入的过程!但在生成BST的时候,可能会由于根结点选择不好,使得树很斜,查找的效率降低,可以使用随机产生根结点的方法,使得BST较平衡,下图就是两棵关键字相同的BST树.第20页/共83页删除删除分三种情况讨论1)删除叶子节点不破坏树的结构,修改其双亲结点:f.lchild:=NIL2)若只有左孩子Pl或者只有右孩子Pr,则只要令Pl或Pr直接为f的左孩子即可:f.lchild:=P.lchild;或者f.lchild:=P.rchild;3)左右孩子都有,设中序遍历的序列为ClC.QlQSlSPPrF,令P的左孩子为f的右孩子,而P的右孩子为S的右孩子q:=
13、p;s:=p.lchild;whilesrchildnildoq:=s;s:=s.rchildp.data:=s.data;ifqpthenq.rchild:=s.lchildelseq.lchild:=s.lchilddispose(s)第21页/共83页练习练习写一个程序，读入n个整数，构建二叉排序树，输出二叉排序树的中序遍历结果。n=100000第22页/共83页样例样例7-表示有7个数3265741第23页/共83页二叉查找树时间复杂度分析二叉查找树时间复杂度分析二叉查找树(BinarySearchTree)可以被用来表示有序集合、建立索引或优先队列等。最坏情况下，作用于二叉查找树上的
14、基本操作的时间复杂度，可能达到O(n)。某些二叉查找树的变形，基本操作在最坏情况下性能依然很好，如红黑树、AVL树等。第24页/共83页Splay树树Splay树是二叉查找树的改进。对Splay树的操作的均摊复杂度是O(log2n)。Splay树与二叉查找树一样，也具有有序性。即Splay树中的每一个节点x都满足：该节点左子树中的每一个元素都小于x，而其右子树中的每一个元素都大于x。Splay树的核心思想就是通过Splay操作进行自我调整，从而获得平摊较低的时间复杂度。第25页/共83页Splay操作lSplay操作是在保持Splay树有序性的前提下，通过一系列旋转操作将树中的元素x调整至树的
15、根部的操作(Zig:右旋,Zag:左旋)。l在旋转的过程中，要分三种情况分别处理：1)Zig 或 Zag 2)Zig-Zig 或 Zag-Zag 3)Zig-Zag 或 Zag-Zig 第26页/共83页Splay操作操作情况情况1Zig或Zag操作：节点x的父节点y是根节点。第27页/共83页Splay操作操作情况情况2Zig-Zig或Zag-Zag操作：节点x的父节点y不是根节点，且x与y同时是各自父节点的左孩子或者同时是各自父节点的右孩子。第28页/共83页Spaly操作操作情况情况3Zig-Zag或Zag-Zig操作：节点x的父节点y不是根节点，x与y中一个是其父节点的左孩子而另一个是
16、其父节点的右孩子。第29页/共83页Splay操作举例操作举例Splay(1,S)第30页/共83页Spaly树基本操作树基本操作查找：与二叉排序树查找类似，只是查找结束后要将找到的元素通过Splay操作旋转到根。插入：用查找过程找到要插入的位置，进行插入。然后将新元素旋转到根。删除：首先在树中找到要删除的元素，将他转到根节点并删去，这样原来的树就分裂成了两棵树，然后将左子树中拥有最大关键字的那一个元素转到根，由于它是左子树中的最大元素，所以他不存在有儿子，这样只要把原来的右子树作为他的右子树，就重新合并成了一棵树。可见在Splay树的基本操作中，处处要用到Splay旋转操作！第31页/共83
17、页应用：应用：Pet宠物收养场提供两种服务：收养被离弃的宠物与让新的主人领养宠物。每个宠物有不相同的特点值。领养人所希望的特点值也不相同。如果领养人/遗弃宠物过多，则当前来的宠物/领养人选择离其特点值最近的（如果有两个特点值与其同样接近，则选择较小的）领养人/宠物，被领养/领养。并且纪录两个特点值的差值。输入N条请求(X,Y)，X=0表示宠物;X=1表示领养人，Y为特征值。任务是计算所有差值的和。（N=80000，等待的宠物/领养者数M=10000）第32页/共83页字典树（字典树（trie）当关键字是串的时候，往往用trie。我们的动机是：利用串的公共前缀来节约内存，加快检索速度。例如，需要
18、保存“computer”和“command”，由于它们的前三个字母是相同的，所以希望它们共享前三个字母，而只有剩下部分才进行分开储存。第33页/共83页例如，需要保存以下8个单词：becausebeforebegbeggarbelongbelowdaydead第34页/共83页第35页/共83页Trie的特点的特点根节点不包含字母，除根节点外每一个节点都仅包含一个英文字母从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。每个节点的所有儿子包含的字母都不相同。插入和删除的时间均为O(L)L为字符串的长度第36页/共83页应用：最长前缀应用：最长前缀给定给定n个
19、字符串，即基元个字符串，即基元给定一个字符串给定一个字符串T，即生物体的结构，即生物体的结构要找出字符串要找出字符串T由基元构成的前缀，使得该前缀的长度最大由基元构成的前缀，使得该前缀的长度最大N=100,Len(T)=500000,基元长度基元长度L=20第37页/共83页样例样例基元：基元：A，AB，BBC，CA，BAT:ABABACABAABCB最长前缀构成有三种方法最长前缀构成有三种方法uA+BA+BA+CA+BA+ABuAB+AB+A+CA+BA+ABuAB+A+BA+CA+BA+AB长度为长度为11第38页/共83页分析分析为了尽快的查找到基元，我们把基元构成一个单词树，为了尽快的
20、查找到基元，我们把基元构成一个单词树，也叫也叫trie树。如下图为样例的单词树。树。如下图为样例的单词树。该树最多为该树最多为26叉树，任何单词要么是某个单词的前缀，叉树，任何单词要么是某个单词的前缀，要么为从根到叶子结点组成的单词。要么为从根到叶子结点组成的单词。这样我们只需要这样我们只需要O(L)的时间即可查找到某个单词，的时间即可查找到某个单词，L为为单词的长度。单词的长度。第39页/共83页动态规划动态规划我们设前我们设前j个字符已经匹配，考虑前个字符已经匹配，考虑前i个字符是否能匹配，主要看从个字符是否能匹配，主要看从i+1j组成的字符串是否是单词组成的字符串是否是单词因此设因此设f
21、(i)表示前表示前i个字符是否已匹配，若能匹配则为真个字符是否已匹配，若能匹配则为真(用用1表示表示),否则为假否则为假(用用0表示表示)。则有：。则有：第40页/共83页时间复杂度分析时间复杂度分析每次求每次求f(i)需要向前找需要向前找f(j)，i-jL,每移动一次每移动一次j需要判定需要判定word(j+1,i)是否是单是否是单词词1=i=len(T),1=i-jL查找单词时间复杂度为查找单词时间复杂度为O(L)因此总时间复杂度为因此总时间复杂度为O(len(T)*L2)。因为因为T=500000,L=20,因此因此,5*105*202=2*108第41页/共83页并查集引例并查集引例写
22、一个数据结构，支持一下两种操作：现有若干个队伍，1、询问两个人是否属于同一个队伍2、合并两个人所在的队伍第42页/共83页输入样例输入样例第一行nm表示有n个人（用1到n表示），在开始时没有两个人是属于同一个队伍。接下来m行，表示m次操作。每行操作有2种可能：1xy表示询问x和y是不是在同一个队伍2xy合并x和y所在的队伍（如果x和y已经在同一队伍，不做任何操作）第43页/共83页样例样例45113213113234141n=100000m=100000NOYESYES第44页/共83页分析分析每个队伍实际上是一个集合，两个操作相当于：1、询问两个元素是否在同一个集合2、合并两个集合尝试用树结
23、构表示一个集合A与B是父子关系表示A与B在同一个队伍第45页/共83页问题一问题一如何知道两个节点是否在同一颗树中？第46页/共83页问题二问题二怎样合并两颗树？第47页/共83页用双亲表示法存储树结构用双亲表示法存储树结构若两种操作都解决了，如何储存这颗树呢？n-表示一共n个节点father1,father2,fathern表示每个节点的父亲节点是谁。如果t为根，则fathert=0第48页/共83页如何寻找根节点？如何寻找根节点？functionfind(t:longint):longint;varf:longint;beginf:=t;whilefatherf0dof:=fatherf;
24、find:=f;end;intfind(intt)intf;f=t;while(fatherf!=0)f=fatherf;return(f);第49页/共83页启发式合并第50页/共83页如何合并？如何合并？procedureunionxy(x,y:longint);beginx:=find(x);y:=find(y);ifxythenfatherx:=y;end;voidunionxy(intx,inty)x=find(x);y=find(y);if(x!=y)fatherx=y;return;第51页/共83页效率分析效率分析不断询问红色节点所在的根节点路径压缩！第52页/共83页路径压缩
25、路径压缩f为根节点whilefathert0dobeginp:=fathert;fathert:=f;t:=p;end;f为根节点while(fathert!=0)p=fathert;fathert=f;t=p;第53页/共83页并查集的时间复杂度并查集的时间复杂度可以证明，经过启发式合并和路径压缩之后的并查集，执行m次查找的复杂度为O(m(m)其中(m)是Ackermann函数的某个反函数，你可以近似的认为它是小于5的。所以并查集的单次查找操作的时间复杂度也几乎是常数级的。第54页/共83页应用用1：friend有一个镇有N个居民。当然其中有许多人是朋友的关系。根据有名的谚语：“我朋友的朋友
26、也是我的朋友”，所以如果A和B是朋友，B和C是朋友，那么A和C也是朋友。你的任务是算出在这个镇中最大的朋友集团为多少人。【输入文件】【输入文件】输入文件的第一行有2个正整数N和M。N代表镇上居民的数目（1=N=30000），M代表这些居民中朋友关系的数目（0=M=30000）。接下来的M行每行有2个整数A，B（1=A,B=N,A不等于B），代表A，B为朋友关系。这M行中可能有的会重复出现。【输出文件】【输出文件】输出文件仅一行，在这个镇中最大的朋友集团为多少人。第55页/共83页应用应用2：银河英雄传说银河英雄传说银河系的两大军事集团在巴米利恩星域爆发战争。泰山压银河系的两大军事集团在巴米利恩
27、星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成分成30000列，每列依次编号为列，每列依次编号为1,2,30000。之后，。之后，他把自己的战舰也依次编号为他把自己的战舰也依次编号为1,2,30000，让第，让第i号号战舰处于
28、第战舰处于第i列列(i=1,2,30000)，形成，形成“一字长蛇阵一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为实施密集攻击。合并指令为Mij，含义为让第，含义为让第i号战舰所号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至在的整个战舰队列，作为一个整体（头在前尾在后）接至第第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成
29、的。合并指令的执行结果会同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。使队列增大。第56页/共83页然而，老谋深算的莱因哈特早已在战略上取得然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。络随时监听杨威利的舰队调动指令。在杨威利发布指令调动舰队的同时，莱因哈特在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：会发出一些询问指令：Cij。该指令意思是，。该指令意思是，询问电脑，杨威利的第询
30、问电脑，杨威利的第i号战舰与第号战舰与第j号战舰当号战舰当前是否在同一列中，如果在同一列中，那么它前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。们之间布置有多少战舰。作为一个资深的高级程序设计员，你被要求编作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特写程序分析杨威利的指令，以及回答莱因哈特的询问。的询问。第57页/共83页分析分析由于我们要得到的信息除了某条战舰在哪个队列，还要知道它在该队列中的位置。因此需要对并查集进行扩充。定义：ai：战舰i暂时标记为属于以战舰ai为首的队列，称战舰ai为战舰i的父节点bi：战舰i到战舰ai（包括战舰ai）
31、之间的战舰数量，称bi为战舰i到战舰ai的深度。ci：战舰i所属队列后方（包括战舰i本身）的战舰数量（注意：此变量只有当ai=i时才有意义），称ci为队列长度。第58页/共83页分析分析初始时：ai=i，bi=0，ci=1对于每个Mij命令，需要进行如下操作：对战舰i,j进行查找和路径压缩设ai=r1,aj=r2且r1r2，则：ar1=r2，br1=cr2，cr2=cr1+cr2对于每个Cij命令，需要进行如下操作：对战舰i,j进行查找和路径压缩判断是否有ai=aj，如是则表示他们是同一队列，输出|bi-bj|-1；如果不是则输出-1第59页/共83页引例引例写一种数据结构，完成以下写一种数据
32、结构，完成以下3种操作：种操作：(操作的总次数不超过操作的总次数不超过100000)1、插入一个数、插入一个数2、询问最小值、询问最小值3、删除最小值、删除最小值要求是这要求是这3种操作都要快。种操作都要快。第60页/共83页输入输出输入输出输入每行一次操作，有如下三种：1x：表示插入X这个数2：表示询问当前最小值3：表示删除最小值输出对于每个询问最小值操作，输出一行，每行仅一个数，表示当前的最小值。第61页/共83页输入：9-9次操作120213011023232输出：20102030样例样例第62页/共83页用线性表作为数据结构用线性表作为数据结构无序表：插入操作O（1）询问最小值O（n）
33、删除最小值O（n）有序表：插入操作O（n）询问最小值O（1）删除最小值O（1）第63页/共83页二叉堆二叉堆定义定义堆是一棵完全二叉树，对于每一个非叶子结点，它的权值都不堆是一棵完全二叉树，对于每一个非叶子结点，它的权值都不大于（或不小于）左右孩子的权值，我们称这样的堆为小根堆大于（或不小于）左右孩子的权值，我们称这样的堆为小根堆（或大根堆）。（或大根堆）。描述如下描述如下:n个元素的序列个元素的序列k1,k2,kn，当且仅当满足，当且仅当满足ki=k2i并且并且ki=k2i并且并且ki=k2i+1二叉堆肯定是一颗完全二叉树二叉堆肯定是一颗完全二叉树第64页/共83页在堆中插入元素在堆中插入元
34、素x首先将元素首先将元素x放到堆中的最后一个位置（即最放到堆中的最后一个位置（即最底层最右边的位置），然后不断地把底层最右边的位置），然后不断地把x往上调往上调整，直到整，直到x调不动为止（即大于它现在的父亲，调不动为止（即大于它现在的父亲，或者或者x处于根结点）。处于根结点）。定义一个堆:Var st:array1.maxn of longint;/存储堆 n:longint;/堆中元素个数第65页/共83页13545786213557864(1)将新节点插到最后(2)把新节点和父亲进行交换1557864(3)继续交换，直到重新满足堆的性质322第66页/共83页插入插入(实际上是不断向上调
35、整的过程实际上是不断向上调整的过程)PROCup(k:longint);把第k个结点上调beginwhilek1dobegini:=kdiv2;i是k的父亲ifstistkthenbeginswap(i,k);k:=i;交换结点i和kendelseexit;end;end;第67页/共83页在堆中删除任意一个元素在堆中删除任意一个元素这里说指的删除任意一个元素，是指在当前堆中位置为w的元素。过程如下：首先把位置w的元素和最后一个位置的元素交换，然后删去最后一个位置，这样w上的元素就被删除了。接着把位置w上的新元素不断下调，直到满足堆的性质。第68页/共83页155786431557864315
36、578634(1)当前要删除的节点是根节点的左儿子(2)将根节点的左儿子和最后一个节点交换(3)将新的节点不断下调，直到满足堆的性质22第69页/共83页删除删除(实际上是不断向下调整的过程实际上是不断向下调整的过程)PROCdown(k:longint);把第k个结点往下调beginwhilek+k=ndobegini:=min2k,2k+1;如果2k+1不存在直接返回k+k否则返回2个中间的值较小的元素ifsti=2),要求一个具有要求一个具有m个外部节点的扩充二叉树，每个外部个外部节点的扩充二叉树，每个外部ki节点有一个节点有一个wi与之对应，作为它的权与之对应，作为它的权,使得带权外部
37、路径长度使得带权外部路径长度最小，其中最小，其中li是从根到外部节点的路径长度。是从根到外部节点的路径长度。应用应用1：哈夫曼树：哈夫曼树第73页/共83页算法算法1.构造m个只有1个节点的树2.找两个最小的权3.以这两个节点为左右儿子构造一个二叉树，并将该数的根节点权之为左右儿子权值之和4.继续第二步，直到剩下一棵树为止第74页/共83页应用应用2：任务：任务有n个任务，每个任务有一个截止完成的时间Ti和完成需要的时间Ci。现在你一个人希望从0时刻开始完成尽量多的任务。问最多能完成多少任务？第75页/共83页引例：数列操作引例：数列操作假设有一列数假设有一列数Ai(1in)，支持如下两种操作
38、：，支持如下两种操作：1.将将Ak的值加的值加D。（。（k,D是输入的数）是输入的数）2.输出输出As+As+1+At。（。（s,t都是输入的数，都是输入的数，ST）输入：第一行一个整数输入：第一行一个整数n，第二行为第二行为n个整数，表示个整数，表示Ai的初始值。的初始值。第三行为一个整数第三行为一个整数m，表示操作数，表示操作数下接下接m行，每行描述一个操作，有如下两种情况：行，每行描述一个操作，有如下两种情况：ADDkd(表示将表示将Ak加加d，1=k1:a,(a+b)div2为T的左儿子；(a+b)div2,b为T的右儿子。若L=1:T为叶子节点。表示区间1,10的线段树样例：1,10
39、 1,5 5,10 1,3 3,5 5,7 7,10 1,2 2,3 3,4 4,5 5,6 6,7 7,8 8,10 8,9 9,10 第78页/共83页线段树的建立线段树的建立我们知道，对于长度为n的线段建立的线段树，至多只有nlogn个节点，故建立线段树的复杂度是O(nlogn)Procedure MakeTree(a,b)Var Now:LongintBegin tot tot+1 Now tot TreeNow.a a TreeNow.b b If a+1 b then TreeNow.Left tot+1 MakeTree(a,)TreeNow.Right tot+1 MakeTr
40、ee(,b)End 第79页/共83页回到原问题回到原问题我们用线段树来维护序列。给线段树的每个节点增加一个域Treei.S，表示该区间内所有值的和。对于ADDkd操作，只需要从根节点开始遍历线段树中每个包含了k的区间节点，然后修改S域。由于这样的区间至多只有logn个，所以一次ADD操作的复杂度是O(logn)第80页/共83页SUM操作操作对于待计算的区间对于待计算的区间s,t：Functiongetsum(v):integer;if(s=Treev.a)and(Treev.b=t)thengetsum:=Treev.Selsebegintot:=0;ifs,t和和Treev.Left表示
41、的区间相交表示的区间相交thentot:=tot+getsum(Treev.Left);ifs,t和和Treev.Right表示的区间相交表示的区间相交thentot:=tot+getsum(Treev.Right);getsum:=totend;我们不难发现这个过程中所遍历到的区间数（节点数）和我们不难发现这个过程中所遍历到的区间数（节点数）和线段树的深度同阶，因此时间复杂度是线段树的深度同阶，因此时间复杂度是O(logn)第81页/共83页问题的解决问题的解决综上，M次操作的时间复杂度为O(Mlogn)通过引入线段树的数据结构，虽然ADD操作的复杂度提高到了O(logn)。但SUM操作变得更快(O(logn)。从而也使得算法在大数据处理上更加高效。第82页/共83页谢谢您的观看！第83页/共83页