排序二叉树.ppt

《排序二叉树.ppt》由会员分享，可在线阅读，更多相关《排序二叉树.ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、排序二叉树BinarySortTree线性表知识回顾数组静态实现链表实现线性表知识回顾数组静态实现data:arrayof1.maxnofinteger查找:顺序查找O(n)二分查找O(logn)插入:O(n)删除:O(n)数组静态实现（查找）data:arrayof1.maxnofinteger查找:顺序查找O(n)Functionsearch(x:longint):longint;返回关键字为x的节点编号，如不存在返回0vari:longint;b:boolean;Begini:=1;b:=false;while(inthensearch:=0;End;数组静态实现（查找）data:arr

2、ayof1.maxnofinteger查找:二分查找O(logn)Functionsearch(x,i,j:longint):longint;在i至j范围内查找,返回关键字为x的节点编号,如不存在返回0varm:longint;Beginifijthenbeginsearch:=0;exit;end;ifi=jthenifx=dataithensearch:=ielsesearch:=0elsebeginm:=(i+j)div2;ifx=datamthensearch:=mifdatamxthensearch:=search(x,i,m-1);ifdatamxthensearch:=searc

3、h(x,m+1,j);end;End;数组静态实现（插入）data:arrayof1.maxnofinteger插入:O(n)procedureinsert(x,k:longint):longint;将关键字为x的节点插入到k号节点前面vari:longint;Beginfori:=ndowntokdodatai+1:=datai;datak:=x;n:=n+1;End;数组静态实现（删除）data:arrayof1.maxnofinteger删除:O(n)proceduredelete(x:longint);删除k号节点vari:longint;Beginfori:=k+1tondodata

4、i-1:=datai;n:=n-1;End;线性表知识回顾链表实现data:arrayof1.maxn,1.2ofintegerdatai,2表示元素datai,1的后继编号查找:顺序查找O(n)插入:O(1)删除:O(1)data:arrayof1.maxn,1.2ofintegerFunctionsearch(x:longint):longint;返回关键字为x的节点编号,如不存在返回0,s为根结点编号vari:longint;b:boolean;Begini:=s;b:=false;repeatifdatai,1=xthenbeginsearch:=i;b:=true;endelsei:

5、=datai,2untilbordatas,2=0;ifnot(b)thensearch:=0;End;链表实现（查找O(n)）data:arrayof1.maxn,1.2ofintegerprocedureinsert(x,i:longint);将关键字为x的节点插入到i号节点后面Beginn:=n+1;datan,2:=datai,2;datan,1:=x;datai,2:=nEnd;链表实现（插入O(1)）data:arrayof1.maxn,1.3ofintegerdatai,3表示i号节点的父节点编号proceduredelete(i:longint);删除i号节点Beginy:=d

6、atai,3;ify=0thens:=datai,2elsedatay,2:=datai,2;End;链表实现（删除O(1)）定义(递归)二叉排序树(BinarySortTree)又称二叉查找(搜索)树(BinarySearchTree)。定义：二叉排序树或者是空树，或者是满足如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身又各是一棵二叉排序树。上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。左根右特点由BST性质可得：（1）二叉排序树中任一结点x，其左(右

7、)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。（2）二叉排序树中，各结点关键字是唯一的。注意：实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中BST性质(1)里的小于改为大于等于，或将BST性质(2)里的大于改为小于等于，甚至可同时修改这两个性质。（3）按中序遍历该树所得到的中序序列是一个递增有序序列。排序二叉树698752341中序遍历:123456789132231123123132排序二叉树n遍历(中序):O(n)n查找:O(logn)n插入:直接递归O(logn)n删除:O(logn)n先查找到该结点n无儿子:直接删除O(1)n单个儿子

8、:用儿子代替它O(1)n两个儿子:用后继(在右子树中一直左走)代替它排序二叉树链表实现TreeNode=recordv:longint;left,right,p:longint;end;Data:array1.maxnoflongint;排序二叉树遍历(中序):O(n)procedureprint(x:longint);beginifdatax.left0thenprint(datax.left);writeln(datax.key);ifdatax.right0thenprint(datax.right);end;注:datax.left=0表示该节点没有左子树，一般常用或者-来表示虚拟结点

9、（没有孩子）排序二叉树查找:O(logn)functionsearch(x,i:longint):boolean;关键字为x的节点是否在以i号节点为根的二叉树上beginifdatai.v=xthensearch:=trueelseifxdatai.vthenifdatax.left=0thensearch:=falseelsesearch(x,datai.left);ifxxthenifdatai.left0theninsert(datai.left,x)elsebegininc(s);datai.left:=s;datas.v:=x;endelseifdatai.right0thenins

10、ert(datai.right,x)elsebegininc(s);datai.right:=s;datas.v:=x;end;end;end;排序二叉树插入:O(logn)procedureinsert(x,i:longint);将编号为x的节点插入到以i号节点为根的二叉树中beginy:=0;whilei0dobeginy:=i;ifdatax.vdatai.vtheni:=datai.leftelsei:=datai.right;end;datax.p:=y;ify=0thenroot:=xelseifdatax.vdatay.vthendatay.left:=xelsedatay.ri

11、ght:=x;end;排序二叉树6987523415.55.55.55.55.5排序二叉树最大最小值:O(logn)functionmax(i:longint):longint;返回以i号节点为根的二叉树上的最大节点的编号beginwhiledatai.right0doi:=datai.right;max:=i;end;functionmin(i:longint):longint;返回以i号节点为根的二叉树上的最大节点的编号beginwhiledatai.left0doi:=datai.left;min:=i;end;排序二叉树687523419排序二叉树前趋:O(logn)X无左儿子X有左儿

12、子：x前趋是其左子树的最大值（1）X是其父的右儿子：x前趋是其父（2）X是其父的左儿子：找到其最低的祖先(满足是其父的右儿子),该节点的父节点是x的前趋若无这样的祖先，无后继X无父亲节点(根):无后继,x是最大节点（3）（4）X的前趋排序二叉树前趋:O(logn)functionpred(i:longint):longint;返回i号节点的前趋节点的编号,如果无后继返回0beginifdatai.left0dopred:=max(datai.left)elsebeginx:=datai.p;while(x0)and(datax.left=i)dobegini:=x;x:=datax.pend;

13、pred:=x;end;end;前趋情况（1）6987523416的前趋是其左子树的最大值56987523415的前趋是其父4前趋情况（2）912111082341前趋情况（3）676的前趋是其最近的祖先（该节点是其父节点的右儿子,若该节点是其父的左儿子则再向上追溯）8的父节点469876无前趋前趋情况（4）排序二叉树后继:O(logn)X无右儿子X有右儿子：x后继是其右子树的最小值（1）X是其父的右儿子：x前趋是其父（2）X是其父的左儿子：找到其最低的祖先(满足是其父的右儿子),该节点的父节点是x的前趋若无这样的祖先，无后继X无父亲节点(根):无后继,x是最大节点（3）（4）X的后继排序二叉

14、树后继:O(logn)functionsucc(i:longint):longint;返回i号节点的后继节点的编号,如果无后继返回0beginifdatai.right0dosucc:=min(datai.right)elsebeginx:=datai.p;while(x0)and(datax.right=i)dobegini:=x;x:=datax.pend;succ:=x;end;end;后继情况（1）6987523416的后继是其右子树的最小值715201817723611399的后继是其父节点13后继情况（2）71098523415的后继是其最近的祖先（该节点是其父节点的左儿子,若该节

15、点是其父的右儿子则再向上追溯）4的父节点7后继情况（3）后继情况（4）6523416无后继排序二叉树删除:O(logn)proceduredelete(i:longint);删除编号为i的节点beginif(datai.left=0)or(datai.right=0)theny:=ielsey:=succ(i);ifdatay.left0thenx:=datay.leftelsex:=datay.rhghtifx0thendatax.p:=datay.pifdatay.p=0thenroot:=xelseify=datadatay.p.leftthendatadatay.p.left:=xel

16、sedatadatay.p.right:=x;ifyithendatai.v:=datay.vend;排序二叉树71098523416被删除节点6无儿子，直接删除排序二叉树71092341被删除节点5有一个儿子，由其儿子接替其位置566排序二叉树7109852341被删除的节点4有两个儿子，找到其后继节点，先删除其后继节点（即右子树的最小节点，不会有两个儿子），再用后继节点替代其位置6排序二叉树7109862351被删除的节点4有两个儿子，找到其后继节点，先删除其后继节点（即右子树的最小节点，不会有两个儿子），再用后继节点替代其位置说明有两个儿子的节点的后继节点不可能有两个儿子其右子树的最小值

17、节点不会有左儿子（若有，其左儿子小于它，非最小值）排序二叉树7109852341被删除的节点4有两个儿子，找到其前趋节点，先删除其前趋节点（即左子树的最大节点，不会有两个儿子），再用前趋节点替代其位置6被删除的节点4有两个儿子，找到其前趋节点，先删除其前趋节点（即左子树的最大节点，不会有两个儿子），再用前趋节点替代其位置7109851236排序二叉树71098523416被删除的节点4有两个儿子，找到其前趋节点，先删除其前趋节点（不会有两个儿子），再用前趋节点替代其位置排序二叉树710985123被删除的节点4有两个儿子，找到其前趋节点，先删除其前趋节点（不会有两个儿子），再用前趋节点替代其位

18、置6说明有两个儿子的节点的前趋节点不可能有两个儿子其左子树的最大值节点不会有右儿子（若有，其右儿子大于它，非最大值）排序二叉树动态实现TreeNode=recordv:integer;left,right,father:TreeNode;end;优点:可实现在线算法缺点:编程容易出错(删除和指针操作),树容易不平衡排序二叉树动态实现TreeNode=recordv:integer;left,right,father:integer;end;Data:array1.maxnofTreeNode;排序二叉树静态实现（用类完全二叉树实现）Value:array1.maxnofinteger;Coun

19、t:array1.maxnofinteger;优点:编程简单(插入删除查找统一),树完美平衡缺点:只能实现离线算法,需要知道所有数据并排序问题:可能不平衡解决:AVL,RB-Tree,SplayTree,Treap排序二叉树排序二叉树(BinarySortTree)又称二叉搜索树(BinarySearchTree)。它是这样一种二叉树定义：不包含任何结点的空树是一棵排序二叉树；在一棵非空的排序二叉树中，它的左子树是一棵键值都小于根的排序二叉树，它的右子树是一棵键值都大于根的排序二叉树；不难发现，相同的节点可以组成多种不同形状的排序二叉树，请问：对于n个不同的节点，最多可以组成多少种不同形状的排

20、序二叉树。bsta.in3bsta.out5样例分析132231123123132样例分析分析N个节点的二叉树可以分为N类（以第N个节点为根的二叉树）g(i)表示以第i个节点为根的不同二叉树数f(i)=g(1)+g(2)+g(i)f(i)表示i个不同节点组成的不同二叉树数分析f(1)=1f(3)=g(1)+g(2)+g(3)=2+1+2=5f(2)=2g(1)=f(2)=2g(2)=f(1)*f(1)=1g(3)=f(2)=2分析f(4)=g(1)+g(2)+g(3)+g(4)=5+2+2+5=14g(1)=f(3)=5g(2)=f(1)*f(2)=1*2=2g(3)=f(2)*f(1)=2*

21、1=2g(4)=f(3)=5分析f(k)=f(k-1)+f(1)*f(k-2)+f(k-2)*f(1)+f(k-1)算法：递推算法分析时间复杂度：O(n2)空间复杂度：O(n)统计数字 某次科研调查时得到了某次科研调查时得到了n个自然数，每个数均个自然数，每个数均不超过不超过1500000000(1.5*109)。已知不相同的。已知不相同的数不超过数不超过10000个，现在需要统计这些自然数各自个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统出现的次数，并按照自然数从小到大的顺序输出统计结果。计结果。输入输出样例输入：8242451002100输出：234251100

22、2数字统计nconstmaxm=10000;ntypevice=recordnkey,left,right,num:longint;nend;nvarf:text;ndata:array1.maxmofvice;n,s:longint;initprocedureinit;vari:longint;beginassign(f,count.in);reset(f);readln(f,n);fori:=1tomaxmdobeginwithdataidobeginleft:=0;right:=0;num:=0;end;end;readln(f,data1.key);inc(data1.num);s:=

23、1;end;mainproceduremain;vari,x:longint;beginfori:=2tondobeginreadln(f,x);insert(1,x);end;close(f);end;procedureinsert(x,y:longint);将y插入到以x号节点为根的二叉树中beginifdatax.key=ytheninc(datax.num)elsebeginifdatax.keyythenifdatax.left0theninsert(datax.left,y)elsebegininc(s);datax.left:=s;datas.key:=y;datas.num:=

24、1;endelseifdatax.right0theninsert(datax.right,y)elsebegininc(s);datax.right:=s;datas.key:=y;datas.num:=1;end;end;end;print(x)中序输出以x号节点为根的二叉树procedureprint(x:longint);beginifdatax.left0thenprint(datax.left);writeln(f,datax.key,datax.num);ifdatax.right0thenprint(datax.right);end;复杂度分析n空间复杂度:40Kn时间复杂度:

25、O(nlogm)n期望得分:100分采矿金矿的老师傅年底要退休了。经理为了奖赏他的尽职尽责的工作，决定在一块包含n（n15000）个采金点的长方形土地中划出一块长度为S，宽度为W的区域奖励给他（1s,w10000）。老师傅可以自己选择这块地的位置，显然其中包含的采金点越多越好。你的任务就是计算最多能得到多少个采金点。如果一个采金点的位置在长方形的边上，它也应当被计算在内.kop.in1212001122334555421405502332kop.out4采矿采矿方法一:穷举枚举每一对点,j比i大保证不出现(a,b)(b,a)重复求出这一对点所对应的虚拟点作为左上角点复杂度分析时间复杂度:O(n

26、3)空间复杂度:O(n)样例图示n n初步，对X离散化后，图示对于每一种坐标对于每一种坐标y y，建立成两个点事件建立成两个点事件(y,+1),(y+w+1,-1)y,+1),(y+w+1,-1)，例如在一个带状区域内有例如在一个带状区域内有5 5个点的纵坐标分别是个点的纵坐标分别是55，3 3，9 9，1 1，99，w=2w=2，标成标成(1,+1),(4,-(1,+1),(4,-1),(3,+1),(6,-1),(5,+1),(8,-1),(3,+1),(6,-1),(5,+1),(8,-1),(9,+1),(12,-1),(9,+1),(12,-1),1),(9,+1),(12,-1),

27、(9,+1),(12,-1),再将他们按照再将他们按照y y的坐标排序，得的坐标排序，得(1,+1),(3,+1),(4,-1),(5,+1)(1,+1),(3,+1),(4,-1),(5,+1)，(6,-1),(6,-1),(8,-1),(9,+1),(9,+1),(12,-1),(12,-1)(8,-1),(9,+1),(9,+1),(12,-1),(12,-1)我们把后面的标号反映在一个我们把后面的标号反映在一个y y坐标的映射上，坐标的映射上，然后从低到高求和然后从低到高求和 n n坐标下的求和，这些和中最大的一个就是该带坐标下的求和，这些和中最大的一个就是该带状区域中一个包含最多点数

28、的矩形状区域中一个包含最多点数的矩形 n n在插入或者删除一个点事件之后，能够维持坐在插入或者删除一个点事件之后，能够维持坐标下标下 的值；能够在很短时间内得到的值；能够在很短时间内得到 中最大中最大的一个值。的一个值。实现：实现：n nSUMnow对应子树上所有+1，-1标号的和。实现极简单n nMAXSUMnow，子树上和最大的一个前缀的值。MAXSUM1是一种状态下得到最优解。如何维护？n nMAXSUM有哪几种可能？n n1最大值在左树上；n n2最大值正好包含根结点；n n3最大值在右树上。自下而上维护树的特性自下而上维护树的特性n n找到当前坐标对应点序号找到当前坐标对应点序号找到当前坐标对应点序号找到当前坐标对应点序号now,now,修正标号为修正标号为修正标号为修正标号为k kn nRepeatRepeatn nSUMnowSUMnowSUMnow+kSUMnow+kMAXSUMnowMAXSUMnowMaxMaxMAXSUMnow*2,MAXSUMnow*2,n nSUMnow-SUMnow*2+1,SUMnow-SUMnow*2+1,n nSUMnow-SUMnow-SUMnow*2+1+MAXSUMnow*2+1SUMnow*2+1+MAXSUMnow*2+1n n n nnownownowdiv2nowdiv2n nuntiluntilnow=0now=0