SBT
Size Balabce Tree
SBT的平衡条件是，对于一个节点，他的size必须大于等于他的兄弟的左右儿子的size
不满足的话，就要进行修复操作，即maintain操作
加入我们现在修复的是T[x].son[1]，
如果T[T[T[x].son[0]].son[0]].size > T[T[x].son[1]].size 直接将x右旋 （即兄弟的左子树的size）
如果T[T[T[x].son[0]].son[1]].size > T[T[x].son[1]].size 先将T[x].son[0]左旋，再将x右旋
最后我们在重新修复x以及左右儿子
以poj 3481为例 代码如下
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> using namespace std; const int MAXN = 1000006; int cnt, root; struct Tree { int key, size, son[2] , num; }T[MAXN]; inline void PushUp(int x) { T[x].size=T[T[x].son[0]].size+T[T[x].son[1]].size+1; } inline int Newnode(int key , int num) { ++cnt; T[cnt].key=key; T[cnt].num=num; T[cnt].size=1; T[cnt].son[0]=T[cnt].son[1]=0; return cnt; } void Rotate(int p, int &x) { int y=T[x].son[!p]; T[x].son[!p]=T[y].son[p]; T[y].son[p]=x; PushUp(x); PushUp(y); x=y; } void Maintain(int &x, int p) //维护SBT的!p子树 { if(T[T[T[x].son[p]].son[p]].size > T[T[x].son[!p]].size) Rotate(!p, x); else if(T[T[T[x].son[p]].son[!p]].size > T[T[x].son[!p]].size) Rotate(p, T[x].son[p]), Rotate(!p, x); else return; Maintain(T[x].son[0], 0); Maintain(T[x].son[1], 1); Maintain(x, 0); Maintain(x, 1); } inline int Prev() //返回比根值小的最大值 若无返回0 { int x=T[root].son[0]; if(!x) return 0; while(T[x].son[1]) x=T[x].son[1]; return x; } inline int Succ() //返回比根值大的最小值 若无返回0 { int x=T[root].son[1]; if(!x) return 0; while(T[x].son[0]) x=T[x].son[0]; return x; } void Inseroot(int key, int &x, int num) { if(!x) x=Newnode(key , num); else { T[x].size++; Inseroot(key, T[x].son[key > T[x].key],num); Maintain(x, key > T[x].key); } } bool Delete(int key, int &x) //删除值为key的节点 key可以不存在 { if(!x) return 0; if(T[x].key == key) { if(!T[x].son[0]) { x=T[x].son[1]; return 1; } if(!T[x].son[1]) { x=T[x].son[0]; return 1; } int y=Prev(); T[x].size--; return Delete(T[x].key, T[x].son[0]); } else if(Delete(key, T[x].son[key > T[x].key])) { T[x].size--; return 1; } } int GetPth(int p, int &x) //返回第p小的节点 { if(!x) return 0; if(p == T[T[x].son[0]].size+1) return x; if(p > T[T[x].son[0]].size+1) return GetPth(p-T[T[x].son[0]].size-1, T[x].son[1]); else return GetPth(p, T[x].son[0]); } int GetRank(int key, int &x) //找出值<=key的节点个数 { if(!x) return 0; if(T[x].key <= key) return T[T[x].son[0]].size+1+GetRank(key, T[x].son[1]); else return GetRank(key, T[x].son[0]); } int solve(int x , int p) { if(x == 0) return 0; while( T[x].son[p] ) { x = T[x].son[p]; } return x; } int main() { int flag ,num , key; while( scanf("%d" , &flag) != EOF ) { if(flag == 0) break; if(flag == 1) { scanf("%d%d" , &num , &key); Inseroot(key , root , num); } if(flag == 2) { int tmp = solve(root , 1); if(tmp == 0) printf("0 "); else { printf("%d " ,T[tmp].num); Delete(T[tmp].key , root); } } if(flag == 3) { int tmp = solve(root , 0); if(tmp == 0) printf("0 "); else { printf("%d " , T[tmp].num); Delete(T[tmp].key , root); } } } }
至此~~ 再看一看我的主席树模板就不看数据结构了 当初是为什么就学习了主席树呢 真是忘记了