算法合集之伸展树的基本操作与应用学习教案

1、会计学1算法合集之伸展算法合集之伸展(shnzhn)树的基本操作与树的基本操作与应用应用第一页，共35页。2第2页/共35页第二页，共35页。3第3页/共35页第三页，共35页。4第4页/共35页第四页，共35页。5第5页/共35页第五页，共35页。6第6页/共35页第六页，共35页。7Splay(1,S)第7页/共35页第七页，共35页。8伸展操作是基础！第8页/共35页第八页，共35页。9第9页/共35页第九页，共35页。10对某个节点的对某个节点的访问访问(fngwn)和和旋转旋转会计方法第10页/共35页第十页，共35页。11第11页/共35页第十一页，共35页。12第12页/共35页

2、第十二页，共35页。13此外我们花费另外1元钱用来(yn li)支付访问、旋转的基本操作。所以，一次Zig或Zag操作的花费至多为3(S)-(x)+1第13页/共35页第十三页，共35页。14与情况1一样，也需要花费另外(ln wi)的1元钱来支付单位时间的操作。第14页/共35页第十四页，共35页。15第15页/共35页第十五页，共35页。16第16页/共35页第十六页，共35页。17Splay(x,S)3(S)-(x)+1O(log2n)基本操作第17页/共35页第十七页，共35页。18分析公司的营业情况是一项相当复杂的工作(gngzu)。经济管理学上定义了一种最小波动值来衡量营业情况：每

3、天的最小波动值= min | 该天以前某一天的营业额-该天的营业额 | 第一天的最小波动值为第一天的营业额。现在给出公司成立以来每天的营业额，编写一个程序计算公司成立以来每天的最小波动值的总和。数据范围：天数n32767，每天的营业额ai1,000,000。 最后结果T231。例题描述第18页/共35页第十八页，共35页。19初步(chb)分析时间复杂度O(n2)，不能在时限内出解空间要求很大，需要一个大数组编程太复杂，调试不方便第19页/共35页第十九页，共35页。20算法(sun f)描述l这题中，涉及到对于有序集的三种操作： 插入、求前趋、求后继第20页/共35页第二十页，共35页。21

4、顺序查找线段树AVL树伸展树时间复杂度O(n2)O(nlog2a)O(nlog2n)O(nlog2n)空间复杂度O(n)O(a)O(n)O(n)编程复杂度很简单较简单较复杂较简单解题(ji t)小结第21页/共35页第二十一页，共35页。22第22页/共35页第二十二页，共35页。23反复(fnf)琢磨多做比较灵活应用第23页/共35页第二十三页，共35页。24第24页/共35页第二十四页，共35页。25第25页/共35页第二十五页，共35页。26第26页/共35页第二十六页，共35页。27Splay(1,S)第27页/共35页第二十七页，共35页。28Splay(2,S)第28页/共35页第二十八页，共35页。29第29页/共35页第二十九页，共35页。30第30页/共35页第三十页，共35页。31图中，(x) =(x) =(z)。 显然(x) =(y) =(z)。并且可以得出(d ch)(x) =(z) =(z)。 令a = 1 + |A| + |B|，b = 1 + |C| + |D| 。那么 log a = log b = log (a+b+1) 不妨设ba，则有log (a+b+1) log (2a) = 1+log a log a 第31页/共35页第三十一页，共35页。32第32页/共35页第三十二页，共35页。33第33页/共3