1.treap
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<ctime> using namespace std; #define MAXN (100000+5) struct TreapTree{ int val[MAXN], sr[MAXN], ch[MAXN][2], fa[MAXN]; int tot, root; void rotate(int o){ int f = fa[o], g = fa[f]; int c = o == ch[f][1]; if(ch[g][0] == f) ch[g][0] = o; else if(ch[g][1] == f) ch[g][1] = o; fa[f] = o; fa[o] = g; fa[ch[o][c^1]] = f; ch[f][c] = ch[o][c^1]; ch[o][c^1] = f; if(root == f) root = o; } void insert(int f, int &o, int nval){ if(!o){ o = ++tot; val[o] = nval; sr[o] = rand(); fa[o] = f; return; } int c = nval > val[o]; insert(o, ch[o][c], nval); if(sr[ch[o][c]] > sr[o]) rotate(ch[o][c]); } void delet(int f, int o, int nval){ int lc = ch[o][0], rc = ch[o][1]; //printf("f = %d o = %d nval = %d val[%d] = %d\n", f, o, nval, o, val[o]); if(val[o] == nval){ if(!lc && !rc){ if(ch[f][0] == o) ch[f][0] = 0; else ch[f][1] = 0; fa[o] = 0; if(o == root) root = 0; return; } if(lc && !rc) rotate(lc), delet(lc, o, nval); else if(rc && !lc) rotate(rc), delet(rc, o, nval); else{ int big = sr[rc] > sr[lc]; rotate(ch[o][big]); delet(ch[o][big], o, nval); } } if(!lc && !rc) return; //显然是没有要删除的东西 int c = val[o] < nval; delet(o, ch[o][c], nval); } void print(int o){ if(ch[o][0]) print(ch[o][0]); printf("%d ", val[o]); if(ch[o][1]) print(ch[o][1]); } }; TreapTree tre; int main(){ freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); int n, m; scanf("%d%d", &n, &m); // srand(time(NULL)); srand(6); for(int i = 1; i <= n; i++){ int u; scanf("%d", &u); tre.insert(0, tre.root, u); } for(int i = 1; i <= m; i++){ int u; scanf("%d", &u); tre.delet(0, tre.root, u); printf("delet:%d\n", u); tre.print(tre.root); printf("\n\n"); }
2.splay
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; #define MAXN (100000+5) struct Splay{ int w[MAXN], ch[MAXN][2], fa[MAXN], root; int tot; void init(){ tot = root = 0; memset(w, 0, sizeof(w)); memset(ch, 0, sizeof(ch)); memset(fa, 0, sizeof(fa)); } void rotate(int o){ int f = fa[o], g = fa[f]; int c = ch[f][1] == o; if(ch[g][0] == f) ch[g][0] = o; else if(ch[g][1] == f) ch[g][1] = o; fa[o] = g; fa[f] = o; fa[ch[o][c^1]] = f; ch[f][c] = ch[o][c^1]; ch[o][c^1] = f; if(root == f) root = o; } void splay(int o){ while(fa[o]){ int f = fa[o], g = fa[f]; if(g) rotate(f); rotate(o); } root = o; } void insert(int f, int &o, int wo){ if(!o){ fa[o = ++tot] = f; w[o] = wo; splay(o); return; } if(wo > w[o]) insert(o, ch[o][1], wo); else insert(o, ch[o][0], wo); } void print(int x){ if(!x) return; print(ch[x][0]); printf("%d ", w[x]); print(ch[x][1]); } }; Splay SP; int main(){ freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); int n; scanf("%d", &n); for(int i = 1; i <= n; i++){ int x; scanf("%d", &x); SP.insert(0, SP.root, x); } SP.print(SP.root); printf("\n"); return 0; } 更多的信息维护，如size，sum, add, val等, 详见vjudge 平衡树练习
