一棵M阶(M>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：

1. 根节点至少有两个孩子

2. 每个非根节点有[ ,M]个孩子

3. 每个非根节点有[ -1,M-1]个关键字，并且以升序排列

4. key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间

5. 所有的叶子节点都在同一层

ps： 是向上取整

#pragmaoncetemplate<classK,intM=3>structBTreeNode{K_keys[M];//关键字数组BTreeNode<K,M>*_subs[M+1];//孩子数组size_t_size;//关键字的个数BTreeNode<K,M>*_parent;//父亲BTreeNode():_size(0),_parent(NULL){for(size_ti=0;i<M+1;++i){_subs[i]=NULL;}}};template<classK,classV>structPair{K_first;V_second;Pair(constK&k=K(),constV&v=V()):_first(k),_second(v){}};template<classK,intM=3>classBTree{typedefBTreeNode<K,M>Node;public:BTree():_root(NULL){}Pair<Node*,int>Find(constK&key){Node*parent=NULL;Node*cur=_root;while(cur){inti=0;while(i<cur->_size&&cur->_keys[i]<key){++i;}if(cur->_keys[i]==key){returnPair<Node*,int>(cur,i);}parent=cur;cur=cur->_subs[i];}returnPair<Node*,int>(parent,-1);}boolInsert(constK&key){if(_root==NULL){_root=newNode;_root->_keys[0]=key;++_root->_size;returntrue;}Pair<Node*,int>ret=Find(key);if(ret._second!=-1){returnfalse;}Kk=key;Node*cur=ret._first;Node*sub=NULL;//在cur节点插入一个kwhile(1){_InsertKey(cur,k,sub);if(cur->_size<M){returntrue;}//分裂intboundary=M/2;Node*tmp=newNode;size_tindex=0;size_tsize=cur->_size;//拷贝keyfor(inti=boundary+1;i<size;++i){tmp->_keys[index++]=cur->_keys[i];tmp->_size++;cur->_size--;}//拷贝子节点index=0;for(inti=boundary+1;i<=size;++i){tmp->_subs[index]=cur->_subs[i];if(tmp->_subs[index])tmp->_subs[index]->_parent=tmp;++index;}k=cur->_keys[boundary];cur->_size--;//没有父亲if(cur->_parent==NULL){_root=newNode;_root->_keys[0]=k;_root->_subs[0]=cur;_root->_subs[1]=tmp;_root->_size=1;tmp->_parent=_root;cur->_parent=_root;returntrue;}cur=cur->_parent;sub=tmp;}}void_InsertKey(Node*cur,constK&k,Node*sub){inti=cur->_size-1;while(i>=0){if(cur->_keys[i]>k){cur->_keys[i+1]=cur->_keys[i];cur->_subs[i+2]=cur->_subs[i+1];--i;}else{break;}}cur->_keys[i+1]=k;cur->_subs[i+2]=sub;if(sub){sub->_parent=cur;}cur->_size++;}voidInOrder(){_InOrder(_root);cout<<endl;}void_InOrder(Node*root){if(root==NULL){return;}for(size_ti=0;i<root->_size;++i){_InOrder(root->_subs[i]);cout<<root->_keys[i]<<"";}_InOrder(root->_subs[root->_size]);}protected:Node*_root;};voidTestBTree1(){BTree<int,1024>t1;inta[]={53,75,139,49,145,36,101};for(inti=0;i<sizeof(a)/sizeof(a[0]);++i){t1.Insert(a[i]);}t1.InOrder();}