B-Tree的C++实现

B-Tree的C++实现

简要说明下B树的性质。

用M表示B树的阶数，L表示叶子节点的最大元素个

（性质说明来自于《数据结构与问题求解(C++版)》第19章）

1、数据项保存在叶子中

 2、非叶子节点具有M-1个键指导查找的进行；键i代表子树i+1中最小的键

3、根要么是叶子，要么就有2～M个孩子

4、所有非叶子节点，(根除外)都具有[M/2]～M个孩子

 5、所有叶子都在同一深度，并且对某一叶子，具有[L/2]～L个数据项

在对B树进行插入操作时，如果某个叶子中的元素个数已经达到L个，那么这时就需要对叶子进行分裂。而叶子的分裂同时也可能引起父节点的分裂。造成分裂的效果可能会依次往上。直到造成根的分裂，产生一个新的根才终止，当然这种情况是很少的。在对B树进行删除时，可能会使得叶子中元素的个数不满足规则5。这个时候就需要进行叶子的合并了。而叶子的合并也可能会造成父节点的合并，这种影响同样可能会向上传递，直到根的孩子个数减为0，从而造成树的高度减一才终止。这种情形依旧是很少见的

#include<iostream>
using std::cout;
using std::endl;
using std::ostream;
//定义B树的阶数
#define M 4
#define L 3
class BTree
{
private:
int child_size;  //若此节点为非叶子节点，表示此节点的子节点个数
int elem_size;    //若此节点为叶子节点，表示此叶子所含的元素个数
bool is_leaf;
BTree* parent;
BTree* root;
/*
如果此节点是叶子节点，那么就使用elem_data部分
如果此节点是非叶子节点，那么就需要child_list来保存指向其子节点的指针， 并且还需要有index_key（对应第二条性质）
*/
union{     
struct{
BTree* child_list[M];
int index_key[M-1];
};
int elem_data[L];
};
public:
BTree();
void insert(int);  //插入一个元素
void insert(int*,int);  //插入一个数组
~BTree();
void remove(int);
/*查找某个值是否在记录中，找到返回1，否则返回0*/
//int find(int);
BTree* getRoot();
/*
按照层次将数输出
*/
friend ostream& operator<<(ostream& os,BTree);
/*检查树的各项指针的指向是否正确*/
friend bool check_tree(BTree* root);
private:
/*
当往树中插入数据引起树中节点的分裂时使用。
*/
void node_break( BTree&, BTree&);
/*
当从树中删除元素引起叶子合并时使用
*/
void node_merge(BTree&);
/*
往一个有序数组中插入一个元素，插入完之后要保证数组中的元素依旧是有序的
array 为要插入数据的数组
data 为待插入的数据
size 为数组中已有的元素个数
*/
void array_insert(int* array,int data, int size);
/*
从一个有序数组中删除一个元素，删除完之后要保证数组中的元素依旧是有序的
*/
int array_remove(int* array,int data, int size);
/*
取得某一颗子树的最小值
*/
int get_min_value(const BTree&);
/*
返回一个节点的元素个数或者子树个数
*/
int get_size(const BTree&);
};