fttree.cpp

是当初的数据结构的做业,用的是b+树这一块,非常值得初学者的参考

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

#include "stdafx.h"
#include "索引技术.h"
#include "FTTree.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

FTTree::FTTree()
{

}

FTTree::~FTTree()
{

}
/*void FTTree::printnode(FTNode *node)
{if(node==NULL) return;
if(node->lkey!=EMPTY)
cout<<node->lkey<<"|"<<node->ckey<<"|"<<node->rkey<<"     ";
cout<<"!!!!!!!!!!";
if(node->lkey!=EMPTY )
{
printnode(node->left);
printnode(node->lcenter);cout<<"@@@@@@@@@@";
}
else
return;
if(node->ckey!=EMPTY)
printnode(node->rcenter);
else
return;
cout<<"###########";

if(node->rkey!=EMPTY)
printnode(node->right);
else
return;
cout<<"$$$$$$$$$$$";
cout<<endl;
cout<<endl;
cout<<endl;
}*/

bool FTTree::splitenode(FTNode*& subroot,const int & inval ,FTNode *inptr,int & retval, FTNode*& retptr)
{  
	retptr =new FTNode;
    if(inval <subroot->lkey)
	{
		 retval=subroot->ckey;subroot->ckey=subroot->lkey;subroot->lkey=inval;
		 
         retptr->lkey=subroot->rkey;
         retptr->left=subroot->rcenter;retptr->lcenter=subroot->right;
		 subroot->rcenter=subroot->lcenter;subroot->lcenter=inptr;
		 
	}
	else if(inval < subroot->ckey)
	{
       retval=subroot->ckey;
	   subroot->ckey=inval;
       subroot->lcenter=inptr;
	   retptr->left=subroot->rcenter;
       retptr->lkey=subroot->rkey;
       retptr->lcenter=subroot->right;
	}


    else if(inval < subroot->rkey)
	{
	   retval=inval;retptr->left=inptr;
	   retptr->lcenter=subroot->right;retptr->lkey=subroot->rkey;
	}
    else if(inval>subroot->rkey)
	{  
		retval=subroot->rkey;retptr->left=subroot->right;
        subroot->rkey=inval;retptr->lkey=subroot->rkey;
        retptr->lcenter=inptr;
	}
    subroot->rkey=EMPTY;
	return true;

}

bool FTTree::insert(FTNode*& subroot,const int & e ,int &retval, FTNode*& retptr)
{
	int  myretv=0;FTNode * myretp=NULL;
	
	if(subroot->isleaf())
	{
		
	if(subroot->lkey==EMPTY)
				subroot->lkey=e;
	else if(subroot->ckey==EMPTY)
			{
				 if (e >subroot->lkey)  subroot->ckey=e;
			     else if (e<subroot->lkey) 
				 {
					 subroot->ckey=subroot->lkey;
				     subroot->lkey=e;
				 }
			}
	else if (subroot->rkey==EMPTY)
			{    
				 if(e< subroot->lkey)
				 {
				 subroot->rkey=subroot->ckey;
				 subroot->ckey=subroot->lkey;
				 subroot->lkey=e;
				 }
				 else if (e >subroot->lkey && e< subroot->ckey)
				 {
					 subroot->rkey=subroot->ckey;
				     subroot->ckey=e;

				 }

				 else if (e >subroot->ckey)
				 {
					 subroot->rkey=e;
					 
				 }
			 }
			 else  
				 splitenode(subroot,e,NULL,retval,retptr);
	}
		
 	else 
	{
		if (e < subroot->lkey)
		   insert(subroot->left,e,myretv,myretp);
		else if(subroot->ckey==EMPTY || subroot->ckey >e)
		   insert(subroot->lcenter,e,myretv,myretp);
		else if(subroot->rkey==EMPTY || e < subroot->rkey)
		   insert(subroot->rcenter,e,myretv,myretp);
		else if(e>subroot->rkey)
		   insert(subroot->right,e,myretv,myretp);
	}
	if(myretp!=NULL)
	{
	if(subroot->ckey==EMPTY)
	{
		if(myretv >subroot->lkey)
		{
				subroot->ckey=myretv;subroot->rcenter=myretp;
		}
	   else if(myretv<subroot->lkey)
	   {      
				subroot->ckey=subroot->lkey;
				subroot->lkey=myretv;
				
				subroot->rcenter=subroot->lcenter;
				subroot->lcenter=myretp;
			}
	}
	else if(subroot->rkey==EMPTY)
		{
			if(myretv< subroot->lkey)
			{  
				subroot->rkey=subroot->ckey;
				subroot->ckey=subroot->lkey;
				subroot->lkey=myretv;
				subroot->right=subroot->rcenter;
				subroot->rcenter=subroot->lcenter;
				subroot->lcenter=myretp;
			}
			else if(myretv<subroot->ckey)
			{
				subroot->rkey=subroot->ckey;
				subroot->right=subroot->rcenter;
				subroot->ckey=myretv;
				subroot->rcenter=myretp;
			}
			else if(myretv>subroot->ckey)
			{
				subroot->rkey=myretv;
				subroot->right=myretp;
			}
	} 
			else if(subroot->rkey!=EMPTY)
                splitenode (subroot,myretv,myretp,retval,retptr);
		}
	
	  return true;

}