b樹的c++實現

b樹的c++實現

#include 
#include 
#include 

using namespace std;


class BTree{
	static const int M = 2;
	struct BTNode{
		int keyNum;
		int key[2 * M - 1];  //關鍵字數組
		struct BTNode* child[2 * M];//孩子結點數組
		bool isLeaf;
	};
	
	BTNode* root;
	//在插入時，保證pNode結點的關鍵字少於2*M-1個
	void InsertNonFull(BTNode* pNode, int key);
	//當child結點有2M-1個關鍵字時，分裂此結點
	void SplitChild(BTNode* parent, int i, BTNode* child);
	//兩個M-1個元素的結點合並
	void merge(BTNode* parent, BTNode* pNode1, BTNode* pNode2, int index);
	//找到比pNode結點第一個關鍵字小的最大的關鍵字，也就是前繼結點
	int predecessor(BTNode* pNode);
	//找到後繼結點
	int successor(BTNode* pNode);
	//pNode1向parent要一個結點key[index]，parent向pNode0要一個結點，pNode1關鍵字個數為M-1
	void ExchangeLeftNode(BTNode *parent, BTNode* pNode0, BTNode* pNode1, int index);
	void ExchangeRightNode(BTNode* parent, BTNode* pNode1, BTNode *pNode2, int index);
	//刪除，結點關鍵字個數不少於M
	void RemoveNonLess(BTNode* pNode, int key);
	void DiskWrite(BTNode* pNode);
	void DiskRead(BTNode *pNode);
	BTNode* Search(BTNode* pNode, int key, int &index);
public:
	BTree();
	~BTree();
	BTNode* search(int key, int &index);
	void insert(int key);
	void remove(int key);
	//按層級打印。
	void PrintRow();
};

 
BTree::BTree()
{
	root = new BTNode();
	root->isLeaf = true;
	root->keyNum = 0;
	DiskWrite(root);
}

 
BTree::~BTree()
{
	struct BTNode* pNode;
	queue q;
	q.push(root);
	while (!q.empty()){
		pNode = q.front();
		q.pop();
		
		if (pNode->isLeaf)
			continue;
		for (int i = 0; i <= pNode->keyNum; i++)
			q.push(pNode->child[i]);
		delete pNode;
	}
}

 
void BTree::DiskWrite(BTNode* pNode)
{

}

 
void BTree::DiskRead(BTNode *pNode)
{

}

 
BTree::BTNode* BTree::Search(BTNode* pNode, int key, int &index)
{
	int i = 0;
	while (ikeyNum&&key>pNode->key[i])//找到第一個大於等於key的下標
		i++;
	if (i < pNode->keyNum&&key == pNode->key[i]){//如果找到關鍵字，返回
		index = i;
		return pNode;
	}
	if (pNode->isLeaf)//已經搜到葉子結點，不存在
		return NULL;
	else{
		DiskRead(pNode->child[i]);
		return Search(pNode->child[i], key, index);//在第一個大於key值的孩子節點中遞歸搜索
	}
}

 
void BTree::InsertNonFull(BTNode* pNode, int key)
{
	int i = pNode->keyNum - 1;
	if (pNode->isLeaf){//如果是葉子結點，直接插入
		while (i >= 0 && key < pNode->key[i]){
			pNode->key[i + 1] = pNode->key[i];
			i--;
		}
		pNode->key[i + 1] = key;
		pNode->keyNum++;
		DiskWrite(pNode);
	}
	else {
		while (i >= 0 && key < pNode->key[i])
			i--;//找到第一個小於等於key的下標
		i++;
		DiskRead(pNode->child[i]);
		if (pNode->child[i]->keyNum == 2 * M - 1){//判斷孩子結點是否有2*M-1個關鍵字，有就需要分裂
			SplitChild(pNode, i, pNode->child[i]);
			if (key>pNode->key[i])//如果key比上移到父節點的元素大
				i++;
		}
		InsertNonFull(pNode->child[i], key);//已保證孩子結點關鍵字個數少於2*M-1個
	}
}

 
void BTree::SplitChild(BTNode* parent, int i, BTNode* child)
{
	int j;
	struct BTNode* pNode = new BTNode();
	pNode->isLeaf = child->isLeaf;
	pNode->keyNum = M - 1;
	for (j = 0; j < M - 1; j++)//將child結點的後M-1個關鍵字賦給新節點
		pNode->key[j] = child->key[j + M];
	if (!child->isLeaf){//如果child不是葉子結點，將其後M個孩子結點賦給新節點。
		for (j = 0; j < M; j++)
			pNode->child[j] = child->child[j + M];
	}
	child->keyNum = M - 1;

	for (j = parent->keyNum; j > i; j--)
		parent->child[j + 1] = parent->child[j];//將child結點的父節點parent下標i以後的結點指針都向後移動一位，
	parent->child[j + 1] = pNode;//將新生成的結點當成parent的一個孩子
	for (j = parent->keyNum - 1; j >= i; j--)	//將i後面的關鍵字都向後移動一位
		parent->key[j + 1] = parent->key[j];
	parent->key[j + 1] = child->key[M - 1];//將孩子結點的中間結點移到父節點的指定位置
	parent->keyNum++;
	DiskWrite(parent);
	DiskWrite(pNode);
	DiskWrite(child);
}

 
void BTree::merge(BTNode* parent, BTNode* pNode1, BTNode* pNode2, int index)
{
	pNode1->key[M - 1] = parent->key[index];
	for (int i = 0; i < M - 1; i++)//將pNode2的關鍵字移到pNode1中
		pNode1->key[i + M] = pNode2->key[i];
	pNode1->keyNum = 2 * M - 1;
	if (!pNode1->isLeaf){//如果不是葉子，將pNode2的孩子指針也移到pNode1中
		for (int i = 0; i < M; i++)
			pNode1->child[i + M] = pNode2->child[i];
	}

	for (int i = index; i < parent->keyNum; i++){//將父節點index以後的關鍵字以及孩子指針都向前移動一位
		parent->key[i] = parent->key[i + 1];
		parent->child[i + 1] = parent->child[i + 2];
	}
	parent->keyNum--;
	delete pNode2;
}

 
int BTree::predecessor(BTNode* pNode)
{
	while (!pNode->isLeaf)
		pNode = pNode->child[pNode->keyNum];
	return pNode->key[pNode->keyNum - 1];
}

 int BTree::successor(BTNode* pNode)
{
	while (!pNode->isLeaf)
		pNode = pNode->child[0];
	return pNode->key[0];
}

 
void BTree::ExchangeLeftNode(BTNode *parent, BTNode* pNode0, BTNode* pNode1, int index)
{
	for (int i = pNode1->keyNum; i > 0; i--)
		pNode1->key[i] = pNode1->key[i - 1];//pNode1結點所有關鍵字向後移動一位
	pNode1->key[0] = parent->key[index];//第0個關鍵字來自父節點
	pNode1->keyNum++;
	parent->key[index] = pNode0->key[pNode0->keyNum - 1];//父節點的index處的關鍵字來自pNode0的最大關鍵字

	if (!pNode0->isLeaf){//如果不是葉子結點，
		for (int i = pNode1->keyNum; i > 0; i--)//將pNode1的孩子指針都向後移動一位，並將pNode0的最後一個孩子指針賦給它的第一個
			pNode1->child[i] = pNode1->child[i - 1];
		pNode1->child[0] = pNode0->child[pNode0->keyNum];
	}

	pNode0->keyNum--;
}

 
void BTree::ExchangeRightNode(BTNode* parent, BTNode* pNode1, BTNode *pNode2, int index)
{
	pNode1->key[pNode1->keyNum] = parent->key[index];
	pNode1->keyNum++;
	parent->key[index] = pNode2->key[0];
	for (int i = 0; i < pNode2->keyNum - 1; i++)
		pNode2->key[i] = pNode2->key[i + 1];

	if (!pNode2->isLeaf){
		pNode1->child[pNode1->keyNum] = pNode2->child[0];
		for (int i = 0; i < pNode2->keyNum; i++)
			pNode2->child[i] = pNode2->child[i + 1];
	}
	pNode2->keyNum--;
}

 
void BTree::RemoveNonLess(BTNode* pNode, int key)
{
	if (pNode->isLeaf){//到了葉子結點，直接刪除
		int i = 0;
		while (ikeyNum&&key>pNode->key[i])
			i++;
		if (i < pNode->keyNum&&key == pNode->key[i]){
			while (i < pNode->keyNum - 1){
				pNode->key[i] = pNode->key[i + 1];
				i++;
			}
			pNode->keyNum--;
		}
		else {
			cout << "not found!" << endl;
		}
	}
	else {
		int i = 0;
		while (i < pNode->keyNum&&key > pNode->key[i])//找到第一個大於等於key的關鍵字
			i++;
		if (i < pNode->keyNum&&key == pNode->key[i]){//在結點中找到要刪除的關鍵字
			struct BTNode* pNode1 = pNode->child[i];
			struct BTNode* pNode2 = pNode->child[i + 1];
			if (pNode1->keyNum >= M){//如果關鍵字左邊的孩子結點的關鍵字數大於等於M
				int target = predecessor(pNode1);//將其前繼結點移到pNode中
				pNode->key[i] = target;
				RemoveNonLess(pNode1, target);//遞歸刪除target
			}
			else if (pNode2->keyNum >= M){//右邊，同理
				int target = successor(pNode2);
				pNode->key[i] = target;
				RemoveNonLess(pNode2, target);
			}
			else {
				merge(pNode, pNode1, pNode2, i);//都小於M，合並
				RemoveNonLess(pNode1, key);
			}
		}
		else {//不在此結點中
			struct BTNode *pNode1 = pNode->child[i];
			struct BTNode *pNode0 = NULL;
			struct BTNode *pNode2 = NULL;
			if (i>0)
				pNode0 = pNode->child[i - 1];//左結點
			if (i < pNode->keyNum)
				pNode2 = pNode->child[i + 1];//右結點
			if (pNode1->keyNum == M - 1){//如果要刪除的孩子結點關鍵字個數為M-1
				if (i > 0 && pNode0->keyNum >= M){//如果左鄰結點至少有M個關鍵字，向其借一個
					ExchangeLeftNode(pNode, pNode0, pNode1, i - 1);
				}
				else if (i < pNode->keyNum&&pNode2->keyNum >= M){//同理，
					ExchangeRightNode(pNode, pNode1, pNode2, i);
				}
				else if (i>0){//兩個相鄰結點都只有M-1個關鍵字，合並
					merge(pNode, pNode0, pNode1, i - 1);
					pNode1 = pNode0;
				}
				else{
					merge(pNode, pNode1, pNode2, i);
				}
				RemoveNonLess(pNode1, key);

			}
			else{
				RemoveNonLess(pNode1, key);
			}
		}
	}
}

 
BTree::BTNode* BTree::search(int key, int &index)
{
	return Search(root, key, index);
}

 
void BTree::insert(int key)
{
	struct BTNode* r = root;
	if (root->keyNum == 2 * M - 1){//根節點特殊處理，如果根節點關鍵字個數為2*M-1，
		struct BTNode* pNode = new BTNode();//新建一個結點作為新的根節點，並將現在的根節點作為
		root = pNode;//新根節點的孩子結點
		pNode->isLeaf = false;
		pNode->keyNum = 0;
		pNode->child[0] = r;
		SplitChild(pNode, 0, r);//孩子結點r有2*M-1個關鍵字
		InsertNonFull(pNode, key);
	}
	else
		InsertNonFull(r, key);
}

 
void BTree::remove(int key)
{
	if (root->keyNum == 1){//如果根節點只有兩個孩子
		struct BTNode* pNode1 = root->child[0];
		struct BTNode* pNode2 = root->child[1];
		if (pNode1->keyNum == M - 1 && pNode2->keyNum == M - 1){//且兩個孩子都只有M-1個關鍵字，合並
			merge(root, pNode1, pNode2, 0);
			delete root;
			root = pNode1;
		}
		else {
			RemoveNonLess(root, key);
		}
	}
	else {
		RemoveNonLess(root, key);
	}
}

 
void BTree::PrintRow()
{
	struct BTNode* pNode;
	queue q;
	q.push(root);
	while (!q.empty()){
		pNode = q.front();
		q.pop();
		cout << "[ ";
		for (int i = 0; i < pNode->keyNum; i++)
			cout << pNode->key[i] << " ";
		cout << "]" << endl;
		if (pNode->isLeaf)
			continue;
		for (int i = 0; i <= pNode->keyNum; i++)
			q.push(pNode->child[i]);
	}
}

int main(void)
{
	BTree tree;
	tree.insert('c');
	tree.insert('n');
	tree.insert('g');
	tree.insert('a');
	tree.insert('h');
	tree.insert('e');
	tree.insert('k');
	tree.insert('q');
	tree.insert('m');
	tree.insert('f');

	tree.insert('w');
	tree.insert('l');
	tree.insert('t');
	tree.insert('z');
	tree.insert('d');
	tree.insert('p');
	tree.insert('r');
	tree.insert('x');
	tree.insert('y');
	tree.insert('s');
	tree.remove('n');
	tree.remove('b');
	tree.PrintRow();

}