题解 P3369 【【模板】普通平衡树】-白红宇

题解 P3369 【【模板】普通平衡树】

阅读量：6036 次

发布时间：2019-06-20

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

刚刚恶补了替罪羊树，由于一个指针出锅调了贼久，必须得写一篇题解巩固一下理解。

参考了ikka大佬的博客，我的替罪羊树就是在那里学会的。

替罪羊树是一种优越的平衡树，它不像Splay和Treap有着绚丽的旋转操作，而是朴实地暴力重构。

具体来说，为了保持树结构的平衡，替罪羊树在每一次插入和删除的时候都会判断树是否平衡，根据结果选择是否要重构子树。

明白了替罪羊树的思想之后实现其实不难（毕竟思路朴实）。

平衡判断

替罪羊树最核心的部分，也就是它判断树是否平衡的过程，是通过平衡因子来实现的。

这个名字听起来很霸气很高深，但其实就是一个0.5到1之间的浮点数罢了。

1 const double alpha = 0.75;

当一颗树的左子树（或右子树）**存在的**节点数大于这棵树**存在的**节点数*平衡因子的时候，这颗树就是不平衡的。

这个过程我们会在后面用到。

节点结构体

1 struct Node{2     int val,size,cover;3     bool exist;4     Node* ch[2];5     void pushup(){
   this->size=ch[0]->size+ch[1]->size+(int)exist,this->cover=ch[0]->cover+ch[1]->cover+1;}6     int isbad(){
   return (ch[0]->cover>this->cover*alpha+5)||(ch[1]->cover>this->cover*alpha+5);}7 };

val是节点的值，size是节点子树的大小，cover是节点**存在的**的节点个数。

exist是节点是否存在。

ch是左儿子与右儿子。

pushup操作很好理解，就是size和cover都更新一下。

isbad操作判断当前子树是否是不平衡的，原理就是之前讲的那个过程。（之所以加上5是怕不稳）

你可能会注意到，本文多次强调了“存在”这个概念，没错，替罪羊树不会真正删去节点，而是将它们变为“不存在”。

新节点

你可能会认为新建节点就是new node，然鹅这样太慢了。

为了提速，我们必须手动模拟内存池（其实我听到这个词是懵逼的）。

模拟内存池的流程就是，把所有不要的节点丢进内存回收池，然后需要的时候再提取出来。

这样删除掉的节点就不会浪费，而能得到有效利用。

1 Node mempool[N]; 2 Node *tail,*null,*root; 3 Node *bc[N]; 4 int bc_top; 5 Node* newNode(int val){ 6     Node* p=bc_top?bc[--bc_top]:tail++; 7     p->ch[0]=p->ch[1]=null; 8     p->size=p->cover=p->exist=1; 9     p->val=val;10     return p;11 }

mempool就是我们模拟的内存池。tail指向内存池内的元素。

root不用管它。

null是我们模拟的空节点其实没什么用。

bc是内存回收值，bc_top是回收池顶。

创建一个新节点的流程。。。其实我觉得不说你们也看得懂，那就不说了。

重构子树

这是最核心的部分，其根本思路是讲树拍成一个有序数列，然后再重新建树。

排成有序数列做一个中序遍历就可以了，只有存在的节点才加入数列。

建树也很简单，就每次数组折半，分治建即可。

1 void Travel(Node* p,vector
     
      & x){ 2     if(p==null)return; 3     Travel(p->ch[0],x); 4     if(p->exist)x.push_back(p); 5     else bc[bc_top++]=p; 6     Travel(p->ch[1],x); 7 } 8 Node* Divide(vector
      
       & x,int l,int r){ 9     if(l>=r)return null;10     int mid=(l+r)>>1;11     Node* p=x[mid];12     p->ch[0]=Divide(x,l,mid);13     p->ch[1]=Divide(x,mid+1,r);14     p->pushup();15     return p;16 }17 void Rebuild(Node*& p){18     vector
       
         x;19     x.clear();20     Travel(p,x);21     p=Divide(x,0,x.size());22 }

数组你用啥都行，由于懒这里用vector。

实现没有什么好讲的。

插入节点

我个人认为，插入节点是替罪羊树最毒瘤的地方（指针不友好）。

插入节点在插入的同时，会返回指向指向不平衡的节点的指针的指针。

上面那句话就是我所谓的毒瘤（其实也不是很毒瘤），第一次可能会被绕地晕头转向。

之所以要返回指向指针的指针，是因为我们所有操作都需要指针。

1 Node** Insert(Node*& p,int val){ 2     if(p==null){ 3         p=newNode(val); 4         return &null; 5     } 6     p->size++,p->cover++; 7     Node** res=Insert(p->ch[val>=p->val],val); 8     if(p->isbad())res=&p; 9     return res;10 }

如果当前节点是空节点，那就新建一个节点，然后返回空节点（新的节点不会导致树不平衡）。

否则根据插入节点的值递归左右儿子。

然后假如当前节点子树不平衡，返回当前节点。

删除操作

删除操作很水，没什么技术含量。

1 void Erase(Node*& p,int k){ 2     p->size--; 3     int offset=p->ch[0]->size+p->exist; 4     if(p->exist&&offset==k){ 5         p->exist=false; 6     }else{ 7         if(k<=offset)Erase(p->ch[0],k); 8         else Erase(p->ch[1],k-offset); 9     }10 }

初始化

顺带一提，从本函数开始是非工具函数（之前的都是protected，并非外部直接调用的函数）。

1 void init(){2     tail=mempool;3     null=tail++;4     null->ch[0]=null->ch[1]=null;5     null->cover=null->size=null->exist=0;6     root=null;7     bc_top=0;8 }

初始化就搞一个空节点，然后没了。

其他操作

这些操作都是建立在工具函数的基础上，YY出来的。

要注意插入和删除都得检查树是否平衡。

然后查询rank和第K大都是循环实现，思路很朴实。

1 void insert(int val){ 2     Node** res=Insert(root,val); 3     if(*res!=null)Rebuild(*res); 4 } 5 int rank(int val){ 6     Node* now=root; 7     int ans=1; 8     while(now!=null){ 9         if(now->val>=val)now=now->ch[0];10         else{11             ans+=now->ch[0]->size+now->exist;12             now=now->ch[1];13         }14     }15     return ans;16 }17 int kth(int val){18     Node* now=root;19     while(now!=null){20         if(now->ch[0]->size+1==val&&now->exist)return now->val;21         if(now->ch[0]->size>=val)now=now->ch[0];22         else val-=now->ch[0]->size+now->exist,now=now->ch[1];23     }24 }25 void erase(int k){26     Erase(root,rank(k));27     if(root->size
     
      cover*alpha)Rebuild(root);28 }

代码

AC代码放心使用：

1 #include
     
        2 #include
      
         3 #include
       
          4 using namespace std;  5 namespace Scapegoat{  6     const int N=100100;  7     const double alpha = 0.75;  8     struct Node{  9         int val,size,cover; 10         bool exist; 11         Node* ch[2]; 12         void pushup(){
   this->size=ch[0]->size+ch[1]->size+(int)exist,this->cover=ch[0]->cover+ch[1]->cover+1;} 13         int isbad(){
   return (ch[0]->cover>this->cover*alpha+5)||(ch[1]->cover>this->cover*alpha+5);} 14     }; 15     struct Tree{ 16         protected: 17             Node mempool[N]; 18             Node *tail,*null,*root; 19             Node *bc[N]; 20             int bc_top; 21             Node* newNode(int val){ 22                 Node* p=bc_top?bc[--bc_top]:tail++; 23                 p->ch[0]=p->ch[1]=null; 24                 p->size=p->cover=p->exist=1; 25                 p->val=val; 26                 return p; 27             } 28             void Travel(Node* p,vector
        
         & x){ 29                 if(p==null)return; 30                 Travel(p->ch[0],x); 31                 if(p->exist)x.push_back(p); 32                 else bc[bc_top++]=p; 33                 Travel(p->ch[1],x); 34             } 35             Node* Divide(vector
         
          & x,int l,int r){ 36                 if(l>=r)return null; 37                 int mid=(l+r)>>1; 38                 Node* p=x[mid]; 39                 p->ch[0]=Divide(x,l,mid); 40                 p->ch[1]=Divide(x,mid+1,r); 41                 p->pushup(); 42                 return p; 43             } 44             void Rebuild(Node*& p){ 45                 static vector
          
            x; 46 x.clear(); 47 Travel(p,x); 48 p=Divide(x,0,x.size()); 49 } 50 Node** Insert(Node*& p,int val){ 51 if(p==null){ 52 p=newNode(val); 53 return &null; 54 } 55 p->size++,p->cover++; 56 Node** res=Insert(p->ch[val>=p->val],val); 57 if(p->isbad())res=&p; 58 return res; 59 } 60 void Erase(Node*& p,int k){ 61 p->size--; 62 int offset=p->ch[0]->size+p->exist; 63 if(p->exist&&offset==k){ 64 p->exist=false; 65 }else{ 66 if(k<=offset)Erase(p->ch[0],k); 67 else Erase(p->ch[1],k-offset); 68 } 69 } 70 public: 71 void init(){ 72 tail=mempool; 73 null=tail++; 74 null->ch[0]=null->ch[1]=null; 75 null->cover=null->size=null->exist=0; 76 root=null; 77 bc_top=0; 78 } 79 Tree(){ 80 init(); 81 } 82 void insert(int val){ 83 Node** res=Insert(root,val); 84 if(*res!=null)Rebuild(*res); 85 } 86 int rank(int val){ 87 Node* now=root; 88 int ans=1; 89 while(now!=null){ 90 if(now->val>=val)now=now->ch[0]; 91 else{ 92 ans+=now->ch[0]->size+now->exist; 93 now=now->ch[1]; 94 } 95 } 96 return ans; 97 } 98 int kth(int val){ 99 Node* now=root;100 while(now!=null){101 if(now->ch[0]->size+1==val&&now->exist)return now->val;102 if(now->ch[0]->size>=val)now=now->ch[0];103 else val-=now->ch[0]->size+now->exist,now=now->ch[1];104 }105 }106 void erase(int k){107 Erase(root,rank(k));108 if(root->size
           
            cover*alpha)Rebuild(root);109 }110 };111 }112 using namespace Scapegoat;113 Tree tree;114 int main(){115 int n,op,x;116 scanf("%d",&n);117 while(n--){118 scanf("%d%d",&op,&x);119 if(op==1)tree.insert(x);120 if(op==2)tree.erase(x);121 if(op==3)printf("%d\n",tree.rank(x));122 if(op==4)printf("%d\n",tree.kth(x));123 if(op==5)printf("%d\n",tree.kth(tree.rank(x)-1));124 if(op==6)printf("%d\n",tree.kth(tree.rank(x+1)));125 }126 return 0;127 }