平衡树性质总结长郡中学 胡天翔目录一 前言二 平衡树的定义三 平衡树的实现四 平衡树的应用五 总结前言平衡树作为一种功能极其强大，实现较为方便，操作十分灵活的数据结构，在近几年的各级比赛中层出不穷。在动态统计一类问题中，平衡树这种数据结构，能够以普通算法成千上万倍的速度，和更少的冗余，来解决问题。在阅读了不少关于平衡树的论文，以及做了不少关于平衡树的题目之后，本人获得了不少心得，于是在这里，将平衡树最基础的一些性质和操作，进行总结。平衡树的定义平衡树来源于二叉搜索树，只是加上维护其二叉树性质（平衡）的操作后，无论是在速度还是在空间以及变成复杂度上都有了极大的优化。根据维护方式以及储存方式的不同，平衡树又分为点型，线型，静态和动态。【点型与线型】这一个划分，来源于对这一棵平衡树的操作类型。点型的平衡树，其每一个节点，表示的就是离散的一个点。线型的平衡树，表示的就是一段区间。如对于序列10，5，3，4，1，7，6，2，8，他的点型和线型表示分别为：【静态与动态】静态的平衡树一般存在于已经事先知道所有操作且平衡树不需要改变的情况下，可以对数据进行预处理，预先构造出平衡树，这样在之后的操作中就不需要维护平衡而减少各种复杂度。动态的平衡树则范围更广，比如维护一个支持某些操作的数据结构时，就需要一边维护这个平衡树，一边对平衡树进行求值，这个平衡树的形态，信息都处于动态的变化之中。一般的维护动态点型平衡树的有AVL，SPLAY，SBT等几种维护方式。静态的线性平衡树被称为线段树。【信息】平衡树之所以快速，是因为在每一棵子树的根节点处保存信息，这样在对于每一次的询问或者修改时，不必完全下到每一个叶子节点，只需要从根节点处读取信息，或在根节点处标记信息即可。信息又分为两种，区间信息和标记信息。【区间信息】区间信息是用于保存这棵子树的信息的，一般有区间和，区间最大值，区间结点个数，区间深度等等。保存这些信息，有利于减少重复计算，使得在需要这些信息的时候无需下到下面的节点，而直接就在这个节点获取信息。区间信息一般是从子节点更新上来的，或者是根据这一次的操作直接修改。【标记信息】标记信息是用于记录这一棵子树的修改信息的，如区间所有数是否加上了一个同一个值，是否都修改成了同一个值。保存这些信息就使得在修改一段区间的值时，不需要把每一个节点的值都修改，只需记录根节点上，有需要时再下放标记即可。【下放标记】标记信息大多数情况不能永远保存在根节点，在对根节点所对应的一段区间中的一部分子区间进行修改时，就需要现将根节点的标记信息下放，才能进行下一步的标记和修改。但是在平衡树是静态的，而且不下放标记不会对询问造成影响的情况下，是可以将标记信息保存在根节点的。【修改与求值】修改是对应于点和线的，对于点型的修改，只需在整棵平衡树中找到这个点的位置，进行修改，并将一路上的信息一并更新即可。线性的修改，基本如此，只是在线段跨越两个子树的时候分为两个过程，分别修改即可。求值一般是对应于线的，且求值与修改基本无异，递归找到最基本的线段，在返回的路上一层层合并更新，就可以得到最终的值。平衡树的实现如前面所述，平衡树基于普通的二叉搜索树，对于普通的二叉搜索树的介绍，这里省去不说。【平衡树的存储】类似于树的存储，大多数时候建议使用虚二叉树，即编号为T的根节点，其左子树的边号为T*2，右子树的边号为T*2+1.【平衡树的操作】平衡树有两种基本操作，修改与求值，在上一篇说过一些，在这里介绍其基本结构。Function 处理(T)BeginIf 操作的区间完全覆盖T的区间 Then Begin 修改T的区间信息修改T的标记信息End Else Begin将标记下放 处理T的左子树 处理T的右子树更新T的区间信息EndEnd根据实际需要，可以适当的添删操作。【平衡树的维护】对于平衡树，我们会采取一些方法，利用一些关键字，使得平衡树保持“平衡”的性质。【为什么要维护】不难发现，对于平衡树的每一个操作，其时间复杂度就是每一次的深度，所以，顾名思义，“平衡”就是指左右子树基本一致，这样就能使平衡树更大程度的接近于一个完全二叉树，从而使得树的平均深度最短。【如何维护】这里只简单的介绍一下最为简单的一种平衡树AVL。AVL是以树深度个数为关键字，要求左右子树深度相差不能超过1，来维持这棵AVL的性质。其主要操作就是旋转操作。通过旋转某一个节点，使得左右子树的深度发生变化。【单旋转】这是left-rotate(a);Function updata(t:longint);BeginSt:=sleftt+srightt+1;Deept:=max(deepleftt,deeprightt)+1;Exit(deepleftt-deeprightt);End;Function left-rotate(t:longint);VarK:longint;BeginK:=rightt;Rightt:=leftk;Leftk:=t;Updata(t);Updata(k);Exit(t);End;Right-rotate与之成镜像。【双旋转】【Maintain（保持）】由上面的单旋转和双旋转，可以得到关键的Maintain过程；Function maintain(t:longint):longint;VarKk:longint;BeginKk:=updata(t);If kk0 then rightt:=right-rotate(rightt);T:=left-rotate(t);End Else If kk1 then begin If updata(leftt)0 then leftt:=left-rotate(leftt);T:=right-rotate(t);End;Exit(t);End;Maintain操作一般加在树的节点发生变化的时候，比如插入和删除，这种时候都要加上一个Maintain操作来保证维持平衡树的性质。所以每一次操作Maintain的复杂度也是O（logN）的【不平衡的平衡树伸展树】除开AVL以外，有一种极为特殊的二叉搜索树，它并不像其他平衡树那样是平衡的，但是它有一种极为独特的操作伸展操作，这个操作就导致了它在作为一个典型平衡树时，也可以像一棵线型平衡树一样，对于整个线段，进行操作。【伸展操作】伸展操作Splay（Root，K）表示，把Root为根的子树中第K小的节点，通过旋转操作，使之成为根节点。Splay的具体实现，请阅读参考文献。平衡树的应用本篇中的题目有10道，来自于罗穗骞的论文介绍，剩下两道，来自于我的同学李说的奇思妙想。题目见附带的清澄测试包。1. Star最基础的平衡树操作，题目实际是要求对于第I个点，求横纵坐标都小于它的点有多少个，那么可以肯定的是这些点的横坐标一定小于这个店。所在按照横坐标排序之后，从左到右扫描，构建一棵以纵坐标为关键字的平衡树，每次先在平衡树中找到关键字小于yi的点有多少个，再将yi插入平衡树即可。2. Bigsmall这一道题目的本质其实就是排序，只是作为平衡树的练习题而出现在这里的。就是以数值为关键字构建一棵平衡树，每次插入Ai，最后将整棵平衡树按照中序遍历输出即可。3. unhappy把每一个员工的档案看做一个节点，以工资为关键字构建一棵平衡树。因为工资的加减是对于每一个员工的，所以可以看做标记信息，无需下放到每一个节点上，只需另外开一个变量保存，每一次的操作对于这个变量操作就可以了。而在减工资之后，判断谁需要离开，就只需要不停的判断工资最低的员工工资是否高于最低标准。而查询第K大的工资，也就可以从根节点开始一路找下去即可。4. Key这个操作可以等价于，对于每一次操作的Li，找到在Li这个位置后的第一个空位，将那个空位删除，再在Li插入K，所以需要完成的操作就只有几种。所有操作中最复杂的应是找空位操作，这是要在每一个节点处加上一个区间信息，表示这个子树内，最右边的空位在哪里，然后可以使用如下代码，来找到要找到的空位。function succ(t,k:longint):longint;var ans:longint;begin ans:=1; while true do if k=maxleftt then t:=leftt else if (bjt0) and (k=sumleftt+1) then break else begin ans:=ans+sumleftt+1; k:=k-sumleftt-1; if k=0 then k:=1; t:=rightt; end; exit(ans+sumleftt);end;而剩下的其他操作，就是属于基本操作的范围，比较简单了。5. Near伸展树的练习题。询问第I个节点时，将第I个节点提到根，然后答案就是左子树的最大值或者是右子树的最小值。针对求最大最小值的操作，可以零时按照关键字大小去找，也可以加上两维区间信息，直接调用即可。6. Editor和第三题一样的，光标的具体位置并没有必要放入子树，只需要另开一个变量保存即可。因为这道题目是针对一段一段的进行操作，所以使用Splay要十分的快捷方便。以删除操作为例：伪代码：Function delete(p:longint);BeginRoot:=splay(root,p-1);Rightroot:=splay(root,p+1);Leftrightroot:=空更新 rightroot;更新 rootEnd;这就是Splay非常巧妙方便的删除操作。7. Sequence同上一题很像，使用Splay可以轻松解决。这上面的7道题都是各种动态的平衡树，讲究维护树的性质，但是还有一种题目是不需要动态平衡树的，这时使用静态的平衡树线段树，程序就会显得更加简洁优美，时间复杂度也会相应的降低，还可以解决很多点型平衡树解决不了的问题。8. simple最简单的一维线段树。9. Phone二维线段树，因为是点修改，而且具有可减性，所以写成二维树状数组的形式。10. matrix二维线段树，这回是线修改，所以必须写二维线段树，需要注意的是，对于第一维线段树，因为它是由一维线段树拓展而来的，所以它的区间信息和标记信息都要是一个一维线段树，特别是标记信息，