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();

}