#include<iostream>usingnamespacestd;template<classK,intM>structBTreeNode{K_keys[M];BTreeNode*_subs[M+1];BTreeNode*_parent;size_t_size;BTreeNode(constK&key):_parent(NULL),_size(0){for(inti=0;i<M;++i){_keys[i]=0;}for(inti=0;i<=M;++i){_subs[i]=NULL;}_keys[_size++]=key;}~BTreeNode(){};};template<classK,intM>classBTree{public:typedefBTreeNode<K,M>Node;BTree():_root(NULL){}pair<Node*,int>Find(constK&key){if(_root==NULL){returnpair<Node*,int>(NULL,-1);}Node*prev=NULL;Node*cur=_root;while(cur){inti=0;for(;i<(int)cur->_size;){if(key>cur->_keys[i])++i;elseif(key<cur->_keys[i]){break;}elsereturnpair<Node*,int>(cur,i);}prev=cur;cur=cur->_subs[i];}returnpair<Node*,int>(prev,-1);}boolInsert(constK&key){if(_root==NULL){_root=newNode(key);returntrue;}pair<Node*,int>ret=Find(key);if(ret.second!=-1)returnfalse;Node*cur=ret.first;Node*prev=NULL;inti=cur->_size;while(i>ret.second&&key<cur->_keys[i-1]){cur->_keys[i]=cur->_keys[i-1];--i;}cur->_keys[i]=key;++cur->_size;if(cur->_size<M)returntrue;intmid=M/2;//KnewKey=key;while(1){Node*newNode=NULL;//cout<<M<<endl;while(mid<M-1){if(newNode==NULL)newNode=newNode(cur->_keys[mid+1]);elsenewNode->_keys[newNode->_size++]=cur->_keys[mid+1];cur->_keys[mid+1]=0;newNode->_subs[newNode->_size-1]=cur->_subs[mid+1];if(cur->_subs[mid+1])(cur->_subs[mid+1])->_parent=newNode;cur->_subs[++mid]=NULL;newNode->_subs[newNode->_size]=cur->_subs[mid+1];;if(cur->_subs[mid+1])(cur->_subs[mid+1])->_parent=newNode;cur->_subs[mid+1]=NULL;--cur->_size;}//cur->_subs[M/2+1]=newNode;prev=cur->_parent;if(prev==NULL){prev=newNode(cur->_keys[M/2]);cur->_keys[M/2]=0;prev->_subs[0]=cur;prev->_subs[1]=newNode;cur->_parent=prev;newNode->_parent=prev;--cur->_size;_root=prev;returntrue;}i=prev->_size-1;while(i>=0&&prev->_keys[i]>cur->_keys[M/2]){prev->_keys[i+1]=prev->_keys[i];prev->_subs[i+2]=prev->_subs[i+1];--i;}prev->_keys[i+1]=cur->_keys[M/2];prev->_subs[i+2]=newNode;newNode->_parent=prev;cur->_subs[M/2+1]=NULL;cur->_keys[M/2]=0;++prev->_size;--cur->_size;cur=prev;prev=cur->_parent;mid=M/2;if(cur->_size<M)returntrue;}returntrue;}boolRemove(constK&key){if(_root==NULL)returnfalse;pair<Node*,int>ret=Find(key);if(ret.second==-1)returnfalse;Node*cur=ret.first;Node*prev=NULL;intindex=ret.second;intpindex=0;KnewKey=key;while(cur){prev=cur->_parent;//获取父节点if(cur->_subs[index]==NULL)//叶子节点{if(cur->_size>=M/2){//节点key数量>=M/2，直接删除for(inti=index;i<(int)cur->_size;++i){cur->_keys[i]=cur->_keys[i+1];}cur->_size--;returntrue;}if(prev==NULL)//父为空只有一个节点{if(cur->_size==1)//只有一个key删除后释放节点_root制空{_root=NULL;deletecur;}else//否则删除key移动其他{for(inti=index;i<(int)cur->_size;++i){cur->_keys[i]=cur->_keys[i+1];}}returntrue;}else//父不为空{intdev=0;for(;dev<=(int)prev->_size;++dev)//判断删除操作的节点在父节点的关键字的位置(0--m-1){if(prev->_subs[dev]==cur)break;}if(dev!=0&&(int)prev->_subs[dev-1]->_size>M/2)//cur不为prev最左sub找左边替代{Node*tmp=prev->_subs[dev-1];cur->_keys[index]=prev->_keys[dev-1];prev->_keys[dev-1]=tmp->_keys[tmp->_size-1];tmp->_keys[tmp->_size-1]=0;tmp->_size--;returntrue;}if(dev!=(int)prev->_size&&(int)(prev->_subs[dev+1]->_size)>M/2)//不为最右找右替代{Node*tmp=prev->_subs[dev+1];cur->_keys[index]=prev->_keys[dev];prev->_keys[dev]=tmp->_keys[0];tmp->_keys[tmp->_size-1]=0;for(inti=0;i<(int)tmp->_size;++i){tmp->_keys[i]=tmp->_keys[i+1];}tmp->_size--;returntrue;}for(inti=index;i<(int)cur->_size;++i){cur->_keys[i]=cur->_keys[i+1];}cur->_size--;//需要合并Node*ppNode=NULL;while(1){if(dev!=0){ppNode=prev->_parent;Node*sub=prev->_subs[dev-1];sub->_keys[sub->_size++]=prev->_keys[dev-1];for(inti=0;i<(int)cur->_size;++i){sub->_keys[sub->_size++]=cur->_keys[i];}for(inti=dev-1;i<(int)prev->_size;++i){prev->_keys[i]=prev->_keys[i+1];prev->_subs[i+1]=prev->_subs[i+2];}if(sub->_subs[0]==NULL){deletecur;}else{sub->_subs[sub->_size]=cur;cur->_parent=sub;}if((int)prev->_size-->1)returntrue;else{if(ppNode==NULL){_root=sub;sub->_parent=NULL;deleteprev;returntrue;}else{sub->_parent=prev->_parent;memcpy(prev,sub,sizeof(Node));deletesub;cur=prev;prev=ppNode;for(dev=0;dev<=(int)prev->_size;++dev)//判断删除操作的节点在父节点的关键字的位置(0--m-1){if(prev->_subs[dev]==cur)break;}returntrue;}}}else{ppNode=prev->_parent;Node*sub=prev->_subs[dev+1];cur->_keys[cur->_size++]=prev->_keys[dev];for(inti=0;i<(int)sub->_size;++i){cur->_keys[cur->_size++]=sub->_keys[i];}for(inti=dev;i<(int)prev->_size;++i){prev->_keys[i]=prev->_keys[i+1];prev->_subs[i+1]=prev->_subs[i+2];}if(cur->_subs[0]==NULL){deletesub;}else{cur->_subs[cur->_size]=sub;sub->_parent=cur;}if((int)prev->_size-->1)returntrue;else{if(ppNode==NULL){_root=cur;cur->_parent=NULL;deleteprev;returntrue;}else{cur->_parent=prev->_parent;memcpy(prev,cur,sizeof(Node));deletecur;cur=prev;prev=ppNode;for(dev=0;dev<=(int)prev->_size;++dev)//判断删除操作的节点在父节点的关键字的位置(0--m-1){if(prev->_subs[dev]==cur)break;}returntrue;}}}}}}else//不为叶子{if(cur->_subs[index+1]->_size>0)//找右孩子最小替代删除{Node*sub=cur->_subs[index+1];while(sub->_subs[0]){sub=sub->_subs[0];}cur->_keys[index]=sub->_keys[0];cur=sub;index=0;}elseif(cur->_subs[index]->_size>0)//找左孩子最大替代{Node*sub=cur->_subs[index];intsize=sub->_size;while(sub->_subs[0]){size=sub->_size;sub=sub->_subs[size];}cur->_keys[index]=sub->_keys[size-1];cur=sub;index=(int)sub->_size;}else{deletecur->_subs[index];deletecur->_subs[index+1];cur->_subs[index]=NULL;cur->_subs[index]=NULL;}}}returntrue;}voidTraverse(){_Traverse(_root);cout<<endl;}private:void_Traverse(Node*root){if(root==NULL)return;inti=0;for(;i<(int)root->_size;++i){if(i==0)_Traverse(root->_subs[0]);cout<<root->_keys[i]<<"";_Traverse(root->_subs[i+1]);}}Node*_root;};