//這是我在學數據庫時寫的C++的B樹的實現.
B樹有四個性質:
1.樹中每個節點最多含有2m-1的節點;
2.除了根節點外,其他每個節點至少有m-1個孩子;
3.若根節點不是葉子節點則至少有2個孩子(即整個樹只有根節點);
4.所有葉子節點都在同一層
#include <iostream>
using namespace std;
static const int m = 3; //定義最小度為3
static const int key_max = 2*m-1;//關鍵字最大個數
static const int key_min = m - 1;//關鍵字最小個數
static const int child_max = key_max + 1;//子節點最大個數(這裡可以看出子節點數與關鍵字數有關)
static const int child_min = key_min + 1;//子節點最小個數
template <class t="">
class BTree;//前置聲明
/*
類名:BTnode
*/
template <class t="">
class BTnode
{
friend class BTree<t>;//友元函數
public:
BTnode()
{
keyNum = 0;
parent = NULL;//父節點初始化
isleaf = true;
int i ;
for (i = 0;i < child_max;i++)//子樹指針數組初始化
{
pchild[i] = NULL;
}
for (i = 0;i < key_max;i++)//關鍵字數組初始化
{
keyvalue[i] = '\0';
}
}
private:
bool isleaf;//判斷節點是否是葉子節點
int keyNum;//關鍵字個數
BTnode<t>* parent;//指向父節點
BTnode<t>* pchild[child_max];//子樹指針數組
T keyvalue[key_max];//關鍵字數組
};
/*
類名:BTree
*/
template <class t="">
class BTree
{
public:
/*
函數名:BTree
函數作用:無參構造函數
函數參數:無
函數返回值: 無
*/
BTree()
{
root = NULL;
}
/*
函數名:BTree_insert
函數作用:插入關鍵字
函數參數:T value
函數返回值: bool類型判斷插入是否成功
*/
bool BTree_insert(T value)
{
if (contain(value))//看樹中是否有相同的關鍵字
{
return false;
}
else
{
if (root == NULL)
{
root = new BTnode<t>();
}
if (root->keyNum == key_max)
{
BTnode<t>* newnode = new BTnode<t>();
newnode->pchild[0] = root;
newnode->isleaf = false;//由上步操作可知newnode已經有子節點
SplitBlock(newnode,0,root);//分塊操作
root = newnode;//更新根節點
}
Notfull_insert(root,value);//插入塊未滿的操作
return true;
}
}
/*
函數名:SplitBlock
函數作用:把節點分裂
函數參數:BTnode<t>* node_parent,int child_index,BTnode<t>* node_child
函數返回值: 無
*/
void SplitBlock(BTnode<t>* node_parent,int child_index,BTnode<t>* node_child)
{
BTnode<t>* node_right = new BTnode<t>();
node_right->isleaf = node_child->isleaf;
node_right->keyNum = key_min;
int i;
//node_right拷貝關鍵字
for (i = 0;i < key_min;i++)
{
node_right->keyvalue[i] = node_child->keyvalue[i+child_min];
}
//判斷分裂的節點是否是葉子節點,如果不是的話就要把它的孩子賦值過去
if (!node_child->isleaf)
{
for (i = 0;i < child_min;i++)
{
node_right->pchild[i] = node_child->pchild[i+child_min];
node_child->pchild[i+child_min]->parent = node_right->pchild[i];
}
}
node_child->keyNum = key_min;//更新子節點的關鍵字數
//把父節點關鍵字和子指針往後移 倒序賦值
for (i = node_parent->keyNum;i > child_index;i--)
{
node_parent->keyvalue[i] = node_parent->keyvalue[i-1];
node_parent->pchild[i+1] = node_parent->pchild[i];
node_child->pchild[i]->parent = node_parent->pchild[i+1];
}
node_parent->keyNum++;//更新父節點關鍵字數
node_parent->pchild[child_index+1] = node_right;
node_right->parent = node_parent->pchild[child_index+1];
//把中間的那個關鍵字上移到父節點
node_parent->keyvalue[child_index] = node_child->keyvalue[key_min];
}
/*
函數名:Notfull_insert
函數作用:往沒有滿的節點中增加關鍵字
函數參數:BTnode<t>* node,T value
函數返回值:無
*/
void Notfull_insert(BTnode<t>* node,T value)
{
int node_keynum = node->keyNum;//獲取節點關鍵字數
if (node->isleaf)//node是葉子節點
{
while (node_keynum > 0 && value < node->keyvalue[node_keynum-1])
{
node->keyvalue[node_keynum] = node->keyvalue[node_keynum-1];//把關鍵字往後移動
--node_keynum;
}
node->keyvalue[node_keynum] = value;
node->keyNum++;
}
else//node是內部節點
{
while (node_keynum > 0 && value < node->keyvalue[node_keynum-1])
{
--node_keynum;
}
//在比它小和比它大中間那個子節點中找合適位置,
//如果它比所有的都小則在第一個子節點中尋找
BTnode<t>* node_child = node->pchild[node_keynum];
if (node_child->keyNum == key_max)
{
SplitBlock(node,node_keynum,node_child);
if (value > node->keyvalue[node_keynum])//插入值和子節點中間的值比較
{
node_child = node->pchild[node_keynum+1];
}
}
Notfull_insert(node_child,value);//繼續往下尋找合適的位置
}
}
/*
函數名:contain
函數作用:查找是否有相同元素在數中
函數參數:T value
函數返回值:bool類型
*/
bool contain(T value)
{
if (BTree_find(root,value) != NULL)
return true;
return false;
}
/*
函數名:BTree_find
函數作用:查找是否有相同元素在數中
函數參數:BTnode<t>* node,T value
函數返回值: BTnode<t>*
*/
BTnode<t>* BTree_find(BTnode<t>* node,T value)
{
if (node == NULL)//當前節點為空的時候
{
return NULL;
}
else//當前節點不為空
{
int i;
//在比它小和比它大的中間子節點中尋找相等的
for (i = 0; i < node->keyNum ;i++)
{
if (value <= node->keyvalue[i])
{
break;
}
}
//校驗當前的關鍵字是否等於查找的關鍵字
if (i < node->keyNum && value == node->keyvalue[i])//i是下標最大值keyNum-1
{
return node;
}
else
{
//如果之前比查找關鍵沒有相等的關鍵字並且當前節點是葉子節點的話
//那麼在B樹中沒有一樣的關鍵字(因為後面比關鍵字更大)
if (node->isleaf)
{
return NULL;
}
else//如果不是葉子節點則在下面的子節點中尋找
{
return BTree_find(node->pchild[i],value);//這裡的return別忘了
}
}
}
}
/*
函數名:printpoint
函數作用:打印元素
函數參數:BTnode<t>* node,int count
函數返回值:無
*/
void printpoint(BTnode<t>* node,int count)
{
if (node != NULL)//判斷元素是否為空
{
int i,j;
//每個節點從小到大打印
for (i = 0;i < node->keyNum; i++)
{
//判斷是否葉節點,不是的話則要往子節點中尋找打印
if (!node->isleaf)//判斷是否是葉子節點
{
printpoint(node->pchild[i],count-3);
}
for (j = count;j >= 0; j--)
{
cout<<"-";
}
cout<<"|"<<node->keyvalue[i]<<"|"<<endl; if="" node-="">isleaf)//子節點數比關鍵字數多一個
{
printpoint(node->pchild[i],count-3);
}
}
}
/*
函數名:printpoint
函數作用:printpoint無參函數傳遞值過去
函數參數:無
函數返回值:無
*/
void printpoint()
{
printpoint(root,key_max*5);
}
/*
函數名:BTree_delete
函數作用:刪除函數
函數參數:T value
函數返回值:bool類型
*/
bool BTree_delete(T value)
{
if (!contain(value))
{
return false;
}
if (root->keyNum == 1)
{
if (root->isleaf)
{
delete root;
root = NULL;
return true;
}
else//當根節點只有一個關鍵字時且不為葉子節點
{
BTnode<t>* node_child1 = root->pchild[0];
BTnode<t>* node_child2 = root->pchild[1];
//減少一層樹的高度
if (node_child1->keyNum == key_min && node_child2->keyNum == key_min)
{
MergeBlock(root,0);
delete root;
root = node_child1;
}
}
}
BTree_deletebalance(root,value);
}
/*
函數名:MergeBlock
函數作用:合並塊
函數參數:BTnode<t>* node_parent,int child_index
函數返回值:無
*/
void MergeBlock(BTnode<t>* node_parent,int child_index)
{
BTnode<t>* node_child1 = node_parent->pchild[child_index];
BTnode<t>* node_child2 = node_parent->pchild[child_index+1];
//將父節點的節點對應的關鍵字下移
node_child1->keyvalue[key_min] = node_parent->keyvalue[child_index];
node_child1->keyNum = key_max;
int i;
for (i = 0;i < key_min;i++)
{
node_child1->keyvalue[child_min+i] = node_child2->keyvalue[i];
}
//判斷node_child1是否是葉子節點,不是葉子節點則要將node_child2的子節點賦值給node_child1
if (!node_child1->isleaf)
{
for (i = 0; i < child_min;i++)
{
node_child1->pchild[i+child_min] = node_child2->pchild[i];
}
}
//因為父節點下移一個關鍵字,則關鍵字後的所有值要往前移動一個
node_parent->keyNum--;
for (i = child_index;i < node_parent->keyNum;i++)
{
node_parent->keyvalue[i] = node_parent->keyvalue[i+1];
//子節點也要往前移動一位
node_parent->pchild[i+1] = node_parent->pchild[i+2];
}
delete node_child2;
node_child2 = NULL;
}
/*
函數名:getprev
函數作用:在左邊的兄弟節點中找一個最大的
函數參數:BTnode<t>* node
函數返回值:左邊兄弟的最大的關鍵字
*/
T getprev(BTnode<t>* node)
{
//在比節點位置小的節點中找一個最大的值最為
while (!node->isleaf)
{
node = node->pchild[node->keyNum];
}
node->keyNum--;
return node->keyvalue[node->keyNum-1];
}
/*
函數名:getnext
函數作用:在右邊的兄弟節點中找一個最小的
函數參數:BTnode<t>* node
函數返回值:右邊兄弟的最小的關鍵字
*/
T getnext(BTnode<t>* node)
{
//在比節點位置大的節點中找一個最小的
while (!node->isleaf)
{
node = node->pchild[0];
}
return node->keyvalue[0];
}
/*
函數名:BTree_deletebalance
函數作用:用遞歸刪除並做修復
函數參數:BTnode<t>* node
函數返回值:無
*/
void BTree_deletebalance(BTnode<t>* node,T value)
{
int i;
//在當前節點中找合適坐標使得value在這個區間內
for(i = 0;i < node->keyNum && value > node->keyvalue[i];i++)
{
}
//如果當前i的關鍵字等於value
if (i < node->keyNum && value == node->keyvalue[i])
{
//判斷當前節點是否是葉子節點,如果是的話直接刪除,下面的情況保證了如果value在葉子節點的話,葉子節點keyNum一定是>=child_min
if (node->isleaf)
{
node->keyNum--;
//把i後面的都往前移動一位
for (;i < node->keyNum;i++)
{
node->keyvalue[i] = node->keyvalue[i+1];
}
return;
}
else//當前節點為內節點
{
//裡面關鍵字都比value小的節點
BTnode<t>* node_left = node->pchild[i];
//裡面關鍵字都比value大的節點
BTnode<t>* node_right = node->pchild[i+1];
if (node_left->keyNum >= child_min)//左子節點中的關鍵字數大於等於child_min
{
T prev_replace = getprev(node_left);
//傳遞不平衡點讓pre_replace
BTree_deletebalance(node_left,prev_replace);
//讓前繼的關鍵字替換當前刪除的關鍵字
node->keyvalue[i] = prev_replace;
return;
}
else if (node_right->keyNum >= child_min)//右子節點中的關鍵字數大於等於child_min
{
T next_replace = getnext(node_right);
//在左邊中找到最大的那個遞歸替換
BTree_deletebalance(node_right,next_replace);
//讓前繼的關鍵字替換當前刪除的關鍵字
node->keyvalue[i] = next_replace;
return;
}
else//左右子節點中的關鍵字數都等於key_min
{
//合並兩個子節點
MergeBlock(node,i);
//在合並的節點中刪除value值
BTree_deletebalance(node_left,value);
}
}
}
else//關鍵字不在當前節點(下面步驟保證了遍歷的所有節點關鍵字數都是大於等於child_min)
{
//在(<<value<<)的區間找 t="">* node_child = node->pchild[i];//這裡i = node->keyNum
BTnode<t>* node_left = NULL;
BTnode<t>* node_right = NULL;
if (node_child->keyNum == key_min)//當前節點只有兩個關鍵字,補給當前節點使之大於等於child_min
{
//判斷是否有左右兄弟節點
if (i >0)
{
node_left = node->pchild[i-1];
}
if (i <= node->keyNum-1)
{
node_right = node->pchild[i+1];
}
int j;
//當前左兄弟的關鍵字數大於等於child_min
if (node_left && node_left->keyNum >= child_min)
{
//把父節點的i-1對應的關鍵字下移
for (j = node_child->keyNum;j > 0; j--)
{
node_child->keyvalue[j] = node_child->keyvalue[j-1];
}
node_child->keyvalue[0] = node->keyvalue[i-1];
//如果子節點的左兄弟節點不是葉子節點
if (!node_left->isleaf)
{
//把左兄弟最右邊的子節點指針賦值給node_child
for (j = node_child->keyNum+1;j > 0;j--)
{
node_child->pchild[j-1]->parent = node_child->pchild[j]->parent;
node_child->pchild[j] = node_child->pchild[j-1];
}
node_left->pchild[node_left->keyNum]->parent = node_child->pchild[0];
node_child->pchild[0] = node_left->pchild[node_left->keyNum];
}
node_child->keyNum++;
node->keyvalue[i-1] = node_left->keyvalue[node_left->keyNum-1];
node_left->keyNum--;
}
else if (node_right && node_right->keyNum >= child_min)
{
//把父節點的i對應的關鍵字下移
node_child->keyvalue[node_child->keyNum] = node->keyvalue[i];
node_child->keyNum++;
//把右兄弟節點最小的關鍵字賦值給父節點的i位置
node->keyvalue[i] = node_right->keyvalue[0];
node_right->keyNum--;
//把右兄弟的關鍵字往前移動一位
for (j = 0;j < node_right->keyNum;j++)
{
node_right->keyvalue[j] = node_right->keyvalue[j+1];
}
//如果右兄弟不是葉子節點則需要把右兄弟最左邊的子節點指針賦值給node_child
if (!node_right->isleaf)
{
node_right->pchild[0]->parent = node_child->pchild[node_child->keyNum]->parent;
node_child->pchild[node_child->keyNum] = node_right->pchild[0];
for (j = 0;j < node_right->keyNum+1;j++)
{
node_right->pchild[j+1]->parent = node_right->pchild[j]->parent;
node_right->pchild[j] = node_right->pchild[j+1];
}
}
}
else if (node_left)//node_left只有child_min-1個關鍵字
{
//把左兄弟合並
MergeBlock(node,i-1);
//更新子節點
node_child = node_left;
}
else if (node_right)
{
//把右兄弟合並,子節點無需更新
MergeBlock(node,i);
}
}
BTree_deletebalance(node_child,value);
}
}
private:
BTnode<t>* root;//根節點
};
</t></t></t></value<<)的區間找></t></t></t></t></t></t></t></t></t></t></t></t></t></t></endl;></node-></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></class></t></t></t></class></class></iostream>
