Loading [MathJax]/extensions/TeX/newcommand.js
\newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}}

2015年2月18日 星期三

[ korea tree ] 朝鮮樹

某天albus YY出來了一個沒有旋轉操作的平衡樹,由於albus的真名(华中科技大学附属中学 金正中)聽起來很像朝鮮主席,所以就叫朝鮮樹了!

朝鮮樹是一種不需旋轉的 自平衡二元搜尋樹,利用當深度大於max_deep(通常取sqrt(N))時暴力重建的方式讓平均時間為\ord{N*sqrt(N)},是一種很糟糕的平衡樹,但是我們還是要理解他,因為這樣暴力重建的概念會在其他樹上用到。
若題目的要求數據量<=500000時可以使用

所有操作都與本篇其他樹差不多只多了個rebuild函數,它會暴力將整顆樹重建成深度logN的平衡樹

對於重建的部分則使用了拍扁重建法,將樹先拍扁成鍊表後重建,只需要花費\ord 1的空間複雜度

以下提供模板:
#ifndef KOREA_TREE
#define KOREA_TREE
template<typename T>
class korea_tree{
private:
struct node{
node *ch[2];
T data;
int s;
node(const T&d):data(d),s(1){}
node():s(0){ch[0]=ch[1]=this;}
}*nil,*root,t;
int max_deep,d;
void insert(node *&o,const T&data){
if(!o->s){
o=new node(data);
o->ch[0]=o->ch[1]=nil;
}else o->s++,d++,insert(o->ch[o->data<data],data);
}
inline void success_erase(node *&o){
node *t=o;
o=o->ch[0]->s?o->ch[0]:o->ch[1];
delete t;
}
bool erase(node *&o,const T&data){
if(!o->s)return 0;
if(o->data==data){
if(!o->ch[0]->s||!o->ch[1]->s)success_erase(o);
else{
o->s--;
node **t=&o->ch[1];
for(;(*t)->ch[0]->s;t=&(*t)->ch[0])(*t)->s--;
o->data=(*t)->data;
success_erase(*t);
}return 1;
}else if(erase(o->ch[o->data<data],data)){
o->s--;return 1;
}else return 0;
}
node *flatten(node *x,node *y){
if(!x->s)return y;
x->ch[1]=flatten(x->ch[1],y);
return flatten(x->ch[0],x);
}
node *build(node *x,int n){
if(!n){
x->ch[0]=nil;
return x;
}
node *y=build(x,n/2);
node *z=build(y->ch[1],n-1-n/2);
y->ch[1]=z->ch[0];
z->ch[0]=y;
y->s=y->ch[0]->s+y->ch[1]->s+1;
return z;
}
void clear(node *&p){
if(p->s)clear(p->ch[0]),clear(p->ch[1]),delete p;
}
public:
korea_tree(int d=1000):nil(new node),root(nil),max_deep(d){}
~korea_tree(){clear(root),delete nil;}
inline void clear(){clear(root),root=nil;}
inline void insert(const T&data){
d=0;
insert(root,data);
if(d>=max_deep)rebuild();
}
inline bool erase(const T&data){
return erase(root,data);
}
inline void rebuild(){
root=build(flatten(root,&t),root->s)->ch[0];
}
inline bool find(const T&data){
node *o=root;
while(o->s&&o->data!=data)o=o->ch[o->data<data];
return o->s;
}
inline int rank(const T&data){
int cnt=0;
for(node *o=root;o->s;)
if(o->data<data)cnt+=o->ch[0]->s+1,o=o->ch[1];
else o=o->ch[0];
return cnt;
}
inline const T&kth(int k){
for(node *o=root;;)
if(k<=o->ch[0]->s)o=o->ch[0];
else if(k==o->ch[0]->s+1)return o->data;
else k-=o->ch[0]->s+1,o=o->ch[1];
}
inline const T&operator[](int k){
return kth(k);
}
inline const T&preorder(const T&data){
node *x=root,*y=0;
while(x->s)
if(x->data<data)y=x,x=x->ch[1];
else x=x->ch[0];
if(y)return y->data;
return data;
}
inline const T&successor(const T&data){
node *x=root,*y=0;
while(x->s)
if(data<x->data)y=x,x=x->ch[0];
else x=x->ch[1];
if(y)return y->data;
return data;
}
inline int size(){return root->s;}
};
#endif
view raw korea_tree.cpp hosted with ❤ by GitHub

沒有留言:

張貼留言