bminustree.cpp

b-树的增加,删除,已对八百万个数据进行过测试,而且是对多个M值

#include "bMinusTree.h"
#include "bMinusTreeNode.h"

template<typename X>
void CBMinusTree<X>::Traverse(CBMinusTreeNode<X> *treehead)
{
	if(!treehead)
		return;
	for(int i=0;i<treehead->count;i++)
	{
		Traverse(treehead->child[i]);
		cout<<treehead->key[i]<<endl;
	}
	Traverse(treehead->child[i]);
}

template<typename X>
CBMinusTreeNode<X>* CBMinusTree<X>::Find(X value, bool &flag)
{
	flag=0;
	CBMinusTreeNode<X> *p=head;
	while(p)
	{
		for(int i=0;i<p->count&&p->key[i]<value;i++)
			;
		if(i<p->count&&p->key[i]==value)
		{
			flag=1;
			return p;
		}
		if(!p->child[i])
		{
			return p;
		}
		p=p->child[i];
	}
	return 0;
}

template<typename X>
int CBMinusTree<X>::InsertKey(CBMinusTreeNode<X> *addr,X value)
{
	if(!addr||value==FORBIDENKEY||addr->count==2*T)
		return -1;
	for(int i=0;i<addr->count&&addr->key[i]<value;i++)
		;
	for(int j=addr->count-1;j>=i;j--)
	{
		addr->key[j+1]=addr->key[j];
		addr->child[j+2]=addr->child[j+1];
	}
	addr->key[i]=value;
	addr->count++;
	return i;
}

template<typename X>
void CBMinusTree<X>::Insert(X value)
{
	if(value==FORBIDENKEY)
		return;
	if(!head)
	{
		CBMinusTreeNode<X> *newNode=new CBMinusTreeNode<X>;
		newNode->key[0]=value;
		newNode->count++;
		head=newNode;
		return;
	}
	bool flag;
	CBMinusTreeNode<X> *addr=Find(value,flag);
	if(flag)
	{
		cout<<"The data of :"<<value<<" already exist."<<endl;
		return;
	}
	InsertKey(addr,value);
	while(addr->count==2*T)
	{
		CBMinusTreeNode<X> *newNode=new CBMinusTreeNode<X>;
		X tempX=Split(addr,newNode);
		if(addr!=head)
		{
			CBMinusTreeNode<X> *parent=addr->father;
			int place=InsertKey(parent,tempX);
			parent->child[place]=addr;
			parent->child[place+1]=newNode;
			newNode->father=parent;
			addr=parent;
		}
		else
		{
			CBMinusTreeNode<X> *newHead=new CBMinusTreeNode<X>;
			newHead->child[0]=addr;
			addr->father=newHead;
			newHead->child[1]=newNode;
			newNode->father=newHead;
			newHead->key[0]=tempX;
			newHead->count++;
			head=newHead;
		}
	}
}

//返回值为需向上提交的值,即合并到上一层的值
template<typename X>
X CBMinusTree<X>::Split(CBMinusTreeNode<X> *original, CBMinusTreeNode<X> *newNode)
{
	for(int i=0;i<SIZEOFSECOND;i++)
	{
		newNode->key[SIZEOFSECOND-i-1]=original->key[2*T-i-1];
		original->key[2*T-i-1]=FORBIDENKEY;
		newNode->child[SIZEOFSECOND-i]=original->child[2*T-i];
		if(newNode->child[SIZEOFSECOND-i])
			newNode->child[SIZEOFSECOND-i]->father=newNode;
		original->child[2*T-i]=0;
	}
	newNode->child[0]=original->child[2*T-i];
	original->child[2*T-i]=0;
	if(newNode->child[0])
		newNode->child[0]->father=newNode;
	X temp;
	temp=original->key[T-1];
	original->key[T-1]=FORBIDENKEY;
	original->count=SIZEOFFIRST;
	newNode->count=SIZEOFSECOND;
	return temp;
}

template<typename X>
void CBMinusTree<X>::DeleteKeyInLeaf(CBMinusTreeNode<X> *leaf,const int place)
{
	//如果没有不是叶子或者此指针不存在则返回
	if(!leaf||leaf->child[0])
		return;
	for(int i=place;i<=leaf->count-2;i++)
	{
		leaf->key[i]=leaf->key[i+1];
	}
	leaf->key[--leaf->count]=FORBIDENKEY;
}

template<typename X>
void CBMinusTree<X>::Del(X value)
{
	if(value==1460)
		int c=5;
	bool flag;
	CBMinusTreeNode<X> *addr=Find(value,flag),*p,*q;
	if(!flag)
	{
		cout<<"The data of "<<value<<" is not exist!"<<endl;
		return;
	}
	for(int i=0;i<addr->count&&value>addr->key[i];i++)
		;
	if(addr->child[0])//如果所删除的不是叶子结点中的值
	{
		p=head;
		while(p&&p!=addr->father)
		{
			i=0;
			for(;i<p->count&&value>p->key[i];i++)
				;
			if(p->child[0])
				q=p->child[i];
			if(q->count<T)
				Merge(p,i);
			addr=Find(value,flag);
			CBMinusTreeNode<X> *x=p;
			p=p->child[i];
			
		}	
		for(int i=0;i<addr->count&&value>addr->key[i];i++)
			;
		if(addr->child[i]->count>=T)//左树中有够多的结点可以用
		{
			p=addr->child[i];
			while(p->child[0])
			{
				if(p->child[p->count]->count<T)
				{
					Merge(p,p->count-1);
				}
				p=p->child[p->count];
			}
			addr->key[i]=p->key[p->count-1];
			DeleteKeyInLeaf(p,p->count-1);
		}
		else
		{
			if(addr->child[i+1]->count>=T)//右树中有够多的结点可以用
			{
				p=addr->child[i+1];
				while(p->child[0])
				{
					if(p->child[0]->count<T)
					{
						Merge(p,0);
					}
					p=p->child[0];
				}
				addr->key[i]=p->key[0];
				DeleteKeyInLeaf(p,0);
			}
			else//左右树中的结点都不够多,合并
			{
				Merge(addr,i);
				Del(value);
				return;
			}
		}
	}
	else
	{
		if(addr==head)//只有一个结点的情况
		{	
			for(int j=i;j<addr->count-1;j++)
			{
				addr->key[j]=addr->key[j+1];
			}
			addr->key[addr->count-1]=FORBIDENKEY;
			addr->count--;
			if(!addr->count)//整棵树都被删除干净了
			{
				delete(addr);
				head=0;
			}
			return;
		}
		//不是只有一个根结点而且所删元素存在于叶子中
		addr=head;
		while(addr&&addr->child[0])
		{
			for(i=0;i<addr->count&&value>addr->key[i];i++)
				;
			p=addr->child[i];
			if(p->count<T)
			{
				int j=i;
				if(i==addr->count)
					j=i-1;
				CBMinusTreeNode<X> *tempAddr=Merge(addr,j);
				if(tempAddr)
					addr=tempAddr;
			}
			for(i=0;i<addr->count&&value>addr->key[i];i++)
				;
			addr=addr->child[i];
		}
		if(!addr)
			addr=head;
		for(i=0;i<addr->count&&value>addr->key[i];i++)
			;
		DeleteKeyInLeaf(addr,i);
	}
}

template<typename X>
CBMinusTreeNode<X>* CBMinusTree<X>::Merge(CBMinusTreeNode<X> *father,const int place)
{
	if(!father||!father->child[0]||place<0||place>father->count-1)
		return 0;
	CBMinusTreeNode<X> *leftChild=father->child[place];
	CBMinusTreeNode<X> *rightChild=father->child[place+1];
	//左树和右树以及一个关键字合并
	if(leftChild->count<T&&rightChild->count<T)
	{
		leftChild->key[leftChild->count]=father->key[place];
		//把关键字和右树移到左树中,要注意右树的子女所指向的父亲要改为左树
		for(int i=0,j=leftChild->count+1;i<rightChild->count;i++)
		{
			leftChild->key[j+i]=rightChild->key[i];
			leftChild->child[j+i]=rightChild->child[i];
			if(leftChild->child[j+i])
				leftChild->child[j+i]->father=leftChild;
		}
		leftChild->child[j+i]=rightChild->child[i];
		if(leftChild->child[j+i])
			leftChild->child[j+i]->father=leftChild;
		delete(rightChild);
		//把父结点中关键字后面的关键字和指针前移一位
		for(i=place;i<father->count-1;i++)
		{
			father->key[i]=father->key[i+1];
			father->child[i+1]=father->child[i+2];
		}
		father->key[i]=FORBIDENKEY;
		father->key[i+1]=0;
		father->count--;
		leftChild->count=2*T-1;
		if(father->count>=1)
			return father;
		//如果合并是对父结点,左子树结点和右子树结点三个结点进行的,则要处理与父结点的父亲间的指向关系
		if(!father->father)
		{
			delete(head);
			head=leftChild;
			leftChild->father=0;
			return leftChild;
		}
		CBMinusTreeNode<X> *grandfather=father->father;
		leftChild->father=grandfather;
		for(i=0;i<=grandfather->count&&grandfather->child[i]!=father;i++)
			;
		grandfather->child[i]=leftChild;
		return 0;
	}
	//左树有足够兄弟,右树不足
	if(father->child[place]->count>=T)
	{
		for(int i=rightChild->count-1;i>=0;i--)
		{
			rightChild->key[i+1]=rightChild->key[i];
			rightChild->child[i+2]=rightChild->child[i+1];
		}
		rightChild->child[1]=rightChild->child[0];
		rightChild->key[0]=father->key[place];
		rightChild->child[0]=leftChild->child[leftChild->count];
		if(rightChild->child[0])
			rightChild->child[0]->father=rightChild;
		rightChild->count++;
		father->key[place]=leftChild->key[leftChild->count-1];
		leftChild->key[leftChild->count-1]=FORBIDENKEY;
		leftChild->child[leftChild->count--]=0;
		return 0;
	}
	//右树有足够兄弟,左树不够
	leftChild->key[leftChild->count++]=father->key[place];
	leftChild->child[leftChild->count]=rightChild->child[0];
	if(leftChild->child[leftChild->count])
		leftChild->child[leftChild->count]->father=leftChild;
	father->key[place]=rightChild->key[0];
	for(int i=0;i<rightChild->count-1;i++)
	{
		rightChild->key[i]=rightChild->key[i+1];
		rightChild->child[i]=rightChild->child[i+1];
	}
	rightChild->child[i]=rightChild->child[i+1];
	rightChild->key[rightChild->count-1]=FORBIDENKEY;
	rightChild->child[rightChild->count--]=0;
	return 0;
}

template<typename X>
int CBMinusTree<X>::IsBMinusTree(CBMinusTreeNode<X> *treehead,int h)
{
	if(!treehead)
		return 0;
	h++;
	if(!treehead->child[0])
	{
		if(!height)
		{
			height=h;
			return 1;
		}
		else
		{
			if(height==h)
				return 1;
			else
				return -1;
		}
	}
	for(int i=0;i<=treehead->count;i++)
	{
		if(IsBMinusTree(treehead->child[i],h)==-1)
			return -1;
	}
	return 1;
}