btree.cpp

数据结构中B-树经典算法的可视化执行程序

// BTree.cpp : implementation file

#include "stdafx.h"
#include "BTree.h"



//*****************找到给定的关键字要插入的叶结点并返回其指针，若数据重复，则返回NULL******************

BTreeNode * BTree::FindToLeaf(int obj)
{
	BTreeNode *temp=BTreeRoot;
	int pos=0;
	
	while(!temp->IsLeaf()){
		pos=temp->SearchSonNodePos(obj);
		if(pos==-1) return NULL;  //判断关键字是否重复
		temp=temp->SonNode[pos];
	}
	pos=temp->SearchSonNodePos(obj); //查找对应子结点
	if(pos==-1)return NULL;
	return temp;
}



//****************找到给定的关键字所在的结点并返回其指针，若数据不存在，则返回NULL*******************

BTreeNode * BTree::Find(int obj)
{
	BTreeNode *temp=BTreeRoot;
	int pos=0;
	
	while(!temp->IsLeaf()){
		if(temp->Search(obj)!=-1) return temp;
		pos=temp->SearchSonNodePos(obj);
		temp=temp->SonNode[pos];
	}
	
	if(temp->Search(obj)!=-1) 
		return temp;
	else  //关键字不存在
		return NULL;
}




//****************给结点插入关键字,并保证树的结点结构仍然满足B－树定义**************

void BTree::InsertData(BTreeNode *Node,int obj)
{
	BTreeNode *left=NULL,*right=NULL;
	BTreeNode *temp=Node;
	while(1){
		temp->InsertSort(obj,left,right);
		if(!temp->IsFull()) return ;//插入结束

		//插入以后，若结点的关键字已满,进行向上传递关键字的操作
		left=temp;
		obj=left->Data[left->KeyNum/2];
		right=CreatNewNode();
		left->Split(left->KeyNum/2,right);

		if(temp->Parent==NULL){
			temp=CreatNewNode();
			BTreeRoot=temp;  //如果父结点不存在，创造的父结点必定是根结点
		}
		else{
			temp=temp->Parent;
		}
	}	
}




//****************创造一棵B-树*****************

void BTree::CreatTree(int *start,int num)
{
	BTreeNode *temp=NULL;
	for(int i=0;i<num;start++,i++){
		temp=FindToLeaf(*start);
		if(temp!=NULL)  //如果关键字没有重复，插入
			InsertData(temp,*start);
	}
}



//****************插入关键字****************

void BTree::Insert(int obj)
{
	BTreeNode *temp=NULL;
	temp=FindToLeaf(obj);
	if(temp!=NULL)  //如果关键字没有重复则插入
		InsertData(temp,obj);
}



//****************查找关键字是否存在,若存在则返回true*****************

bool BTree::Search(int obj)
{
	BTreeNode *temp=FindToLeaf(obj);
	if(temp==NULL)
		return true;
	else return false;
}



//*****************将左结点，一个关键字，右结点组合并返回组合以后的结点的指针*******************

BTreeNode * BTree::Combine(BTreeNode *left,int mid,BTreeNode *right)
{
	BTreeNode *temp=NULL;
	left->Data.push_back(mid);//先将中间结点插入
	for(int i=left->Data.size(),j=0;j<right->Data.size();i++,j++){
		left->Data.push_back(right->Data[j]);
		temp=right->SonNode[j];
		left->SonNode[i]=temp;
		if (temp!=NULL) temp->Parent=left;//连接父结点
	}
	temp=right->SonNode[j];//针对最后一个关键字的操作
	left->SonNode[i]=temp;
	if (temp!=NULL) temp->Parent=left;
	return left;
}



//*****************删除在非叶子结点上的关键字*****************

void BTree::EraseNoLeaf(BTreeNode *node,int obj)
{
	BTreeNode *temp=NULL;
	int changeData=0;
	int pos=node->Search(obj);
	temp=node->MaxInLeft(pos);
	if(!temp->IsMin()){  //中序前驱结点的关键字大于Min
			changeData=temp->Data[temp->Data.size()-1];
			node->Data[pos]=changeData;
			temp->Remove(changeData);
			return ;    //删除结束
	}
	temp=node->MinInRight(pos);
	if(!temp->IsMin()){ //中序后继结点的关键字大于Min
		changeData=temp->Data[0];
		node->Data[pos]=changeData;
		temp->Remove(changeData);
		return ;       //删除结束
	}
	
	//左右子结点均为最小关键字
	temp=node->MinInRight(pos);
	changeData=temp->Data[0];
	node->Data[pos]=changeData;
	EraseIsMin(temp,changeData);
}



//*****************删除结点中指定关键字***********************

void BTree::EraseData(BTreeNode *node,int obj)
{
	if(!node->IsLeaf()){ //不是叶结点
		EraseNoLeaf(node,obj);
	}
	else{ //叶结点
		//关键字不是最小,或删除的是叶子根结点
		if(node->Data.size() > node->Min || node->Parent==NULL)
			node->Remove(obj);
		else
			EraseIsMin(node,obj);
	}
}


//*********************删除关键字个数等于Min的结点中的关键字*************************

void BTree::EraseIsMin(BTreeNode *node,int obj)
{
	BTreeNode *temp=node;
	BTreeNode *parent=temp->Parent;
	int changeData=0;	
	BTreeNode *left=NULL;
	BTreeNode *right=NULL;
	int pos=parent->SearchPos(node);//查找目标结点在其父结点中位置
	//如果左兄弟关键字个数大于Min
	if(!parent->LeftIsMin(pos-1)){
		left=parent->SonNode[pos-1];
		//将父结点parent->Data[pos-1]传递到目标结点
		node->Remove(obj);
		node->InsertSort(parent->Data[pos-1],NULL,NULL);
		//将左结点最大值覆盖parent->Data[pos-1]
		int deletePos=left->Data.size()-1;
		parent->Data[pos-1]=left->Data[deletePos];
		left->Data.pop_back();//删除左子结点最大值
		return ;//删除结束
	}
	//如果右兄弟关键字数目大于Min
	if(!parent->RightIsMin(pos+1)){
		right=parent->SonNode[pos+1];
		//将父结点parent->Data[pos]传递到目标结点
		node->Remove(obj);
		node->InsertSort(parent->Data[pos],NULL,NULL);
		//将右结点最小值覆盖parent->Data[pos]
		parent->Data[pos]=right->Data[0];
		right->Data.erase(right->Data.begin());//删除右子结点最小值
		return ;//删除结束
	}
	//左右兄弟结点关键字数目均为最小值
	temp->Remove(obj);
	while(temp!=NULL){
		if(temp->IsLessThanMin()){
			temp=CombineAndLink(temp);
		}
		else return;
	}
}



//*******************组合相应结点并连接其父结点************************

BTreeNode * BTree::CombineAndLink(BTreeNode * obj){
	BTreeNode *temp;
	BTreeNode *parent=obj->Parent;
	
	int pos=parent->SearchPos(obj);
	//左兄弟不存在
	if(pos==0)
		pos++;
	//将obj左兄弟和其父结点中序后继关键字，以及obj本身组合
	temp=Combine(parent->SonNode[pos-1],parent->Data[pos-1],
				parent->SonNode[pos]);

	parent->Remove(parent->Data[pos-1]);//从父结点删除被temp组合的关键字
	parent->SonNode[pos-1]=temp;//连接组合后的子结点
	temp->Parent=parent;
	for(int i=pos;i<=parent->Data.size();i++){//移动子结点指针
		parent->SonNode[i]=parent->SonNode[i+1];
	}

	if(temp->IsFull()){//当合并以后的结点不符合规范时,将结点分离
			BTreeNode *right=CreatNewNode();
			int mid=temp->Data[temp->KeyNum/2];
			temp->Split(temp->KeyNum/2,right);
			parent->InsertSort(mid,temp,right);
	}
	if(parent->IsLessThanMin() && parent->Parent==NULL){//当parent已经是根结点
		if(parent->Data.size()==0){//父结点可能为空
			BTreeRoot=parent->SonNode[0];
			BTreeRoot->Parent=NULL;
			return NULL;
		}
		BTreeRoot=parent;
		BTreeRoot->Parent=NULL;
		return NULL;
	}
	return parent;
}