B树的实现与源代码一
B树的定义
假设B树的度为t（t>=2），则B树满足如下要求：（参考算法导论）
（1） 每个非根节点至少包含t-1个关键字，t个指向子节点的指针；至多包含2t-1个关键字，2t个指向子女的指针（叶子节点的子女为空）。
（2） 节点的所有key按非降序存放，假设节点的关键字分别为K[1], K[2] … K[n], 指向子女的指针分别为P[1], P[2]…P[n+1]，其中n为节点关键字的个数。则有：
P[1] <= K[1] <= P[2] <= K[2] …..<= K[n] <= P[n+1] // 这里P[n]也指其指向的关键字
（3） 若根节点非空，则根节点至少包含两个子女；
（4） 所有的叶子节点都在同一层。
B树的搜索，search（root, target）
从root出发，对每个节点，找到大于或等于target关键字中最小的K[i]，如果K[i]与target相等，则查找成功；否则在P[i]中递归搜索target，直到到达叶子节点，如仍未找到则说明关键字不在B树中，查找失败。
B树的插入，insert(root, target)
B树的插入需要沿着搜索的路径从root一直到叶节点，根据B树的规则，每个节点的关键字个数在[t-1, 2t-1]之间，故当target要加入到某个叶子时，如果该叶子节点已经有2t-1个关键字，则再加入target就违反了B树的定义，这时就需要对该叶子节点进行分裂，将叶子以中间节点为界，分成两个包含t-1个关键字的子节点，同时把中间节点提升到该叶子的父节点中，如果这样使得父节点的关键字个数超过2t-1，则要继续向上分裂，直到根节点，根节点的分裂会使得树加高一层。
上面的过程需要回溯，那么能否从根下降到叶节点后不回溯就能完成节点的插入呢？答案是肯定的，核心思想就是未雨绸缪，在下降的过程中，一旦遇到已满的节点（关键字个数为2t-1），就就对该节点进行分裂，这样就保证在叶子节点需要分裂时，其父节点一定是非满的，从而不需要再向上回溯。
B树的删除，delete(root, target)
在删除B树节点时，为了避免回溯，当遇到需要合并的节点时就立即执行合并，B树的删除算法如下：从root向叶子节点按照search规律遍历：
（1） 如果target在叶节点x中，则直接从x中删除target，情况（2）和（3）会保证当再叶子节点找到target时，肯定能借节点或合并成功而不会引起父节点的关键字个数少于t-1。
（2） 如果target在分支节点x中：
（a） 如果x的左分支节点y至少包含t个关键字，则找出y的最右的关键字prev，并替换target，并在y中递归删除prev。
（b） 如果x的右分支节点z至少包含t个关键字，则找出z的最左的关键字next，并替换target，并在z中递归删除next。
（c） 否则，如果y和z都只有t-1个关键字，则将targe与z合并到y中，使得y有2t-1个关键字，再从y中递归删除target。
（3） 如果关键字不在分支节点x中，则必然在x的某个分支节点p[i]中，如果p[i]节点只有t-1个关键字。
（a） 如果p[i-1]拥有至少t个关键字，则将x的某个关键字降至p[i]中，将p[i-1]的最大节点上升至x中。
（b） 如果p[i+1]拥有至少t个关键字，则将x个某个关键字降至p[i]中，将p[i+1]的最小关键字上升至x个。
（c） 如果p[i-1]与p[i+1]都拥有t-1个关键字，则将p[i]与其中一个兄弟合并，将x的一个关键字降至合并的节点中，成为中间关键字。
部分内容转自：http://blog.chinaunix.net/uid-20196318-id-3030529.html
头文件源代码
#ifndef B_TREE_H#define B_TREE_H#include <iostream>#include <utility>#include <queue>#define t 3 // the minimum degreestruct BNode{int size;int key[2 * t - 1];bool leaf;BNode *child[2 * t];};std::pair<BNode*, int> BTreeSearch( BNode *node, int k );void BTreeCreate( BNode *&T );void BTreeSplitChild( BNode *&x, int i, BNode *&y );void BTreeInsertNonfull( BNode *&x, int k );void BTreeInsert( BNode *&T, int k );void LevelOrderTraverse( BNode *T );#endif
源代码
/** * @brief B Tree * @author An * @data 2013.9.1 **/#include "B_Tree.h"//#include <utility>using namespace std;pair<BNode*, int> BTreeSearch( BNode *node, int k ){int i = 0;while ( i < node->size && k > node->key[i] ){++i;}if ( i < node->size && k == node->key[i] ){return make_pair( node, i );}if ( node->leaf ){cout << "Search Error: No this key!" << endl;return make_pair( node, -1 );}else{return BTreeSearch( node->child[i], k );}}void BTreeCreate( BNode *&T ){T->size = 0;T->leaf = true;for ( int i = 0; i < 2 * t - 1; ++i ){T->key[i] = 0;T->child[i] = NULL;}T->child[2 * t - 1 ] = NULL;}void BTreeSplitChild( BNode *&x, int i, BNode *&y ){// initialize the new node zBNode *z = new BNode;z->leaf = y->leaf;z->size = t - 1;for ( int j = 0; j < 2 * t - 1; ++j ){z->key[j] = 0;z->child[j] = NULL;}z->child[2 * t - 1 ] = NULL;for ( int j = 0; j < z->size; ++j ){z->key[j] = y->key[ t + j];}if ( !y->leaf ){//z->child = new BNode*[2 * t];for ( int j = 0; j <= z->size; ++j ){z->child[j] = y->child[ t + j];}}// update yy->size = t - 1;// update the children of xfor ( int j = x->size; j > i; ++j ){x->child[j + 1] = x->child[j];}x->child[i + 1] = z;//update the keys of xfor ( int j = x->size - 1; j >= i; ++j ){x->key[j + 1] = x->key[j];}x->key[i] = y->key[ t - 1];x->size++;}void BTreeInsertNonfull( BNode *&x, int k ){int i = x->size - 1;if ( x->leaf ){while ( i >= 0 && k < x->key[i] ){x->key[i + 1] = x->key[i];i--;}x->key[i + 1] = k;x->size++;}else{while ( i >= 0 && k < x->key[i] ){i--;}i++;if ( x->child[i]->size == 2 * t - 1 ){BTreeSplitChild( x, i, x->child[i] );if ( k > x->key[i] ){i++;}}BTreeInsertNonfull( x->child[i], k );}}void BTreeInsert( BNode *&T, int k ){BNode *r = T;if ( r->size == 2 * t - 1 ){BNode *s = new BNode;s->leaf = false;s->size = 0;for ( int i = 0; i < 2 * t - 1; ++i ){s->key[i] = 0;s->child[i] = NULL;}s->child[2 * t - 1 ] = NULL;s->child[0] = r;T = s;BTreeSplitChild( s, 0, r );BTreeInsertNonfull( s, k );}else{BTreeInsertNonfull( r, k );}}void LevelOrderTraverse( BNode *T ){queue<BNode*> qb;qb.push( T );while ( !qb.empty() ){BNode *r = qb.front();qb.pop();cout << "[ ";for ( int i = 0; i < r->size; ++i ){cout << r->key[i] << " ";if ( r->child[i] != NULL ){qb.push( r->child[i] );}}cout << "] ";if ( r->child[r->size] != NULL ){qb.push( r->child[r->size] );}}}
测试
#include "B_Tree.h"int main(){BNode *T = new BNode;BTreeCreate( T );int a[] = { 18, 31, 12, 10, 15, 48, 45, 47, 50, 52, 23, 30, 20 };int n = sizeof( a ) / sizeof( a[0] );for ( int i = 0; i < n; ++i ){BTreeInsert( T, a[i] );}LevelOrderTraverse( T );return 0;}