#include "Vector.h"  //这是之前写的向量结构，在我的github上，自己写的接口更适合这里实现B树，当然也可以用STL里的。

 #include <cstdio>

 using namespace std;

 #ifndef B__tree_h

 #define B__tree_h

 #define Posi(T) BTrNode<T>*  //B-树节点位置

 template <typename T> struct BTrNode{

     Posi(T) par;

     Vector<T> key;// 存放关键字的向量

     Vector< Posi(T) > child;  //存放孩子指针的向量，比key多1

     //2种构造函数，BTrNode只能作为根节点创建

     BTrNode(){ par=NULL; child.push_back(NULL);}

     BTrNode( T key, Posi(T) lc=NULL, Posi(T) rc=NULL ){

         par=NULL;

         key.insert(,key);

         child.insert(,lc);  child.insert(,rc);

         if(lc) lc->par=this;  if(rc) rc->par=this;

     }

 };

 #endif /* B__tree_h */

 #include "Vector.h"

 #include "B- tree.h"

 #include <cstdio>

 using namespace std;

 template <typename T>

 class BTree {

 protected:

     int _size,_order;  //关键码总数，阶次，至少为3

     Posi(T) _root;

     Posi(T) hot;// BTree::search()最后访问的非空节点位置，相当于浮标

     //core section

     void solveOverFlow(Posi(T) );  //处理上溢的分裂

     void solveUnderFlow(Posi(T) );//处理下溢的合并、旋转

 public:

     BTree(int assign=): _order(assign),_size(){ _root=new BTrNode<T>();}//默认起码3阶

     ~BTree(){ if(_root) release(_root);}

     Posi(T) search(const T & value);

     bool insert(const T & value);

     bool remove(const T & value);

     int const size() {return _size; }   //keep _size can not be changed in external

     int const order(){return _order; }  //ditto

     Posi(T)& root(){ return _root;}

     bool empty() {return !_root;}

 };

 template <typename T>

 Posi(T) BTree<T>::search(const T & e) {

     Posi(T) cur = _root;  hot = NULL;  //从根开始

     while ( cur ) {

         Rank r = cur -> key.search(e);  //顺序查找

         if(r >=  &&  e == cur -> key[r]) return cur; //如果成功则返回当前引用

         hot = cur; cur = cur -> child[r+];//更新hot,转到下一层子树，把根载入内存

     }//走到这里时 !cur为真，说明抵达外部节点

     return NULL;

 }

 template <typename T>

 bool BTree<T>::insert(const T & e){

     Posi(T)  t = search(e);//这里调用的是B树的search接口

     if(t) return false;  //如果已经存在就什么也不做

     Rank r = hot->key.search(e);//在hot中确定插入位置,hot指向的是一个叶节点。search in vector

     hot->key.insert(r+,e);//把目标关键码放在向量对应位置

     hot->child.insert(r+,NULL);//创建一个空子树指针,视作右侧分支

     _size++;

     solveOverFlow(hot);//如果发生overflow要进行一次分裂

     return true;

 }

 template <typename T>

 void BTree<T>::solveOverFlow(Posi(T) current){

     if(_order >= current->child.size()) return ;  //判断当前节点是否上溢，无则返回

     Rank mid=_order/; //作为枢纽 此时有这样的关系： _order = key.size() = child.size()-1

     Posi(T) right=new BTrNode<T>(); // 新节点已经有一个空孩子

     for (int i=; i<_order-mid-; i++) {//当前右侧的_order-s-1个孩子和关键码分裂为右侧节点right(以下简称r)

         right->child.insert(i, current->child.remove(mid+));

         right->key.insert(i,current->key.remove(mid+));

     }

     right->child[_order-mid-] =current->child.remove(mid+);//移动当前最靠右的孩子

     if(right->child[])//如果right的孩子非空

         for(int i=;i< _order-mid;i++)

             right->child[i]->parent=right;  //令他们的父节点统一指向自己,因为下面的都是外部节点了

     Posi(T) p=current->par;

     if(!p) {  //这时候cur已经是根了，就执行对根分裂的步骤

         _root=p=new BTrNode<T>();

         p->child[]=current;

         current->par=p;

     }

     Rank r=+p->key.search(current->key[]);//r获取到p中 指向u的指针的序号

     p->key.insert(r,current->key.remove(mid));//pivot关键码上升

     p->child.insert(r+,right);

     right->par=p;        //新节点r与父节点p互联

     solveOverFlow(p);//视角上升一层，有必要就继续分裂，最多递归O（logn）层，判断放在递归基里

 }

 template <typename T>

 bool BTree<T>::remove(const T & e){

     Posi(T) target = search(e);

     if(!target) return false;// 如果不存在，显然删除失败

     Rank rk_e = target -> key.search(e); //在目标节点中获取到e的下标

     if( target -> child[] ) { //确保不是叶子，那e的后继一定在某片叶子里

         Posi(T) right = target -> child[rk_e+];//在右子树中一直向左即可

         while ( right -> child[] )

             right = right -> child[];//找出e的后继

         target -> key[rk_e] = right -> key[];

         target = right;

         rk_e = ;// 交换target和e后继的位置

     }//此时v到了底层，第r个元素就是要被删除的

     target -> key.remove(rk_e);   //删除e

     target -> child.remove(rk_e+); //删除其中一个外部节点

     _size--;   //更新规模

     solveUnderFlow(target);//如果有必要就旋转 or 合并

     return true;

 }

 template <typename T>

 void BTree<T>::solveUnderFlow(Posi(T) v){

     if( (_order +  )>>  <= v->child.size()) return;   //当前节点没有发生下溢

     Posi(T) p = v -> par;

     if (!p) {  //到达根节点

         if (!v->key.size() && v -> child[]) { //如果v已经不含有关键码，但有唯一的非空child时

             _root = v -> child[]; _root -> par = NULL;//这个节点被跳过

             v -> child[] = NULL; delete v;  //然后销毁

         }//树高-1

         return;

     }

     Rank r=;

     while (p->child[r] !=v) r++; //确定v是p的第几个孩子，记作r

     //COND 1 向左借元素

     if ( r > ) {  //保证v不是p的第一个孩子

         Posi(T) ls = p -> child[r-] ;//那左边一定有元素，是为左兄弟（left sibling），简称ls

         if( (_order + )>>  < ls->child.size() ){//如果这个兄弟家有余粮的话

             v -> key.insert(  , p -> key[r-] ); //v的父亲借出一个关键码作为v的min

             p -> key[r-] = ls->key.remove( ls->key.size()- ); //ls的最大值补充给p

             v -> child.insert( , ls->child.remove(ls->child.size() -  ) );

             if( v->child[] ) v->child[]->par =v;//最后两步调整对应的指针

             return ; //右旋完成

         }

     } //至此左兄弟或者为空，或者不能再借了

     // COND 2 向右借元素

     if (p -> child.size() - > r ) {  //如果v并非p的最后一个孩子

         Posi(T) rs = p->child[r+]; //右边一定有元素

         if ((_order + )>>  < rs->child.size()) {

             v -> key.insert( v->key.size() , p -> key[r] );

             p -> key[r] = rs->key.remove();

             v -> child.insert( v->child.size() , rs->child.remove() );

             if( v->child[v->child.size()-] ) //v->child.size()-1是末尾下标

                 v->child[v->child.size()-]->par =v;//最后两步调整对应的指针

             return; //左旋完成

         }

     }//至此右兄弟或者为空，或者不能再借了

     // COND 3 需要合并

     if ( < r) {  //与左兄弟合并

         Posi(T) ls = p -> child[r-];

         ls->key.insert( ls -> key.size(), p -> key.remove(r-) );

         // p的第r-1个关键码转入ls

         ls->child.insert( ls -> child.size(),v -> child.remove());

         if( ls->child[ ls->child.size() - ]) //把v最左边的孩子（min）给ls做最右侧孩子(max)

             ls->child[ ls->child.size() - ] -> par = ls;

         while (!v -> key.empty() ){ //若v中元素仍非空，就把剩余的依次转入ls

             ls -> key.insert( ls -> key.size(), v->key.remove());

             ls -> child.insert( ls -> child.size(), v->child.remove());

             if( ls->child[ ls->child.size() - ] )

                 ls->child[ ls->child.size() - ] -> par =ls;

         }

         delete v; //合并后该局部的根已经空了，所以不妨将它删除，用合并后的节点作为新的根即可，下同

     }

     else{//与右兄弟合并

         Posi(T) rs = p -> child[r+];

         rs->key.insert(  , p -> key.remove(r) );

         p->child.remove(r); //以上两步将p的第r个关键码转入rs

         rs->child.insert( ,v -> child.remove(v -> child.size() - ) );

         if(rs -> child[] )

             rs -> child[] -> par = rs;

         while (!v -> key.empty()) {    //若v中元素仍非空，就把剩余的依次转入rs

             rs -> key.insert( , v->key.remove(v -> key.size()- ) );

             rs -> child.insert( , v->child.remove( v -> child.size() - ) );

             if( rs ->child[] )

                rs->child[] -> par =rs;

         }

         delete v;

     }

     solveUnderFlow( p ); //继续检查上一层

     return;

 }