#include #define biggerThan_2t 10 #define smallerThan_t 20 #define empty_root 30 #define good 40 using namespace std; template struct page { int level; bool isroot=true; dequeval; dequenext; page() {} page(bool isroot):isroot(isroot) { next.resize(0),val.resize(0); } deque::iterator search(int value) { return lower_bound(val.begin(),val.end(),value); } int find(int value) { return search(value)-val.begin(); } bool isleaf() { return next.size()==0; } int length() { return val.size(); } int nlength() { return next.size(); } void print() { cout<<"[ "; for(int i=0; i<(int)val.size(); i++) cout<0 && next[index-1]->length()>t) val[index]=next[index-1]->getLastAndDelIt(); else if(indexlength()>t) val[index]=next[index+1]->getFirstAndDelit(); else if(isroot && !isleaf() && ! specialCase){ return true; } else val.erase(val.begin()+index); } return false; } int getMostRight() { page*p=this; while(!p->isleaf()) p=p->getnLast(); return p->val[p->length()-1]; } pair>gethalf() { page*right=new page(false); page*left=new page(false); for(int i=0; ival.push_back(val[i]); else if(i>t) right->val.push_back(val[i]); } if(!isleaf()) { for(int i=0; i<=t; i++) left->next.push_back(next[i]); for(int i=t+1; inext.push_back(next[i]); } return {val[t],{left,right}}; } int getLastAndDelIt() { int last=this->getvLast(); del(last); return last; } int getFirstAndDelit() { int first=val[0]; del(first); return first; } void getFromAt(page*&from,int at) { if(at==from->length()) at=from->length()-1; add(from->val[at]); from->del(from->val[at],true); } int& getvLast() { return val[length()-1]; } page*&getnLast() { return next[nlength()-1]; } void mergeWith(page*&other) { if(other==NULL) return; for(int i=0; ilength(); i++) val.push_back(other->val[i]); if(!isleaf()) { while(!other->next.empty()) { next.push_back(other->next[0]); other->next.pop_front(); } } delete other; other=nullptr; } }; template class BTree { page*root=new page; public: void add(int value) { function*&,int)>a=[&](page*&root,int value) { int result=0; int index=good; if(root==NULL ) return good; if(!root->isleaf()) { index=root->find(value); result=a(root->next[index],value); } else root->add(value); fix(root,result,index); return checkPage(root); }; fix(root,a(root,value),-1); } void del(int value) { function*&,int)>d=[&](page*&root,int value) { if(root==NULL) return good; int result=good; int index=root->find(value); if(index>=root->length()||root->val[index]!=value && !root->isleaf()) result=d(root->next[index],value); else if(root->del(value)){ int new_value=root->next[index]->getMostRight(); fix(root,d(root,new_value),-1); root->del(value); root->add(new_value); } if(!root->isleaf()) fix(root,result,index); return checkPage(root); }; fix(root,d(root,value),-1); root->isroot=true; } bool search(int value) { function*&,int)>s=[&](page*root,int value)->int { if(root==NULL) return false; int index=root->find(value); if(indexlength() && root->val[index]==value) return value; return s(root->next[index],value); }; return s(root,value)==value; } void print() { if(!root) return; queue*>q ; q.push(root); root->level=0; int cur_level=0; while(!q.empty()) { page*p=q.front(); q.pop(); if(p->level>cur_level) { cout<level; } p->print(); if(!p->isleaf()) for(auto i : p->next) { if(i==NULL&&cout<<"NULL in print ") continue; i->level=p->level+1; q.push(i); } } } int checkPage(page*&root) { if(root->length()>2*t) return biggerThan_2t; if(!root->isroot && root->length()isroot && root->length()==0 ) return empty_root; return 0; } void fix(page*&root,int result,int index) { if(result==good) return; switch(result) { case biggerThan_2t: if(index==-1) { auto get=root->gethalf(); auto temp=root; root=new page(true); root->add(get.first); root->next.push_back(get.second.first); root->next.push_back(get.second.second); delete temp; } else { auto get=root->next[index]->gethalf(); root->add(get.first); auto temp=root->next[index]; root->next[index]=get.second.first; root->next.insert(root->next.begin()+index+1,get.second.second); delete temp; } break; case smallerThan_t: { page*&r=root->next[index]; if( (index>0 && root->next[index-1]->length()>t) || (indexlength() && root->next[index+1]->length()>t) ) r->getFromAt(root,index); else { if(index==root->length()) getAndMerge(root,root->next[index-1],r,index-1); else getAndMerge(root,r,root->next[index+1],index); } } break; case empty_root: if(root->isleaf()) return; page*temp=root->next[0]; if(root->next[1]) { page*&a=root->next[0], *&b=root->next[1]; if(!a->isleaf()) a->getnLast()->mergeWith(b->next[0]); } root->next[0]->mergeWith(root->next[1]); delete root; root=temp; break; } } void getAndMerge(page*&root,page*&first,page*&second,int index) { first->getFromAt(root,index); first->mergeWith(second); auto it=std::find(root->next.begin(),root->next.end(),nullptr); if(it!=root->next.end()) { delete root->next[it - root->next.begin()]; root->next.erase(it); } } }; int main() { BTree<2>t; vectorx; for(int i=0; i<=20; i++) x.push_back(i); for(int i=0; i<(int)x.size(); i++) t.add(x[i]),t.print(),cout<<"ddd"<

B tree