簡要說明下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&);
};