终于终于终于，写完了，长达将近两个小时的斗争，，，，(^_−)☆
（进入正题）
平衡树，这个词我听了好长时间了，但是，一直拖着没学，当今天老师讲到要用了，我才学，，，（没事，只要想学，什么时候都不晚）
平衡树的定义就是：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。所以，他有自己对于每个点严格的要求，因此，他可以保持平衡。
为什么用平衡树？——当然是因为它复杂度低，而且应用广泛啊！
平衡树的时间复杂度：
设n为树内节点个数，h为树的高度，树的各种操作的复杂度都依赖于树的高度，所有操作的复杂度均为O(h), h可能log(n)，也可能n，则普通的二叉查找树，操作复杂度均为log(n)，最坏情况可能O(n)，可以证明，随机构造的树的平均高度为log(n)，所以平均复杂度为log(n)。这样就能解决好多数据结构的体了吧，，，，
（先好好看代码吧，，，）
这里就解释一下代码中右（左）旋的过程：
先画一颗完美的树
（如何画一颗完美的树，，(๑╹◡╹)ﾉ"""）
现在就看刚刚画出的树，现在要让它其中的D节点变成B节点的父亲，这就是旋转的目的，那么由平衡树的定义可知道要保证高度和顺序（左儿子<右儿子），通过下面代码的推理，就能画出一个更完美的树，（如图）
（仿佛上面的都比较水）
重要的是代码（注释）！！！
为了更好的了解平衡树，我干了件有意思的事，，，
每行都写上注释
（尽管很慢，还很没意思，但是很好的让我迅速理解平衡树的操作！）
interesting code：
#include<bits/stdc++.h>using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;}const int sea=100100;int ch[sea][2],fa[sea],key[sea],cnt[sea],size[sea],root,sz;//fa[i]表示i的父结点，ch[i][0]表示i的左儿子，ch[i][1]表示i的右儿子，key[i]表示i的关键字（即结点i代表的那个数字），cnt[i]表示i结点的关键字出现的次数（相当于权值），size[i]表示包括i的这个子树的大小；sz为整棵树的大小，root为整棵树的根。//先写前置的四项基本用法：clear,get,rotate,splay;void clear(int x){ch[x][1]=ch[x][0]=fa[x]=size[x]=cnt[x]=key[x]=0;} //必备的清空此节点的操作 bool get(int x){return ch[fa[x]][1]==x;}//判断此节点在他父亲的哪个节点，如果是在右子树时，就return 1; void update(int x){if(x)//根节点不更新 {size[x]=cnt[x];//赋成当前点的权值 if(ch[x][0]) size[x]+=size[ch[x][0]];//加上左子树 if(ch[x][1]) size[x]+=size[ch[x][1]];//加上右子树}}void rotate(int x)//这一部分具体看图{int old=fa[x],fold=fa[old],w=get(x);ch[old][w]=ch[x][w^1]; fa[ch[old][w]]=old;//B_Gch[x][w^1]=old;fa[x]=fold;fa[old]=x;//B_Dif(fold) ch[fold][ch[fold][1]==old]=x;//D_Aupdate(old); update(x);//更新B、D }void splay(int x){for(int i;i=fa[x];rotate(x))//向上旋找到他的父亲，直到根节点 if(fa[i]) rotate((get(x)==get(i))?i:x);//为了防止单链单旋的情况，如果有单链的情况就直接转化为双旋，先旋fa[x]，否则先旋x root=x;//把现在旋到的点标记为根节点 }//基本操作写完之后就来好好敲一下题目上给的内容吧 六个函数：add,del,find,findx,before,next void add(int x){if(root==0){sz++;ch[sz][0]=ch[sz][1]=fa[sz]=0;root=sz;size[sz]=cnt[sz]=1;key[sz]=x;return ;}//当插入前就是一颗空树时，总大小++，左右儿子为0，根节点是1，权值是1，1的关键字是x int now=root,f=0;while(1){if(x==key[now]){cnt[now]++; update(now);update(f);splay(now);break;}//从上到下遍历，如果遍历到x就进行更新操作，先加上权值，更新此节点、他的父亲节点，在从他旋到根节点 f=now; now=ch[now][key[now]<x];//如果不是的话，f先存父亲节点，now现在存的就是儿子节点了，如果比这个节点大就是右儿子if(now==0)//如果没有儿子，就手动加进去一个儿子，然后更新，（就不用更新自己了） {sz++;ch[sz][0]=ch[sz][1]=0; fa[sz]=f; size[sz]=cnt[sz]=1; ch[f][key[f]<x]=sz; key[sz]=x;update(f); splay(sz);break;} }}int find(int x){int now=root,ans=0;//开始时now为根节点 while(1){if(x<key[now]) now=ch[now][0];//如果x小就向左找 （设想一下，走到整棵树的最左端最底端排名不就是1吗） else{ans+=(ch[now][0]?size[ch[now][0]]:0);//如果比它大答案就加上左子树的大小以及根的大小（这里的大小指的是权值）。 if(x==key[now]){splay(now); return ans+1;}//这里如果找到答案就在splay一下 ans+=cnt[now]; now=ch[now][1];//ans加上根节点的权值，now移到右子树 }} }int findx(int x){int now=root;while(1){if(ch[now][0]&&x<=size[ch[now][0]]) now=ch[now][0];//如果这个节点小就接着找他的左儿子（存在左儿子）else{int temp=(ch[now][0]?size[ch[now][0]]:0)+cnt[now];//如果比它大答案就加上左子树的大小以及根的大小（这里的大小指的是权值）。if(x<=temp) return key[now];//由于是向大的方向更新的，如果找到x<=,就可以关键字return x-=temp; now=ch[now][1];//不断的缩小范围，now移到右子树 }}}int before(){int now=ch[root][0];while(ch[now][1]) now=ch[now][1];return now;}//由于是找前驱，所以只要不断地去找根节点的左子树的右节点就好， int next(){int now=ch[root][1];while(ch[now][0]) now=ch[now][0];return now;}//由于是找后驱，所以只要不断地去找根节点的右子树的左节点就好， void del(int x){int w=find(x);//在这里查找下x就是要将x旋到根节点 if(cnt[root]>1){cnt[root]--;update(root); return ;}//如果cnt[root]>1，即x是根节点的时候，不只有一个x的话，更新后直接return if(!ch[root][0]&&!ch[root][1]) {clear(root);root=0;return ;}//如果root并没有孩子，就说这课树上只有一个x而已，直接clear+return if(!ch[root][0]){int oldroot=root; root=ch[root][1];fa[root]=0; clear(oldroot);return ;}//如果只有一个根节点和右儿子或者左儿子，直接clear+returnelse if (!ch[root][1]){int oldroot=root; root=ch[root][0]; fa[root]=0; clear(oldroot); return;}//剩下的就是两个儿子的情况 int qq=before(),oldroot=root; splay(qq);//把x的前驱旋成新ch[root][1]=ch[oldroot][1]; fa[ch[oldroot][1]]=root;//然后将原来x的右子树接到新根的右子树上（注意这个操作需要改变父子关系）。这实际上就把x删除了。 clear(oldroot); update(root);//清空旧根，更新新根 }int main(){int n,opt,x;scanf("%d",&n);for (int i=1;i<=n;++i){scanf("%d%d",&opt,&x);switch(opt){case 1: add(x); break;case 2: del(x); break;case 3: printf("%d\n",find(x)); break;case 4: printf("%d\n",findx(x)); break;case 5: add(x); printf("%d\n",key[before()]); del(x); break;case 6: add(x); printf("%d\n",key[next()]); del(x); break;}}return 0;}
