替罪羊树
一 定义
替罪羊树是计算机科学中，一种基于部分重建的自平衡二叉搜索树。在替罪羊树上，插入或删除节点的平摊最坏时间复杂度是O(log n)，搜索节点的最坏时间复杂度是O(log n)
（非常暴力，一言不合拍扁重建）
二 思路
插入
和普通平衡树没啥区别...
void insert(node* &now,int x) { if(now==null) { now=new node; now->val=x; now->size=1; now->del=false; now->l=now->r=null; return ; } ++now->size; if(x<=now->val) insert(now->l,x); else insert(now->r,x); if(now->bad()) rebuild(now); return ; }
删除
替罪羊树的删除不是真正意义上的删除，而是给这个节点打标记，在重构时不将它加入树中。
void erase(node *now,int rk) { if(!now->del && rk==now->l->size+1) { now->del=1; --now->size; return; } --now->size; if(rk<=now->l->size+!now->del) erase(now->l,rk); else erase(now->r,rk-now->l->size-!now->del); }
判断重建
定义一个平衡因子alpha，如果左右子树大小大于整棵树的大小*alpha，就将这棵子树拍扁重建
struct node { node* l; node* r; int val; int size; bool del; bool bad() //判断是否需要重建 { if(l->size>size*alpha+5||r->size>size*alpha+5) return true; else return false; } void push_up() { size=l->size+r->size+!del; return ; } }; void dfs(vector<node*> &v,node* now) { if(now==null) return ; dfs(v,now->l); if(!now->del) v.push_back(now); dfs(v,now->r); if(now->del) delete now; return ; } node* build(vector<node*> &v,int l,int r) { if(l>=r) return null; int mid=(l+r)>>1; node* now=v[mid]; now->l=build(v,l,mid); now->r=build(v,mid+1,r); now->push_up(); return now; } void rebuild(node* &now) { vector<node*> v; dfs(v,now); now=build(v,0,v.size()); return ; }
（其实还应该判断已经删除个数是否大于整棵树的一半，如果是，就将这棵子树拍扁重建（然而我忘写了...））
查找某排名的数
int kth(node* now,int x) { while(now!=null) { if(now->l->size+1==x&&!now->del) return now->val; if(now->l->size>=x) now=now->l; else { x-=now->l->size+!now->del; now=now->r; } } }
查找某数的排名
int rank(node* now,int x) { int ans=1; while(now!=null) { if(now->val>=x) now=now->l; else { ans=ans+now->l->size+!now->del; now=now->r; } } return ans; }
查找前驱
kth(root,rank(root,x)-1)
查找后继
kth(root,rank(root,x+1))
lg 3369
#include<algorithm> #include<iostream> #include<cstring> #include<vector> using namespace std; const double alpha=0.7; struct node { node* l; node* r; int val; int size; bool del; bool bad() { if(l->size>size*alpha+5||r->size>size*alpha+5) return true; else return false; } void push_up() { size=l->size+r->size+!del; return ; } }; node* null; node* root; void dfs(vector<node*> &v,node* now) { if(now==null) return ; dfs(v,now->l); if(!now->del) v.push_back(now); dfs(v,now->r); if(now->del) delete now; return ; } node* build(vector<node*> &v,int l,int r) { if(l>=r) return null; int mid=(l+r)>>1; node* now=v[mid]; now->l=build(v,l,mid); now->r=build(v,mid+1,r); now->push_up(); return now; } void rebuild(node* &now) { vector<node*> v; dfs(v,now); now=build(v,0,v.size()); return ; } void insert(node* &now,int x) { if(now==null) { now=new node; now->val=x; now->size=1; now->del=false; now->l=now->r=null; return ; } ++now->size; if(x<=now->val) insert(now->l,x); else insert(now->r,x); if(now->bad()) rebuild(now); return ; } void erase(node *now,int rk) { if(!now->del && rk==now->l->size+1) { now->del=1; --now->size; return; } --now->size; if(rk<=now->l->size+!now->del) erase(now->l,rk); else erase(now->r,rk-now->l->size-!now->del); } int rank(node* now,int x) { int ans=1; while(now!=null) { if(now->val>=x) now=now->l; else { ans=ans+now->l->size+!now->del; now=now->r; } } return ans; } int kth(node* now,int x) { while(now!=null) { if(now->l->size+1==x&&!now->del) return now->val; if(now->l->size>=x) now=now->l; else { x-=now->l->size+!now->del; now=now->r; } } } int main() { ios::sync_with_stdio(false); null=new node; root=null; int n; cin>>n; for(int i=1; i<=n; i++) { int opt,x; cin>>opt>>x; switch(opt) { case 1: insert(root,x); break; case 2: erase(root,rank(root,x)); break; case 3: cout<<rank(root,x)<<endl; break; case 4: cout<<kth(root,x)<<endl; break; case 5: cout<<kth(root,rank(root,x)-1)<<endl; break; default: cout<<kth(root,rank(root,x+1))<<endl; } } return 0; }