// Deletion operation on a B+ tree in C++#include<climits>#include<fstream>#include<iostream>#include<sstream>usingnamespacestd;intMAX=3;classBPTree;classNode{boolIS_LEAF;int*key,size;Node**ptr;friendclassBPTree;public:Node();};classBPTree{Node*root;voidinsertInternal(int,Node*,Node*);voidremoveInternal(int,Node*,Node*);Node*findParent(Node*,Node*);public:BPTree();voidsearch(int);voidinsert(int);voidremove(int);voiddisplay(Node*);Node*getRoot();};Node::Node(){key=newint[MAX];ptr=newNode*[MAX+1];}BPTree::BPTree(){root=NULL;}voidBPTree::insert(intx){if(root==NULL){root=newNode;root->key[0]=x;root->IS_LEAF=true;root->size=1;}else{Node*cursor=root;Node*parent;while(!cursor->IS_LEAF){parent=cursor;for(inti=0;i<cursor->size;i++){if(x<cursor->key[i]){cursor=cursor->ptr[i];break;}if(i==cursor->size-1){cursor=cursor->ptr[i+1];break;}}}if(cursor->size<MAX){inti=0;while(x>cursor->key[i]&&i<cursor->size)i++;for(intj=cursor->size;j>i;j--){cursor->key[j]=cursor->key[j-1];}cursor->key[i]=x;cursor->size++;cursor->ptr[cursor->size]=cursor->ptr[cursor->size-1];cursor->ptr[cursor->size-1]=NULL;}else{Node*newLeaf=newNode;intvirtualNode[MAX+1];for(inti=0;i<MAX;i++){virtualNode[i]=cursor->key[i];}inti=0,j;while(x>virtualNode[i]&&i<MAX)i++;for(intj=MAX+1;j>i;j--){virtualNode[j]=virtualNode[j-1];}virtualNode[i]=x;newLeaf->IS_LEAF=true;cursor->size=(MAX+1)/2;newLeaf->size=MAX+1-(MAX+1)/2;cursor->ptr[cursor->size]=newLeaf;newLeaf->ptr[newLeaf->size]=cursor->ptr[MAX];cursor->ptr[MAX]=NULL;for(i=0;i<cursor->size;i++){cursor->key[i]=virtualNode[i];}for(i=0,j=cursor->size;i<newLeaf->size;i++,j++){newLeaf->key[i]=virtualNode[j];}if(cursor==root){Node*newRoot=newNode;newRoot->key[0]=newLeaf->key[0];newRoot->ptr[0]=cursor;newRoot->ptr[1]=newLeaf;newRoot->IS_LEAF=false;newRoot->size=1;root=newRoot;}else{insertInternal(newLeaf->key[0],parent,newLeaf);}}}}voidBPTree::insertInternal(intx,Node*cursor,Node*child){if(cursor->size<MAX){inti=0;while(x>cursor->key[i]&&i<cursor->size)i++;for(intj=cursor->size;j>i;j--){cursor->key[j]=cursor->key[j-1];}for(intj=cursor->size+1;j>i+1;j--){cursor->ptr[j]=cursor->ptr[j-1];}cursor->key[i]=x;cursor->size++;cursor->ptr[i+1]=child;}else{Node*newInternal=newNode;intvirtualKey[MAX+1];Node*virtualPtr[MAX+2];for(inti=0;i<MAX;i++){virtualKey[i]=cursor->key[i];}for(inti=0;i<MAX+1;i++){virtualPtr[i]=cursor->ptr[i];}inti=0,j;while(x>virtualKey[i]&&i<MAX)i++;for(intj=MAX+1;j>i;j--){virtualKey[j]=virtualKey[j-1];}virtualKey[i]=x;for(intj=MAX+2;j>i+1;j--){virtualPtr[j]=virtualPtr[j-1];}virtualPtr[i+1]=child;newInternal->IS_LEAF=false;cursor->size=(MAX+1)/2;newInternal->size=MAX-(MAX+1)/2;for(i=0,j=cursor->size+1;i<newInternal->size;i++,j++){newInternal->key[i]=virtualKey[j];}for(i=0,j=cursor->size+1;i<newInternal->size+1;i++,j++){newInternal->ptr[i]=virtualPtr[j];}if(cursor==root){Node*newRoot=newNode;newRoot->key[0]=cursor->key[cursor->size];newRoot->ptr[0]=cursor;newRoot->ptr[1]=newInternal;newRoot->IS_LEAF=false;newRoot->size=1;root=newRoot;}else{insertInternal(cursor->key[cursor->size],findParent(root,cursor),newInternal);}}}Node*BPTree::findParent(Node*cursor,Node*child){Node*parent;if(cursor->IS_LEAF||(cursor->ptr[0])->IS_LEAF){returnNULL;}for(inti=0;i<cursor->size+1;i++){if(cursor->ptr[i]==child){parent=cursor;returnparent;}else{parent=findParent(cursor->ptr[i],child);if(parent!=NULL)returnparent;}}returnparent;}voidBPTree::remove(intx){if(root==NULL){cout<<"Tree empty\n";}else{Node*cursor=root;Node*parent;intleftSibling,rightSibling;while(!cursor->IS_LEAF){for(inti=0;i<cursor->size;i++){parent=cursor;leftSibling=i-1;rightSibling=i+1;if(x<cursor->key[i]){cursor=cursor->ptr[i];break;}if(i==cursor->size-1){leftSibling=i;rightSibling=i+2;cursor=cursor->ptr[i+1];break;}}}boolfound=false;intpos;for(pos=0;pos<cursor->size;pos++){if(cursor->key[pos]==x){found=true;break;}}if(!found){cout<<"Not found\n";return;}for(inti=pos;i<cursor->size;i++){cursor->key[i]=cursor->key[i+1];}cursor->size--;if(cursor==root){for(inti=0;i<MAX+1;i++){cursor->ptr[i]=NULL;}if(cursor->size==0){cout<<"Tree died\n";delete[]cursor->key;delete[]cursor->ptr;deletecursor;root=NULL;}return;}cursor->ptr[cursor->size]=cursor->ptr[cursor->size+1];cursor->ptr[cursor->size+1]=NULL;if(cursor->size>=(MAX+1)/2){return;}if(leftSibling>=0){Node*leftNode=parent->ptr[leftSibling];if(leftNode->size>=(MAX+1)/2+1){for(inti=cursor->size;i>0;i--){cursor->key[i]=cursor->key[i-1];}cursor->size++;cursor->ptr[cursor->size]=cursor->ptr[cursor->size-1];cursor->ptr[cursor->size-1]=NULL;cursor->key[0]=leftNode->key[leftNode->size-1];leftNode->size--;leftNode->ptr[leftNode->size]=cursor;leftNode->ptr[leftNode->size+1]=NULL;parent->key[leftSibling]=cursor->key[0];return;}}if(rightSibling<=parent->size){Node*rightNode=parent->ptr[rightSibling];if(rightNode->size>=(MAX+1)/2+1){cursor->size++;cursor->ptr[cursor->size]=cursor->ptr[cursor->size-1];cursor->ptr[cursor->size-1]=NULL;cursor->key[cursor->size-1]=rightNode->key[0];rightNode->size--;rightNode->ptr[rightNode->size]=rightNode->ptr[rightNode->size+1];rightNode->ptr[rightNode->size+1]=NULL;for(inti=0;i<rightNode->size;i++){rightNode->key[i]=rightNode->key[i+1];}parent->key[rightSibling-1]=rightNode->key[0];return;}}if(leftSibling>=0){Node*leftNode=parent->ptr[leftSibling];for(inti=leftNode->size,j=0;j<cursor->size;i++,j++){leftNode->key[i]=cursor->key[j];}leftNode->ptr[leftNode->size]=NULL;leftNode->size+=cursor->size;leftNode->ptr[leftNode->size]=cursor->ptr[cursor->size];removeInternal(parent->key[leftSibling],parent,cursor);delete[]cursor->key;delete[]cursor->ptr;deletecursor;}elseif(rightSibling<=parent->size){Node*rightNode=parent->ptr[rightSibling];for(inti=cursor->size,j=0;j<rightNode->size;i++,j++){cursor->key[i]=rightNode->key[j];}cursor->ptr[cursor->size]=NULL;cursor->size+=rightNode->size;cursor->ptr[cursor->size]=rightNode->ptr[rightNode->size];cout<<"Merging two leaf nodes\n";removeInternal(parent->key[rightSibling-1],parent,rightNode);delete[]rightNode->key;delete[]rightNode->ptr;deleterightNode;}}}voidBPTree::removeInternal(intx,Node*cursor,Node*child){if(cursor==root){if(cursor->size==1){if(cursor->ptr[1]==child){delete[]child->key;delete[]child->ptr;deletechild;root=cursor->ptr[0];delete[]cursor->key;delete[]cursor->ptr;deletecursor;cout<<"Changed root node\n";return;}elseif(cursor->ptr[0]==child){delete[]child->key;delete[]child->ptr;deletechild;root=cursor->ptr[1];delete[]cursor->key;delete[]cursor->ptr;deletecursor;cout<<"Changed root node\n";return;}}}intpos;for(pos=0;pos<cursor->size;pos++){if(cursor->key[pos]==x){break;}}for(inti=pos;i<cursor->size;i++){cursor->key[i]=cursor->key[i+1];}for(pos=0;pos<cursor->size+1;pos++){if(cursor->ptr[pos]==child){break;}}for(inti=pos;i<cursor->size+1;i++){cursor->ptr[i]=cursor->ptr[i+1];}cursor->size--;if(cursor->size>=(MAX+1)/2-1){return;}if(cursor==root)return;Node*parent=findParent(root,cursor);intleftSibling,rightSibling;for(pos=0;pos<parent->size+1;pos++){if(parent->ptr[pos]==cursor){leftSibling=pos-1;rightSibling=pos+1;break;}}if(leftSibling>=0){Node*leftNode=parent->ptr[leftSibling];if(leftNode->size>=(MAX+1)/2){for(inti=cursor->size;i>0;i--){cursor->key[i]=cursor->key[i-1];}cursor->key[0]=parent->key[leftSibling];parent->key[leftSibling]=leftNode->key[leftNode->size-1];for(inti=cursor->size+1;i>0;i--){cursor->ptr[i]=cursor->ptr[i-1];}cursor->ptr[0]=leftNode->ptr[leftNode->size];cursor->size++;leftNode->size--;return;}}if(rightSibling<=parent->size){Node*rightNode=parent->ptr[rightSibling];if(rightNode->size>=(MAX+1)/2){cursor->key[cursor->size]=parent->key[pos];parent->key[pos]=rightNode->key[0];for(inti=0;i<rightNode->size-1;i++){rightNode->key[i]=rightNode->key[i+1];}cursor->ptr[cursor->size+1]=rightNode->ptr[0];for(inti=0;i<rightNode->size;++i){rightNode->ptr[i]=rightNode->ptr[i+1];}cursor->size++;rightNode->size--;return;}}if(leftSibling>=0){Node*leftNode=parent->ptr[leftSibling];leftNode->key[leftNode->size]=parent->key[leftSibling];for(inti=leftNode->size+1,j=0;j<cursor->size;j++){leftNode->key[i]=cursor->key[j];}for(inti=leftNode->size+1,j=0;j<cursor->size+1;j++){leftNode->ptr[i]=cursor->ptr[j];cursor->ptr[j]=NULL;}leftNode->size+=cursor->size+1;cursor->size=0;removeInternal(parent->key[leftSibling],parent,cursor);}elseif(rightSibling<=parent->size){Node*rightNode=parent->ptr[rightSibling];cursor->key[cursor->size]=parent->key[rightSibling-1];for(inti=cursor->size+1,j=0;j<rightNode->size;j++){cursor->key[i]=rightNode->key[j];}for(inti=cursor->size+1,j=0;j<rightNode->size+1;j++){cursor->ptr[i]=rightNode->ptr[j];rightNode->ptr[j]=NULL;}cursor->size+=rightNode->size+1;rightNode->size=0;removeInternal(parent->key[rightSibling-1],parent,rightNode);}}voidBPTree::display(Node*cursor){if(cursor!=NULL){for(inti=0;i<cursor->size;i++){cout<<cursor->key[i]<<" ";}cout<<"\n";if(!cursor->IS_LEAF){for(inti=0;i<cursor->size+1;i++){display(cursor->ptr[i]);}}}}Node*BPTree::getRoot(){returnroot;}intmain(){BPTreenode;node.insert(5);node.insert(15);node.insert(25);node.insert(35);node.insert(45);node.display(node.getRoot());node.remove(15);node.display(node.getRoot());}