学习一下各种平衡树
1.替罪羊树
一种不用旋转的平衡树,核心思想即在太不平衡时对部分子树进行重建。
设定一个参数\(\alpha\in[0.5,1)\),那么我们希望保证两个平衡
\(\alpha\)高度平衡:树高\(h\le log_{\frac{1}{a}}n\)
\(\alpha\)大小平衡:对于一个结点\(p\)满足\(max(size_{l_p},size_{r_p})\le \alpha size_p\)
如果每个结点均满足\(\alpha\)大小平衡,假设最深的点为\(d\),那么有
$$1\le n\alpha^{dep_d}$$
那么\(dep_d\le log_{\alpha}\frac{1}{n}=log_{\frac{1}{\alpha}}n\),即满足\(\alpha\)高度平衡。
插入和普通BST类似,只需要判断插入操作是否导致了这一条链上结点的大小平衡被破坏,如果有的话将深度最浅的点所在子树暴力重建。重建最简单的方法就是对这棵子树中序遍历后分治建树。通过势能分析可以证明每一次插入的均摊复杂度为\(logn\)。
查询和普通BST并无区别。
删除操作比较巧妙。对于一次删除,我们并不马上移除这个点,而是直接这个点上打上删除标记,查询时跳过该点。重构时可以顺便删除打了删除标记的点。当被删除结点的个数超过总结点数的\((1-\alpha)\)倍时可以选择重构整棵树进行结构优化,并且显然这部分重构的复杂度不会超过\(O(nlogn)\)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
// <3224_scap.cpp> - 01/22/17 14:54:42 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=100010; const int INF=1e9; const double alpha=0.75; int rt,tot,s[MAXN][2]; int val[MAXN],size[MAXN],cover[MAXN]; bool del[MAXN]; int lt,lis[MAXN]; inline void update(int x){ int l=s[x][0],r=s[x][1]; size[x]=size[l]+size[r]+!del[x]; cover[x]=cover[l]+cover[r]; } void dfs(int x){ if(!x)return; dfs(s[x][0]); if(!del[x])lis[++lt]=x; dfs(s[x][1]); } int divide(int l,int r){ if(l>r)return 0; int m=l+r>>1; s[lis[m]][0]=divide(l,m-1); s[lis[m]][1]=divide(m+1,r); update(lis[m]); return lis[m]; } inline void rebuild(int &p){ lt=0;dfs(p); p=divide(1,lt); } int* Insert(int &p,int x){ if(!p){ val[p=++tot]=x; size[p]=cover[p]=1; return NULL; }else{ size[p]++;cover[p]++; int *q=Insert(s[p][x>=val[p]],x); if(max(cover[s[p][0]],cover[s[p][1]])>cover[p]*alpha+5)q=&p; return q; } } inline void insert(int x){ int *p=Insert(rt,x); if(p)rebuild(*p); } inline int rank(int x){ int p=rt,res=1; while(p){ if(x<=val[p])p=s[p][0]; else res+=size[s[p][0]]+!del[p],p=s[p][1]; } return res; } inline int kth(int k){ int p=rt; while(p){ if(!del[p]&&k==size[s[p][0]]+1)return val[p]; if(k<=size[s[p][0]])p=s[p][0]; else k-=size[s[p][0]]+!del[p],p=s[p][1]; } } inline void Erase(int k){ int p=rt; while(p){ size[p]--; if(!del[p]&&k==size[s[p][0]]+1){del[p]=1;return;} if(k<=size[s[p][0]])p=s[p][0]; else k-=size[s[p][0]]+!del[p],p=s[p][1]; } } inline void erase(int x){ Erase(rank(x)); if(size[rt]<cover[rt]*alpha)rebuild(rt); } int main(){ int T=gi(); while(T--){ int op=gi(),x=gi(); switch(op){ case 1:insert(x);break; case 2:erase(x);break; case 3:printf("%d\n",rank(x));break; case 4:printf("%d\n",kth(x));break; case 5:printf("%d\n",kth(rank(x)-1));break; case 6:printf("%d\n",kth(rank(x+1)));break; } } return 0; } |
2.Splay
算是复习一下吧
Splay的核心操作Splay,将一个节点通过旋转调整至某一位置并保持BST性质。
旋转的话看这张图应该就能理解:
Splay分三种情况进行旋转:
- 父亲即为目标结点。直接旋转一次即可。
- 自己和父亲在各自父亲的同一侧。先旋转父亲一次,再旋转自己一次。
- 自己和父亲在各自父亲的不同侧。连续旋转自己两次。
重复以上操作直到到达目标结点。
由于形态调整自由,所以可以通过旋转将一段区间位于一棵子树内从而进行区间操作。所以写这道题有点大材小用了(懒得写了)。
3.Treap
顾名思义,一个BST和堆的结合体。
给每个点随机一个权值,那么需要在Treap上保证关键字满足BST性质,权值满足堆性质。因为权值是随机的,所以期望树高是\(O(logn)\)的。
旋转式Treap
插入时先将该点像普通BST一样插入,然后不断向上旋转该点直到权值满足堆的性质。显然这样是可行的。
删除时,分三种情况:
- 该点没有儿子,直接删除该点。
- 该点有一个儿子,直接将儿子接到该点所在位置。
- 该点有两个儿子,将权值较大的儿子向上旋转,继续删除过程。
那么显然这样做是不会破坏Treap的性质的。
其它操作与普通BST相同。
和Splay一样也支持区间操作。方法是新建一个权值无穷大的结点,那么这个点会被转到根节点,于是就将原序列分为了两半。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
// <3224_treap.cpp> - Tue Jan 24 20:07:45 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=100010; const int INF=1e9; int rt,tot,s[MAXN][2]; int val[MAXN],r[MAXN],size[MAXN]; inline void update(int x){size[x]=size[s[x][0]]+size[s[x][1]]+1;} inline void R(int &p,bool k){ int t=s[p][k];s[p][k]=s[t][k^1];s[t][k^1]=p;p=t; update(s[t][k^1]);update(t); } void insert(int &p,int x){ if(!p){val[p=++tot]=x;r[p]=rand();size[p]=1;return;} size[p]++; bool k=x>val[p]; insert(s[p][k],x); if(r[s[p][k]]>r[p])R(p,k); } inline void kill(int &p){ if(!s[p][0]||!s[p][1]){p=s[p][0]+s[p][1];return;} bool k=r[s[p][1]]>r[s[p][0]]; R(p,k);size[p]--; kill(s[p][k^1]); } inline void del(int &p,int k){ size[p]--; if(size[s[p][0]]+1==k)return kill(p); if(k<=size[s[p][0]])del(s[p][0],k); else del(s[p][1],k-size[s[p][0]]-1); } inline int rank(int x){ int p=rt,res=1; while(p){ if(x<=val[p])p=s[p][0]; else res+=size[s[p][0]]+1,p=s[p][1]; } return res; } inline int kth(int k){ int p=rt; while(p){ if(size[s[p][0]]+1==k)return val[p]; if(k<=size[s[p][0]])p=s[p][0]; else k-=size[s[p][0]]+1,p=s[p][1]; } } int main(){ int n=gi(); for(int i=1;i<=n;i++){ int op=gi(),x=gi(); switch(op){ case 1:insert(rt,x);break; case 2:del(rt,rank(x));break; case 3:printf("%d\n",rank(x));break; case 4:printf("%d\n",kth(x));break; case 5:printf("%d\n",kth(rank(x)-1));break; case 6:printf("%d\n",kth(rank(x+1)));break; } } return 0; } |
非旋转式Treap
不通过旋转实现BST的功能并维护Treap的性质。
两个操作:split和merge
split将一棵Treap中的前\(k\)个点和其它点分离为两棵Treap。在分离过程中分几种情况讨论:
- 左子树大小等于\(k\)或\(k-1\)。显而易见,直接返回结果。
- 左子树大小大于\(k\)。递归向左子树分离,将分离得到的右子树作为该点新的左子树。返回分离得到的左子树和自身。
- 左子树大小小于\(k\)。递归向右子树分离,将分离得到的左子树作为该点新的右子树。返回自身和分离得到的右子树。
merge将两棵Treap按顺序合并为一棵。也分两种情况:
- 左Treap权值大于右Treap。将左Treap的右子树与右Treap合并作为左Treap新的右子树。返回左Treap。
- 右Treap权值大于左Treap。将左Treap与右Treap的左子树合并作为右Treap新的左子树。返回右Treap。
这两个操作都保证了Treap的两个性质。
非旋转式Treap的区间操作更简单一些,只要把区间split出来操作,最后merge回去即可。
并且由于不需要旋转,非旋转式Treap常被用于可持久化及与其它数据结构嵌套使用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
// <3224_treap_2.cpp> - Tue Jan 24 20:07:45 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; typedef pair <int,int> pri; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=100010; const int INF=1e9; int rt,tot,s[MAXN][2]; int val[MAXN],r[MAXN],size[MAXN]; inline void update(int x){size[x]=size[s[x][0]]+size[s[x][1]]+1;} void split(int p,int k,int &a,int &b){ if(!k){a=0;b=p;return;} int l=s[p][0],r=s[p][1]; if(size[l]==k){s[p][0]=0;a=l;b=p;} else if(size[l]+1==k){s[p][1]=0;a=p;b=r;} else if(k<size[l]){split(l,k,a,s[p][0]);b=p;} else {split(r,k-size[l]-1,s[p][1],b);a=p;} update(p); } int merge(int x,int y){ if(!x||!y)return x+y; if(r[x]>r[y]){ s[x][1]=merge(s[x][1],y); update(x); return x; }else{ s[y][0]=merge(x,s[y][0]); update(y); return y; } } inline int rank(int x){ int p=rt,res=1; while(p){ if(x<=val[p])p=s[p][0]; else res+=size[s[p][0]]+1,p=s[p][1]; } return res; } inline void insert(int x){ val[++tot]=x;r[tot]=rand();size[tot]=1; int l,r; split(rt,rank(x)-1,l,r); rt=merge(merge(l,tot),r); } inline void del(int k){ int x,y; split(rt,k,x,y); split(x,k-1,x,k); rt=merge(x,y); } inline int kth(int k){ int p=rt; while(p){ if(size[s[p][0]]+1==k)return val[p]; if(k<=size[s[p][0]])p=s[p][0]; else k-=size[s[p][0]]+1,p=s[p][1]; } } int main(){ int n=gi(); for(int i=1;i<=n;i++){ int op=gi(),x=gi(); switch(op){ case 1:insert(x);break; case 2:del(rank(x));break; case 3:printf("%d\n",rank(x));break; case 4:printf("%d\n",kth(x));break; case 5:printf("%d\n",kth(rank(x)-1));break; case 6:printf("%d\n",kth(rank(x+1)));break; } } return 0; } |