刘汝佳高级数据结构

第2讲高级数据结构刘汝佳目录•平衡二叉树•可并优先队列•线段树和树状数组基础•RMQ与LCA一、平衡二叉树基本BST•基本BST(BinarySearchTree)定义–二叉树–左子树根右子树–递归定义:左子树和右子树均是BST•基本实现方式–查找:从根往下走O(h)–插入:查找失败后O(1).总O(h)–删除:分情况讨论,O(h)为何要平衡•越平衡,各种操作的速度越快•什么是平衡:渐进意义下树高h=O(logn)–固定结点数,则树高越小越好balancedheight(T)=O(logn)unbalancedheight(T)=O(nc),1c0extremelyunbalancedheight(T)=O(n)一、AVL树•基本思想:限制树的形状,使得满足该限制的树一定是平衡的•定义:每个结点的左右子树高度差不超过1(空树高度为-1)的排序二叉树称为AVL树•AVL树的高度.设S(n)为高度为n的AVL树的昀少结点数,则S(n)=S(n-1)+S(n-2)+1,而S(0)=1,S(1)=2,归纳得S(n)=Fh+3-1,因此max21.44loghn≈Sh-1Sh-2T1T0abqT1T0abT2pT3cT2T3cpq12旋转线两端变水平AVLAVL的单旋转的单旋转哪棵子树高度过大就以哪个儿子为轴voidrotatewithRightChild(int&p){intq=right[p];right[p]=left[q];left[q]=p;height[p]=max(height[left[p]],height[right[p]])+1;height[q]=max(height[right[q]],height[p])+1;}T1T0acT3bT2T1T0acT3bT2AVLAVL的双旋转rotatewithLeftChild(right[p]);rotatewithRightChild(p);T1T0acT3bT2不平衡的点一定有孙子祖父与孙子共线:单旋转祖父与孙子不共线:双旋转的双旋转插入算法:从插入元素开始向上找第一个祖父不平衡的点x,设父亲为p(x),祖父为g(x)…AVL树的插入•插入元素后，所有不平衡结点只可能在该元素到根的路径上•从插入元素开始向上找第一个祖父不平衡的点x,设父亲为p(x),祖父为g(x),则–x,p(x),g(x)“共线”:单旋转–x,p(x),g(x)不“共线”:双旋转•统一算法:不考虑旋转的种类,直接处理•重要结论:旋转后g(x)的高度恢复到插入以前，因此g(x)的不平衡祖先（如果有）也一起恢复平衡插入的统一算法•设x,p(x),g(x)在排序为abc;它们的四棵不相交子树排序为T0T1T2T3(四棵子树中可能有空树),则将以g(x)为根的子树替换为如下子树后,g(x)的高度恢复到插入前aT0T1cT2T3bAVL树的删除•删除叶子后，它的父亲可能不平衡，在处理后可能祖父仍不平衡…–从被删除叶子的父亲开始依次考虑各个祖先，只要不平衡就要旋转–昀坏情况：O(logn)次旋转•删除中间结点时，先套用一般BST删除–单儿子结点u：用惟一的儿子取代（注意：该儿子一定是叶子，否则u不平衡）–双儿子结点u：用u的前驱取代后删除前驱491112131068751230AVL=insert{419026113581012713}key节点类型删除方法需重新平衡?2需要8不需要无右孩子（左子树至多包含单个节点）代之以左孩子需要7、13不需要0、3、5、10需要12不需要无左孩子（右子树至多包含单个节点）代之以右孩子9不需要1、6、11、4需要左、右孩子都有代之以直接前驱内部节点叶子直接摘除二、伸展树•基本思想：不严格限制树的形状，而是假设访问有局部性，让数据在访问后不久再次访问时变快•伸展操作Splay(x,S):把x旋转到树根,同时保持树是一棵合法的BST•设y=father(x),z=father(y)–情况一:y是根结点:zig或zag–情况二:y不是根结点,且x与y同是(自己父亲的)左孩子或同是右孩子:zig-zig或zag-zag–情况三:y不是根结点,且x与y中一个是左孩子一个是右孩子:zig-zig或zag-zig三种情况的处理yyxxABCzzDyyxxABCzzDZig-ZigyyxxABCyyxxABCZig(x)Zag(y)情况1.y是根情况2.y不是根，x,y,z共线zzyyxxxxzzyyADBCABCDZig-Zag情况3.y不是根，x,y,z不共线voidsplay(int&x,int&s){intp;while(father[x]){p=father[x];if(!father[p]){if(x==left[p])Zig(x);elseZag(x);break;}if(x==left[p]){if(p==left[father[p]]){Zig(p);Zig(x);}else{Zig(x);Zag(x);}}else{if(p==right[father[p]]){Zag(p);Zag(x);}else{Zag(x);Zig(x);}}}s=x;}ppxxABCppxxABCppxxABCDppxxADBCppxxCDBAppxxDABC伸展操作的实现伸展操作的实现基本操作•Find(x,S):BST查找,然后Splay•Insert(x,S):BST插入,然后Splay–方法二：查找x后Join(留作练习)•Delete(x,S)–Find(x,S),合并x的左右儿子•Join(S1,S2):见后•Split(x,S):见后•伸展操作是基础!合并与分离•Join(S1,S2):伸展S1中的昀大元素•Split(x,S):伸展x,断开儿子S1S1S2S1S2S2S1S2S1S2intfind(intx,ints){intp=BST_Search(x,s);splay(p,s);returnp;}voidinsert(intx,int&s){intp=BST_Insert(x,s);splay(p,s);returnp;}voidremove(intx,int&s){intp=find(x,s);join(left[p],right[p]);}intmaximum(ints){intp=s;while(right[p])p=right[p];splay(p,s);returnp;}intminimum(ints){intp=s;while(left[p])p=left[p];splay(p,s);returnp;}intprev(intx,int&s){intp=find(x,s);p=left[p];returnmaximum(p);}intnext(intx,int&s){intp=find(x,s);p=right[p];returnminimum(p);}intjoin(int&s1,int&s2){if(!s1)returns2;if(!s2)returns1;intp=maximum(s1);right[p]=s2;returnp;}voidsplit(intx,int&s,int&s1,int&s2){intp=find(x,s);s1=left[p];s2=right[p];}小结•伸展:三种情况,两种基本旋转(zig,zag)•五种基本操作:以伸展为基础•时间复杂度：n个结点的伸展树,每个操作的平摊时间复杂度为O(logn)(不证)•下面的讨论均假定所有key均不相同.如果有相同的key呢?–方法一:加计数器–方法二:允许多个相同结点,注意各种操作三、Treap•有一种实现相对容易的平衡二叉树称为Treap=Tree+Heap–每个结点有两个键值–treap关于key是排序二叉树–treap关于priority是堆（除了形态不一定是完全二叉树外）•把Treap作为平衡二叉树的方法是：插入时随机取优先级，则期望树高为O(logn)•重要结论：key和priority确定时，treap惟一M1M1H2H2T3T3G7G7I4I4A9A9L8L8R5R5O6O6S-1S-1M1M1H2H2T3T3G7G7I4I4A9A9L8L8R5R5O6O6S-1S-1插入：插入：ABCDABCD删除：删除：DCBADCBAABM1M1H2H2T3T3G7G7I4I4A9A9L8L8R5R5O6O6S-1S-1M1M1H2H2T3T3G7G7I4I4A9A9L8L8R5R5O6O6S-1S-1DCvoidinsert(intx,int&p){if(!p)p=newnode(x,myrand());elseif(xkey[p]){insert(x,left[p]);if(pr[left[p]]pr[p])rotateWithLeftChild(p);}elseif(xkey[p]){insert(x,right[p]);if(pr[right[p]]pr[p])rotateWithRightChild(p);}}voidremove(intx,int&p){if(p){if(xkey[p])remove(x,left[p]);elseif(xkey[p])remove(x,right[p]);else{if(!left[p]&&!right[p])deletenode(p);if(pr[left[p]]pr[right[p]]){rotateWithLeftChild(p);remove(right[p]);}else{rotateWithRightChild(p);remove(left[p]);}}}}例1.采矿•金矿的老师傅年底要退休了。经理为了奖赏他的尽职尽责的工作，决定在一块包含n(n=15000)个采金点的长方形土地中划出一块长度为S，宽度为W的区域奖励给他(1=s,w=10000)•老师傅可以自己选择这块地的位置，显然其中包含的采金点越多越好。你的任务就是计算昀多能得到多少个采金点。如果一个采金点的位置在长方形的边上，它也应当被计算在内。平面扫描•用间隔固定的两条线L1和L2从左到右扫描，则两线之间的所有点可以忽略x坐标，即可以投影到y轴上SL1L2投影投影投影后的处理•投影之后的问题变为了：在数轴上找一个长度为W的区间，包含尽量多的点•每个点y拆成两个事件(y,+1),(y+w-1,-1)，表示区间右端点在y和y+w-1时该点进入/退出扫描区间，则扫描过程变成了累加过程，点数昀多的位置对应了昀大前缀和•主算法：从左到右处理各个点进入/退出L1-L2间区域的事件，维护昀大前缀和昀大前缀和•要求:支持以下操作–INSERT(key)–DELETE(key)–FIND(key)–MAXSUM:求昀大的k前缀和•用BST或线段树均可,结点附加信息:m(p)表示以结点p为根的子树中的昀大前缀和–如何用m(p)计算MAXSUM?答:就是m(root)–如何维护m(p)?答：利用所有结点和s(p)m(p)的计算•不管是BST插入还是伸展过程中的维护，都需要利用用儿子计算父亲的递推式•昀大前缀和的终点u有三种情况–u在以y为根的子树中,则m(x)=m(y)–u=x,则m(x)=s(y)+x–u在以z为根的子树中,则m(x)=s(y)+x+m(z)xxyyzz二、可并优先队列可并优先队列•二叉堆很好的实现了优先队列的各种操作，但是却很难将两个堆合并起来（只能将其中一个堆的元素一个一个取出来插入另一个堆）。如果两个堆的元素都有n个，需要花nlogn的时间•常用的可并优先队列有四种，其中左偏树和斜堆实现简单，实用性高。二项堆是一种非常巧妙的数据结构，实现难度适中，也是Fibonacci堆的基础。Fibonacci堆的理论时间复杂度非常优秀，特别是基于层叠提升法的decreaseKey操作，不仅思想巧妙，而且平摊时间复杂度仅为O(1)。左偏树•左偏树是一棵二叉树，每个结点定义了距离(dist)，即它到后代中昀多一个儿子的结点的昀小距