POJ 3481 SBT做法-白红宇

POJ 3481 SBT做法

阅读量：4320 次

发布时间：2019-06-06

本文共 2333 字，大约阅读时间需要 7 分钟。

第三次做此题。。

不解释啦。

不过变成用SBT来做啦！

SBT好处在于能够保证树的高度为lgn，真真正正的平衡二叉树。

因此删除，插入操作与普通二叉树几乎相同。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #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, 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;}