bminustree.cpp

b-树的增加,因为我看到的资料里的最大关键字数目为m-1,我考虑了一下,2-3树的删除会比较麻烦,后来看了下算法导论,别人的数目是2t-1,所以相同情况下是2-3-4树,我考虑按照这个因子再写一个,增

//三月五号于上海交通大学,只写了增加算法,关键字最大数目是M-1(M阶b-树),我觉得这样的最大关键字数目有问题//
//刚刚翻看了算法导论里面的定义果然不一样,那里的t=(int)((M+1)/2);而最大的关键字为2t-1//
//所以对于3阶树来说一个是2-3树,一个是2-3-4树,我考虑了一下,对于删除来说相差很大,我准备再按照那个定义写,会增加删除部分
//有兴趣可以联系我,联系方式是[e-mail],我不保证都能给予回复//
#include "bMinusNode.h"
#include "bMinusTree.h"

template<typename X>
void bMinusTree<X>::insert(X value)
{
	if(!head)
	{
		bMinusNode<X> *newNode=new bMinusNode<X>;
		newNode->count=1;
		head=newNode;
		newNode->key[0]=value;//第一个关键字空着
		return;
	}
	if(!head->child[0])
	{
		if(head->count<M-1)
		{
			int i=0;
			while(head->key[i]<value&&i<head->count)
				i++;
			for(int j=head->count;j>=i;j--)
			{
				head->key[j+1]=head->key[j];
			}
			head->key[i]=value;
			head->count++;
		}
		else
		{
			bMinusNode<X> *newNode=new bMinusNode<X>,*p;
			p=head;
			newNode->count=1;
			newNode->child[0]=head;
			p->father=newNode;
			head=newNode;
			newNode=new bMinusNode<X>;
			head->child[1]=newNode;
			newNode->father=head;
			bool flag=0;
			for(int i=0;i<SIZEOFSECOND;i++)
			{
				if(flag||p->key[M-i-1]>value)
				{
					newNode->key[SIZEOFSECOND-i-1]=p->key[M-i-1];
					p->key[M-i-1]=0;
				}
				else
				{
					newNode->key[SIZEOFSECOND-i-1]=value;
					flag=1;
				}
			}
			if(!flag)
			{
				if(p->key[M-i-1]>value)
				{
					head->key[0]=p->key[M-i-1];
					p->key[M-i-1]=0;
				}
				else
				{
					head->key[0]=value;
					flag=1;
				}
			}
			else
			{
				head->key[0]=p->key[M-i-1];
				p->key[M-i-1]=0;
			}
			if(!flag)
			{
				for(i=SIZEOFFIRST-2;p->key[i]>value&&i>=0;i--)
					;
				for(int j=SIZEOFFIRST-2;j>=i;j--)
					p->key[j+1]=p->key[j];
				p->key[i]=value;
			}
			p->count=SIZEOFFIRST;
			newNode->count=SIZEOFSECOND;
		}
	}
	else
	{
		bool flag;
		int place;
		bMinusNode<X> *p=find(value,flag,place);
		if(flag) //数据已经存在在树中
			return; 
		for(int i=0;p->key[i]<value&&i<p->count;i++)
			;
		for(int j=p->count-1;j>=i;i--)
			p->key[j+1]=p->key[j];
		p->key[i]=value;
		p->count++;
		while(p->count==M)
		{
			bMinusNode<X> *newNode=new bMinusNode<X>;
			newNode->father=p->father;
			for(i=0;i<SIZEOFSECOND;i++)
			{
				newNode->key[SIZEOFSECOND-i-1]=p->key[M-i-1];
				newNode->child[SIZEOFSECOND-i]=p->child[M-i];
				if(p->child[M-i])
					p->child[M-i]->father=newNode;
				p->key[M-i-1]=0;
				p->child[M-i]=0;
			}
			newNode->child[SIZEOFSECOND-i]=p->child[M-i];
			if(newNode->child[SIZEOFSECOND-i])
				newNode->child[SIZEOFSECOND-i]->father=newNode;
			p->child[M-i]=0;
			value=p->key[SIZEOFFIRST];
			p->key[SIZEOFFIRST]=0;
			p->count=SIZEOFFIRST;
			newNode->count=SIZEOFSECOND;
			if(p!=head)
			{
				bMinusNode<X> *q=p;
				p=p->father;
				for(i=0;i<p->count&&p->key[i]<value;i++)
					;
				for(j=p->count-1;j>=i;j--)
				{
					p->key[j+1]=p->key[j];
					p->child[j+2]=p->child[j+1];
					if(p->child[j+2])
						p->child[j+2]->father=p;
				}
				p->key[i]=value;
				p->child[i+1]=newNode;
				if(p->child[i+1])
					p->child[i+1]->father=p;
				p->child[i]=q;
				if(p->child[i])
					p->child[i]->father=p;
				p->count++;
			}
			else
			{
				bMinusNode<X> *newHead=new bMinusNode<X>;
				newHead->key[0]=value;
				newHead->child[0]=p;
				//newHead->child[0]->father=newHead;
				newHead->child[1]=newNode;
				//newHead->child[1]->father=newHead;
				p->father=newHead;
				newNode->father=newHead;
				head=newHead;
				newHead->count=1;
			}
		}
	}
}

template<typename X>
void bMinusTree<X>::traverse(bMinusNode<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>
bMinusNode<X>* bMinusTree<X>::find(X value,bool &flag,int &place)//flag表示是否树中有这个数据,1是,0否
{
	if(!head)
		return 0;
	bMinusNode<X> *p=head;
	while(p)
	{
		for(int i=0;p->key[i]<=value&&i<p->count;i++)
		{
			if(p->key[i]==value)
			{
				flag=1;
				return p;
			}
		}
		if(p->child[i])
		{
			p=p->child[i];
			continue;
		}
		if(i==p->count||value!=p->key[i])
		{
			flag=0;
			place=i;
			return p;
		}
		else
		{
			flag=1;
			return p;
		}
	}
}