首页 > 代码库 > 三大平衡树（Treap + Splay + SBT）总结+模板
三大平衡树（Treap + Splay + SBT）总结+模板
Treap树
核心是 利用随机数的二叉排序树的各种操作复杂度平均为O(lgn)
Treap模板：
#include <cstdio>#include <cstring>#include <ctime>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 0x3f3f3f3f#define MAXN 100005using namespace std;int cnt=1,rt=0; //节点编号从1开始struct Tree{ int key, size, pri, son[2]; //保证父亲的pri大于儿子的pri void set(int x, int y, int z) { key=x; pri=y; size=z; son[0]=son[1]=0; }}T[MAXN];void rotate(int p, int &x){ int y=T[x].son[!p]; T[x].size=T[x].size-T[y].size+T[T[y].son[p]].size; T[x].son[!p]=T[y].son[p]; T[y].size=T[y].size-T[T[y].son[p]].size+T[x].size; T[y].son[p]=x; x=y;}void ins(int key, int &x){ if(x == 0) T[x = cnt++].set(key, rand(), 1); else { T[x].size++; int p=key < T[x].key; ins(key, T[x].son[!p]); if(T[x].pri < T[T[x].son[!p]].pri) rotate(p, x); }}void del(int key, int &x) //删除值为key的节点{ if(T[x].key == key) { if(T[x].son[0] && T[x].son[1]) { int p=T[T[x].son[0]].pri > T[T[x].son[1]].pri; rotate(p, x); del(key, T[x].son[p]); } else { if(!T[x].son[0]) x=T[x].son[1]; else x=T[x].son[0]; } } else { T[x].size--; int p=T[x].key > key; del(key, T[x].son[!p]); }}int find(int p, int &x) //找出第p小的节点的编号{ if(p == T[T[x].son[0]].size+1) return x; if(p > T[T[x].son[0]].size+1) find(p-T[T[x].son[0]].size-1, T[x].son[1]); else find(p, T[x].son[0]);}int find_NoLarger(int key, int &x) //找出值小于等于key的节点个数{ if(x == 0) return 0; if(T[x].key <= key) return T[T[x].son[0]].size+1+find_NoLarger(key, T[x].son[1]); else return find_NoLarger(key, T[x].son[0]); }
相关题解：
POJ 3481 treap
POJ 1442 treap
POJ 2352 treap
Splay Tree（伸展树）
核心就是 过程Splay(x, y)，即将x节点转移到y节点的子节点上面（其中y是x的祖先）。
利用其中双旋的优势能够保证查询复杂度均摊为O(lgn)
一开始理解有些困难，其实实际上不做深入的理解就是，双旋的过程就是一个建立相对平衡的二叉树的一个过程。
》对于二叉树，最极端的情况就是线性插入，使得整棵二叉树退化为一条链。比如你查询链的最后一个节点，之后再次查询第一个节点。
1）若只是单旋通过Splay(x, 0)将最后一个节点移动到根节点，需要O(n)复杂度，而查询第一个节点时又需要O(n)复杂度，来来往往就退化成一条链了。
2）若是双旋Splay(x, 0)将最后一个节点移动到根节点上时，移动过程中建立起了相对平衡的二叉树，需要O(n)，也就是查询第一个节点时，大概是需要O(lgn)复杂度。这就降低了复杂度。可以证明，总的每个操作的均摊复杂度是O(lgn)。
具体证明可以参见 杨思雨《伸展树的基本操作与应用》
I 用于维护单调队列：（以key为维护对象保证单调）
常用版：（支持相同值）
Struct Tree{
int key, size, fa, son[2];
}
void PushUp(int x);
void Rotate(int x, int p); //0左旋 1右旋
void Splay(int x, int To) //将x节点插入到To的子节点中
int find(int key) //返回值为key的节点 若无返回0 若有将其转移到根处
int prev() //返回比根值小的最大值 若无返回0 若有将其转移到根处
int succ() //返回比根值大的最小值 若无返回0 若有将其转移到根处
void Insert(int key) //插入key 并且将该节点转移到根处
void Delete(int key) //删除值为key的节点 若有重点只删其中一个 x的前驱移动到根处
int GetPth(int p) //获得第p小的节点 并将其转移到根处
int GetRank(int key) //获得值<=key的节点个数 并将其转移到根处 若<key只需将<=换为<
int cnt=1, rt=0;struct Tree{ int key, size, fa, son[2]; void set(int _key, int _size, int _fa) { key=_key; size=_size; fa=_fa; son[0]=son[1]=0; }}T[MAXN];inline void PushUp(int x){ T[x].size=T[T[x].son[0]].size+T[T[x].son[1]].size+1;}inline void Rotate(int x, int p) //0左旋 1右旋{ int y=T[x].fa; T[y].son[!p]=T[x].son[p]; T[T[x].son[p]].fa=y; T[x].fa=T[y].fa; if(T[x].fa) T[T[x].fa].son[T[T[x].fa].son[1] == y]=x; T[x].son[p]=y; T[y].fa=x; PushUp(y); PushUp(x);}void Splay(int x, int To) //将x节点插入到To的子节点中{ while(T[x].fa != To) { if(T[T[x].fa].fa == To) Rotate(x, T[T[x].fa].son[0] == x); else { int y=T[x].fa, z=T[y].fa; int p=(T[z].son[0] == y); if(T[y].son[p] == x) Rotate(x, !p), Rotate(x, p); //之字旋 else Rotate(y, p), Rotate(x, p); //一字旋 } } if(To == 0) rt=x;}int find(int key) //返回值为key的节点 若无返回0 若有将其转移到根处{ int x=rt; while(x && T[x].key != key) x=T[x].son[key > T[x].key]; if(x) Splay(x, 0); return x;}int prev() //返回比根值小的最大值 若无返回0 若有将其转移到根处{ int x=T[rt].son[0]; if(!x) return 0; while(T[x].son[1]) x=T[x].son[1]; Splay(x, 0); return x;}int succ() //返回比根值大的最小值 若无返回0 若有将其转移到根处{ int x=T[rt].son[1]; if(!x) return 0; while(T[x].son[0]) x=T[x].son[0]; Splay(x, 0); return x;}void Insert(int key) //插入key 并且将该节点转移到根处{ if(!rt) T[rt = cnt++].set(key, 1, 0); else { int x=rt, y=0; while(x) { y=x; x=T[x].son[key > T[x].key]; } T[x = cnt++].set(key, 1, y); T[y].son[key > T[y].key]=x; Splay(x, 0); }}void Delete(int key) //删除值为key的节点 若有重点只删其中一个 x的前驱移动到根处{ int x=find(key); if(!x) return; int y=T[x].son[0]; while(T[y].son[1]) y=T[y].son[1]; int z=T[x].son[1]; while(T[z].son[0]) z=T[z].son[0]; if(!y && !z) { rt=0; return; } if(!y) { Splay(z, 0); T[z].son[0]=0; PushUp(z); return; } if(!z) { Splay(y, 0); T[y].son[1]=0; PushUp(y); return; } Splay(y, 0); Splay(z, y); T[z].son[0]=0; PushUp(z); PushUp(y);}int GetPth(int p) //获得第p小的节点 并将其转移到根处{ if(!rt) return 0; int x=rt, ret=0; while(x) { if(p == T[T[x].son[0]].size+1) break; if(p>T[T[x].son[0]].size+1) { p-=T[T[x].son[0]].size+1; x=T[x].son[1]; } else x=T[x].son[0]; } Splay(x, 0); return x;}int GetRank(int key) //获得值<=key的节点个数 并将其转移到根处 若<key只需将<=换为<{ if(!rt) return 0; int x=rt, ret=0, y; while(x) { y=x; if(T[x].key <= key) { ret+=T[T[x].son[0]].size+1; x=T[x].son[1]; } else x=T[x].son[0]; } Splay(y, 0); return ret;}
完全版：（支持相同值，支持区间删除，支持懒惰标记）
Struct Tree{
int key, num, size, fa, son[2];
}
void PushUp(int x);
void PushDown(int x);
int Newnode(int key, int fa); //新建一个节点并返回
void Rotate(int x, int p); //0左旋 1右旋
void Splay(int x, int To); //将x节点移动到To的子节点中
int GetPth(int p, int To); //返回第p小的节点 并移动到To的子节点中
int Find(int key); //返回值为key的节点 若无返回0 若有将其转移到根处
int Prev(); //返回根节点的前驱
int Succ(); //返回根结点的后继
void Insert(int key); //插入key值
void Delete(int key); //删除值为key的节点
int GetRank(int key); //获得值<=key的节点个数
void Delete(int l, int r); //删除值在[l, r]中的节点
int cnt, rt;int Add[MAXN];struct Tree{ int key, num, size, fa, son[2];}T[MAXN];inline void PushUp(int x){ T[x].size=T[T[x].son[0]].size+T[T[x].son[1]].size+T[x].num;}inline void PushDown(int x){ if(Add[x]) { if(T[x].son[0]) { T[T[x].son[0]].key+=Add[x]; Add[T[x].son[0]]+=Add[x]; } if(T[x].son[1]) { T[T[x].son[1]].key+=Add[x]; Add[T[x].son[1]]+=Add[x]; } Add[x]=0; }}inline int Newnode(int key, int fa) //新建一个节点并返回{ ++cnt; T[cnt].key=key; T[cnt].num=T[cnt].size=1; T[cnt].fa=fa; T[cnt].son[0]=T[cnt].son[1]=0; return cnt;}inline void Rotate(int x, int p) //0左旋 1右旋{ int y=T[x].fa; PushDown(y); PushDown(x); T[y].son[!p]=T[x].son[p]; T[T[x].son[p]].fa=y; T[x].fa=T[y].fa; if(T[x].fa) T[T[x].fa].son[T[T[x].fa].son[1] == y]=x; T[x].son[p]=y; T[y].fa=x; PushUp(y); PushUp(x);}void Splay(int x, int To) //将x节点移动到To的子节点中{ while(T[x].fa != To) { if(T[T[x].fa].fa == To) Rotate(x, T[T[x].fa].son[0] == x); else { int y=T[x].fa, z=T[y].fa; int p=(T[z].son[0] == y); if(T[y].son[p] == x) Rotate(x, !p), Rotate(x, p); //之字旋 else Rotate(y, p), Rotate(x, p); //一字旋 } } if(To == 0) rt=x;}int GetPth(int p, int To) //返回第p小的节点 并移动到To的子节点中{ if(!rt || p > T[rt].size) return 0; int x=rt; while(x) { PushDown(x); if(p >= T[T[x].son[0]].size+1 && p <= T[T[x].son[0]].size+T[x].num) break; if(p > T[T[x].son[0]].size+T[x].num) { p-=T[T[x].son[0]].size+T[x].num; x=T[x].son[1]; } else x=T[x].son[0]; } Splay(x, 0); return x;}int Find(int key) //返回值为key的节点 若无返回0 若有将其转移到根处{ if(!rt) return 0; int x=rt; while(x) { PushDown(x); if(T[x].key == key) break; x=T[x].son[key > T[x].key]; } if(x) Splay(x, 0); return x;}int Prev() //返回根节点的前驱 非重点{ if(!rt || !T[rt].son[0]) return 0; int x=T[rt].son[0]; while(T[x].son[1]) { PushDown(x); x=T[x].son[1]; } Splay(x, 0); return x;}int Succ() //返回根结点的后继 非重点{ if(!rt || !T[rt].son[1]) return 0; int x=T[rt].son[1]; while(T[x].son[0]) { PushDown(x); x=T[x].son[0]; } Splay(x, 0); return x;}void Insert(int key) //插入key值{ if(!rt) rt=Newnode(key, 0); else { int x=rt, y=0; while(x) { PushDown(x); y=x; if(T[x].key == key) { T[x].num++; T[x].size++; break; } T[x].size++; x=T[x].son[key > T[x].key]; } if(!x) x=T[y].son[key > T[y].key]=Newnode(key, y); Splay(x, 0); }}void Delete(int key) //删除值为key的节点1个{ int x=Find(key); if(!x) return; if(T[x].num>1) { T[x].num--; PushUp(x); return; } int y=T[x].son[0]; while(T[y].son[1]) y=T[y].son[1]; int z=T[x].son[1]; while(T[z].son[0]) z=T[z].son[0]; if(!y && !z) { rt=0; return; } if(!y) { Splay(z, 0); T[z].son[0]=0; PushUp(z); return; } if(!z) { Splay(y, 0); T[y].son[1]=0; PushUp(y); return; } Splay(y, 0); Splay(z, y); T[z].son[0]=0; PushUp(z); PushUp(y);}int GetRank(int key) //获得值<=key的节点个数{ if(!Find(key)) { Insert(key); int tmp=T[T[rt].son[0]].size; Delete(key); return tmp; } else return T[T[rt].son[0]].size+T[rt].num;}void Delete(int l, int r) //删除值在[l, r]中的所有节点 l!=r{ if(!Find(l)) Insert(l); int p=Prev(); if(!Find(r)) Insert(r); int q=Succ(); if(!p && !q) { rt=0; return; } if(!p) { T[rt].son[0]=0; PushUp(rt); return; } if(!q) { Splay(p, 0); T[rt].son[1]=0; PushUp(rt); return; } Splay(p, q); T[p].son[1]=0; PushUp(p); PushUp(q);}
(经测NOI2004郁闷的出纳员 POJ3481 POJ2352 POJ1442)
速度相对来说都还不错，POJ这些都3~500ms，郁闷的出纳员900多ms
相关题解：
HNOI 2002 营业额统计
POJ 3481 splay
POJ 2352 splay
POJ 1442 splay
NOI2004 郁闷的出纳员
II 用于维护序列：（以序列下标为对象维护，相当于对区间操作）（能够完成线段树的操作及其不能完成的操作）
Struct Tree{
int key, sum, size, fa, son[2];
}
支持操作：
void PushUp(int x);
void PushDown(int x);
int MakeTree(int l, int r, int a[]); //新建一个子树返回根节点
void Rotate(int x, int p); //0左旋 1右旋
void Splay(int x, int To); //将x节点移动到To的子节点中
int Select(int p, int To); //将第p个数移动到To的子节点中 并返回该节点
int Find(int key); //返回值为key的节点 若无返回0 若有将其转移到根处
int Prev(); //返回根节点的前驱
int Succ(); //返回根结点的后继
void Insert(int p, int l, int r, int a[]) //将a[l .. r]的数插入到下标为p后面
void Delete(int l, int r); //删除区间[l, r]中的节点
int Query(int l, int r); //返回[l, r]的和
待补充。。
Size Balance Tree
和上述两种二叉树比起来，SBT可能是最像真正平衡二叉树吧。
SBT能够保证树的高度在lgn，这样对于插入，删除操作都能够准确保证时间复杂度在O(lgn)
Maintain操作事实上理解起来也是挺简单的，至于证明参见CQF神牛的《SBT》
int cnt, rt;struct Tree{ int key, size, son[2];}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){ ++cnt; T[cnt].key=key; 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[rt].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[rt].son[1]; if(!x) return 0; while(T[x].son[0]) x=T[x].son[0]; return x;}void Insert(int key, int &x){ if(!x) x=Newnode(key); else { T[x].size++; Insert(key, T[x].son[key > T[x].key]); 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]);}
相关题解：
POJ 3481 SBT做法
上述题均为用于测试平衡树基本操作的题目。
提高题：（暂时未写）
[NOI2005]维修数列
[POJ3580]SuperMemo
[HNOI2004]宠物收养所
三大平衡树（Treap + Splay + SBT）总结+模板