btree.cpp

这些程序是本人学习数据结构时编的

// Mtree.cpp: implementation of the Mtree class.
//
//////////////////////////////////////////////////////////////////////

#include "Btree.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
template<class Type>
Btree<Type>::Btree()
{

}

template<class Type>
Btree<Type>::~Btree()
{

}


template<class Type>
void Btree<Type>::insertkey(Mnode<Type> *p,int j,Type K, Mnode<Type> * ap ,int num)
{
	int i = p->n;
	p->n++;
	while( i >= j)
	{
		p->key[i+1] = p->key[i];
		p->num[i+1] = p->num[i];
		p->ptr[i+1] = p->ptr[i];
		i--;
	}
	p ->key[j] = K; p->ptr[j]= ap;p->num[j] = num;
	return;
}

template<class Type>
int Btree<Type>:: Search()
{
	Type x;
	cout<<"输入要查找的键值:";
	cin>>x;
	Triple<Type> loc = Mtree<Type>::Search(x);
	if (loc.tag)
	{ 
		cout<<"没有此数据"<<endl;
		return 0;
	}
	cout<<"对应值为:"<<loc.r->num[loc.i]<<endl;
	return 1;
}


template<class Type>
void Btree<Type>::move( Mnode<Type> *p, Mnode<Type> *q, int s, int m)
{
	int i;
	q->ptr[s-1] = p->ptr[m];
	for (i = 1; i<s ; i++)
	{
		q->key[i] = p->key[s+i];
		q->num[i] = p->num[s+i];
		q->ptr[i-1] = p->ptr[i + s - 1];
		if ( q->ptr[i-1] != NULL )
			q->ptr[i-1]->parent = q;
	}
	p -> n = s-1;
	q -> n = m-s;
};

template<class Type>
int Btree<Type>::Insert(const Type &x ,int num)
{
	Triple<Type> loc = Mtree<Type>::Search(x);		//找x的位置
	if (!loc.tag) return 0;							//找到,不再插入
	Mnode<Type> * p = loc.r, * q;					//未找到,插入
	Mnode<Type> * ap = NULL, * t;
	Type K= x; int j= loc.i;
	while(1)
	{
		if ( p-> n < m-1)							//当前结点未满
		{
			insertkey (p, j, K, ap ,num);			//(K,ap)插入 j后
			return 1;
		}			
		int s = (m+1) /2;							//结点已满,分裂,求 m/2
		insertkey(p,j ,K ,ap ,num);					//(K,ap)插入 j后
		q= new Mnode<Type>(m);						//建立新结点
		move (p,q,s,m);								//从 p向q 搬送

		K= p->key[s] ; ap = q;						//分界关键码上移
		if (p->parent != NULL)						//双亲结点不是根 
		{
			t = p -> parent;
			j = 1; 
			t -> key[(t->n) +1] = MAXKEY;
			while( t->key[j]<K) j++;				//找插入点
			q -> parent = p->parent;
			p= t;
		}else{										//双亲是根
			root = new Mnode<Type>(m);				//创建新根
			root -> n= 1;
			root ->parent = NULL;
			root ->key[1] = K;
			root ->num[1] = num;
			root -> ptr[0] = p;
			root -> ptr[1] = ap;
			q-> parent = p->parent = root;
			return 1;
		}
	}
}




template<class Type> int Btree<Type>::Delete()
{
	Type x;
	cout<<"输入要删除的键值:";
	cin>>x;
	Triple<Type> loc = Mtree<Type>::Search(x);		//搜索x
	if (loc.tag) return 0;							//未找到,不删除
	Mnode <Type> *p = loc.r , * q ,* s;				//找到,删除
	int j = loc.i;
	if (p-> ptr[j] != NULL)							//非叶结点
	{
		s = p-> ptr[j];q= p;
		while (s != NULL)							//从叶结点替补
		{
			q = s; s= s->ptr[0];
		}
		p -> key[j] = q ->key[1];
		p -> num[j] = q ->num[1];
		compress(q,1);								//在叶结点删除
		p= q;										//转化为叶结点的删除
	}else compress (p ,j);							//叶结点,直接删除
	int d= (m+1) /2;								//求 [m/2]

	while (1)										//调整或合并
	{
		if (p-> n< d-1)								//小于最小限制
		{
			j= 0; q= p->parent;						//找到双亲
			while(j <= q ->n && q->ptr[j] != p) j++;
			if (!j) LeftAdjust (p,q,d,j);			//调整
			else RightAdjust (p,q,d,j) ;			//向上调整  
			p = q;
			if (p == root ) break;
		}else break;
	}
	if (! root->n)									//调整后根的n减到0
	{
		p = root -> ptr[0] ; delete root;			//删根
		root = p; root ->parent = NULL;				//新根
	}
};

template<class Type> 
void Btree<Type>::LeftAdjust( Mnode<Type> * p, Mnode<Type> * q, int d,int j)
{
	Mnode<Type> * p1 = q ->ptr[1];
	if (p1->n > d-1)
	{
		(p-> n)++;
		p ->key[p->n] = q ->key[1];
		p ->num[p->n] = q ->num[1];
		q ->key[1] = p1 -> key[1];
		q ->num[1] = p1 -> num[1];
		p -> ptr[p->n] = p1 -> ptr[0];
		p1 ->ptr[0] = p1-> ptr[1];
		compress (p1,1);
	}else merge(p,q, p1,1);
};    

template<class Type> 
void Btree<Type>::RightAdjust( Mnode<Type> * p, Mnode<Type> * q, int d,int j)
{
	Mnode<Type> * p1 = q ->ptr[j-1];
	if (p1->n > d-1)
	{
		for (int i= p->n; i>=0 ; i--)
		{
			p->key[i+1] = p->key[i];
			p->num[i+1] = p->num[i];
			p->ptr[i+1] = p->ptr[i];
		};
		(p-> n)++;
		p ->key[1] = q ->key[j];
		p ->num[1] = q ->num[j];
		q ->key[j] = p1 -> key[p1->n];
		q ->num[j] = p1 -> num[p1->n];
		p ->ptr[0] = p1 -> ptr[p1->n];
		compress (p1,1);
	}else merge(p,q, p1,j);
};

template<class Type> void Btree<Type>::compress (Mnode<Type> * p,int j)
{
	for (int i = j ; i< p->n; i++)
	{
		p ->key[i] = p-> key[i+1];
		p ->num[i] = p -> num[i+1];
		p-> ptr[i] = p -> ptr[i+1];
	}
	p->n --;
}

template<class Type> void Btree<Type>::merge(Mnode<Type> * p ,Mnode <Type> * q ,Mnode<Type> * p1, int j)
{
	p ->key[(p->n)+1] = q ->key[1];
	p ->num[(p->n)+1] = q ->key[1];
	p ->ptr[(p->n)+1] = p1 ->ptr[0];
	for (j =1 ; j<= p1 ->n; j++)
	{
		p ->key[(p->n) +j+1 ] = p1 ->key[j];
		p ->num[(p->n) +j+1 ] = p1 ->num[j];
		p ->ptr[(p->n) +j+1] =  p1 ->ptr[j];
	}
	compress(q,j);
	p ->n = p ->n + p1->n +1;
	delete p1;
}