第三次做此题。。
不解释啦。
不过变成用SBT来做啦！
SBT好处在于能够保证树的高度为lgn，真真正正的平衡二叉树。
因此删除，插入操作与普通二叉树几乎相同。
#include #include #include #include #include #include #include #include #include #include #include <set> #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define INF 0x3f3f3f3f #define MAXN 100005 using namespace std; int cnt, rt; struct SBT { 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].num=num; 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); } void Insert(int key, int &x, int num) { if(!x) x=Newnode(key, num); else { T[x].size++; Insert(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=T[x].son[0]; while(T[y].son[1]) y=T[y].son[1]; T[x].key=T[y].key; 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) { 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 main () { int p, key, num, x; while(scanf("%d", &p) && p) { switch (p) { case 1: scanf("%d%d", &num, &key); Insert(key, rt, num); break; case 2: x=GetPth(T[rt].size, rt); if(x) { printf("%d\n",T[x].num); Delete(T[x].key, rt); } else printf("0\n"); break; case 3: x=GetPth(1, rt); if(x) { printf("%d\n",T[x].num); Delete(T[x].key, rt); } else printf("0\n"); } } return 0; }
POJ 3481 SBT做法
京公网安备 11010802041100号