btree.cpp

一个简单的b tree 实现代码

						   if(nm->d==0 &&nm->p[0]==NULL)
							t->p[i]==NULL;
							else
							{
							t1=MergeNode(nl,nm,0);
							 l1=i;
							}
							t->d--;
							}
					   }

					  i=i;

					}

                    if (le==btree_level&& t1!=NULL && root->d<1 ) {
					  root=t1;
					  btree_level--;
					 }

				  if(t->d>0)
				  if(t->p[ l1 ]->d==0 )// 叶子节点中已经为空
				  {  //将该叶子节点从索引中删除

					 if(i>0)
					 DelFromNode(t,l1-1);
					 else
					 DelFromNode(t,l1);
					 //t->d--;
				  }
				  // 比较索引对应的节点第一项是否有与索引对应
				  //有则修改
				  if (t->d>=0 && i<=t->d)
				   if((t->p[ i ]->min!=t->k[i-1] ) &&(i>=1)  )
					 {
					   t->k[i-1]= t->p[ i]->min ;
					   t->v[0]=NULL;
					 }
					 else if(i==0 && t->min!=t->p[0]->min)
					 {
					  t->min =t->p[0]->min ;
					 }
					//当 t->d 小于M时 考虑左移 或右移 到临近节点上，
					//并将父节点中的索引删除

			 }
			 else                     //判断为节点
			{
			if (key == t->k [ i ])
				{
				   if(t->v[ i ]!= NULL)
				   {
						//memset(t->v[i],0x0,20);       //删除节点
							#ifdef key_string
							t->k[ i ]=null_string;
							#else
							t->k[ i ]=0;
							#endif
						free(t->v[i]);
				   }
						DelFromNode(t,i);     //维护父节点索引


					btree_count--;


					t->d--;

					if (t->k[ 0 ]!=t->min)
					 t->min=t->k[ 0 ];
				 }
				 else{
				 printf("key not found\n");
				 }

				}

		


}

btree tree::RebuildIndexNode(btree t)
{
  node p,temp[2*M];
  btree p1,t2;
  p1=&p;
  t2=&temp[0];
  int i,j,k=0,l=0;

  memset(p1,0x0,sizeof(node));
  memset(t2,0x0,sizeof(node));

   memcpy(p1,t,sizeof(node));
  for(i=0;i<=t->d;i++)
  {

   for(j=0;j<t->p[i]->d;j++)
	{
	  t2->p[k]=t->p[i]->p[j];
	  t2->k[k]=t->p[i]->k[j];
	  t2->v[k]=t->p[i]->v[j];

	   t2->d++;
	  if( j==2*M-1)
		t2->p[k+1]=t->p[i]->p[j+1];

	  k++;
	  if(k>=2*M-1)
	  {
	   if(t2->p[0]==NULL)
		t2->min=t2->k[0];
		else
		 t2->min=t2->p[0]->min;
		   t2->p[k+1]=t->p[i]->p[j+1];
	  // memcpy(p1->p[l],t2,sizeof(node));
	   k=0;
	   l++;
	   t2=&temp[l];
	   memset(t2,0x0,sizeof(node));
	  }
	}

  }
  if(t2->d>0)
  { if(t2->p[0]==NULL)
		t2->min=t2->k[0];
		else
		 t2->min=t2->p[0]->min;
	   //memcpy(p1->p[l],&t2,sizeof(node));
	   k=0;
	  // l++;
	  // t2=&temp[l];
	  // memset(&t2,0x0,sizeof(node));
  }
	  for(i=0;i<l;i++)
		memcpy(p1->p[i],&temp[i],sizeof(node));
	 memcpy(t,p1,sizeof(node));
}

float tree::use_rate(btree t)
{
if(t->p[0]=NULL)
 return (t->d/(2*M));//叶子节点占用率

int x=0;
for(int i=0;i<=t->d;i++)
{
x+=t->p[i]->d;
}
return x/((t->d+1)*2*M);//索引节点占用率
}

btree tree::MergeLeafNodeBack(btree t1,btree t2,int d,int l)
{
int i,m,j;
m=d;
	for(i=0;i<d;i++)
	{
		   if(i<t2->d)
			{
				t2->k[i+m]=t2->k[i];
				t2->v[i+m]=t2->v[i];
				t2->p[i+m]=t2->p[i];
			}
			t2->k[i]=t1->k[t1->d-m+i];
			t2->v[i]=t1->v[t1->d-m+i];
			t2->p[i]=t1->p[t1->d-m+i];
            	#ifdef key_string
					t1->k[t1->d-m+i]=null_string;
				#else
				t1->k[t1->d-m+i]=0;
				#endif

			t1->v[t1->d-m+i]=NULL;
			t1->p[t1->d-m+i]=NULL;
	}
	t2->d+=m;
	t1->d-=m;
	return t2;

}

btree tree::MergeLeafNode(btree t1,btree t2,int d,int l)
{
int i,m,j;
  if (d==0)
  if (l>0)
  (2*M+1-t1->d)>t2->d?m=t2->d:m=2*M+1-t1->d;
 else
   (2*M-t1->d)>t2->d?m=t2->d:m=2*M-t1->d;
  else
  m=d;
  j=t1->d;
   for(i=0;i<m;i++)
	{
	 t1->k[j+i]=t2->k[i];
	 t1->v[j+i]=t2->v[i];
	 t1->p[j+i]=t2->p[i];

	}
	t1->d+=m;
	if (t2->d-m>0)
	  for(i=0;i<t2->d-m;i++)
		{
			t2->k[i]=t2->k[i+m];
			t2->v[i]=t2->v[i+m];
			t2->p[i]=t2->p[i+m];
		}


	t2->d-=m;



	if (t2->d>0) t2->min=t2->k[0];
	return  t1;
}

btree tree::MergeNode(btree t1,btree t2,int d)
{
 //将 t2 的数据 移动到t1  若移动后T2没有数据则释放 t2 的空间
 //移动时T1 的最小值要小于 T2
  if(t1->min>t2->min)
  return NULL;

   if(t1->d==0 && t1->p[0]==NULL) t1->min=t2->min;
  int i,j,m;
  if (d==0)
  (2*M-t1->d)>t2->d?m=t2->d:m=2*M-t1->d;
  else
  m=d;
  //判断是否为叶子节点
  if(t1->p[0]!=NULL && t1->d>0 && t2->d>0)
  {
	 j=t1->d+1;
	 for(i=0;i<m;i++)
	{
	 t1->k[j+i]=t2->k[i];
	 t1->v[j+i]=t2->v[i];
	 t1->p[j+i]=t2->p[i];
	 t2->k[i]=t2->k[i+m];
	 t2->v[i]=t2->v[i+m];
	 t2->p[i]=t2->p[i+m];
	}
	 t1->p[j+i]=t2->p[i];
	 t1->k[t1->d] =t2->min;
	 t1->d+=m+1;
	 t2->d-=m;
	//  if(t2->d<=0)
	//  free(t2);
  }
  else
  {
  j=t1->d;
  for(i=0;i<m;i++)
  {
	 t1->k[j+i]=t2->k[i];
	 t1->v[j+i]=t2->v[i];
	 t1->p[j+i+1]=t2->p[i+1];

	 t2->k[i]=t2->k[i+m];
	 t2->v[i]=t2->v[i+m];
	 t2->p[i]=t2->p[i+m];

  }
	 t1->p[j+i+1]=t2->p[i+1];

	 if (t2->d<=0 && t2->p[0]!=NULL) {
	 t1->p[t1->d+1]=t2->p[0];
	  t1->k[t1->d]=t2->min;
	  t1->d++;
	 } else
	 {
	 t1->d+=m;
	 t2->d-=m;
	  }
	 //if(t2->d<=0)
	 //free(t2);
   }
	return t1;

}

/*
* 把一个键和对应的右子树从一个节点中删除
*/
void tree::DelFromNode(btree t, int d)
{
	int i;
	/* 把所有大于要删除的键值的键左移 */
	if (i==2*M) {}
	for(i=d;i <= t->d-1; i++) {
		t->k[ i ] = t->k[i+1];
		t->v[ i ] = t->v[i+1];
		t->p[ i ] = t->p[i+1];
	}


}

btree tree::NewRoot(btree t,btree nt)
{
	btree temp;
	temp = (btree)malloc(sizeof(node));
	memset(temp,0x0,sizeof(node));
	temp->d = 2;
	temp->p[0] = t;
	temp->p[1] = nt;
	temp->k[0] = t->k[0];
	temp->k[1] = nt->k[0];
	temp->v[0] = NULL;
	temp->v[1] = NULL;
	btree_level++;

	/* if(btree_level>1)
			  {
				temp->k[0] =InsKey;
				temp->v[0] = InsValue;
				//temp->p[0]=NewTree;
	}

  /*	if (	nt->p[0]!=NULL)
	 { for(int i=0;i<nt->d;i++)
	  {
		nt->k[i]=nt->k[i+1];
		nt->v[i]=nt->v[i+1];
		nt->p[i]=nt->p[i+1];

	  }
		  nt->d--;
	  }
	*/


	node_sum++;
	return(temp);
}
/*
* 建立有两个子树和一个键的根节点
*/
btree tree::NewRoot(btree t)
{
	btree temp;
	temp = (btree)malloc(sizeof(node));
	memset(temp,0x0,sizeof(node));
	temp->d = 1;
    temp->p[0] = t; 
	temp->p[1] = NewTree;
	temp->k[0] = InsKey;
	temp->v[0] = InsValue;
	btree_level++;
	node_sum++;
	return(temp);
}
/*
* 释放根节点，并返回它的最左子树
*/
btree tree::FreeRoot(btree t)
{
	btree temp;
	temp = t->p[0];
	free(t);
   // btree_level--;
	node_sum--;
	return temp;
}

void tree::Error(int f,typekey key)
{
	if (f==1)
		printf("Btrees error: Insert %d!\n",key);
	else if(f==0)
		printf("Btrees error: delete %d!\n",key);

}

int tree::height(btree t)
{
	return btree_level;
}

int tree::count( )
{
	return btree_count;
}
double tree::payload(btree t)
{
	if (node_sum==0)
		return 1;
	return (double)btree_count/(node_sum*(2*M));
}
btree tree::deltree (btree t)
{
	level=btree_level;
	btree_level = 0;
	delall(t,level);

	root=(btree)malloc(sizeof(node));
	memset(root,0x0,sizeof(node));
	return root;

}

btree tree::delall(btree t,int l)
{


	int i,j,m;

	   for(i=0 ; i<t->d;i++)
	   {


		   if(l==0)
		  if( t->v[i]!=NULL )
			  free(t->v[i]  );
		  else
		   if(t->p[i]!=NULL )
			  delall(t->p[i],l-1);

	   }


	return NULL;
}

int tree::print(  )
{
	 print_tree(root,btree_level);
	return 0;

	}

int tree::print_tree(btree t, int n)
{
	 int i,j,m,l;
	  l=n;


		j=t->d;

		//printf("nc=%d ",t->d );
	   for(i=0 ; i<t->d;i++)
	   {

		  if (l<btree_level)
		  if ((i>0 &&l>0) ||(l==0) )
				{
					 for(m=0;m<btree_level-l;m++)
					   printf("     ");
					   printf("+");


					 for(m=0;m<btree_level-l;m++)
						printf("--");
				}

		   if(l==0)
			  {
			  #ifdef key_string
			  printf("l%d t->k[%d]=%s  v=%s  \n",l,i,t->k [i].c_str(),t->v[i]  );
			  #else
			  printf("l%d t->k[%d]=%d  v=%s  \n",l,i,t->k [i],t->v[i]  );
			  #endif
			  }
			else  if (i>0)
		  {
		   #ifdef key_string
				printf("l%d t->k[%d]=%s  v=%s min=%d\n",l,i-1,t->k [i].c_str(),t->v[i],t->min );
			  #else
		  printf("l%d t->k[%d]=%d  v=%s min=%d\n",l,i-1,t->k [i],t->v[i],t->min );
		  #endif
		  }


		   if(t->p[i]!=0 )
			  print_tree(t->p[i],l-1);




	   }

	 //  if( t->p[t->d]!=NULL )
	 //	 print_tree(t->p[t->d],l-1);


		return i;
	}


tree* menu_do(char c,  tree* t,long n )
{

	//printf("a=add, d=delete, e=empty, f=find, m=menu, p=print, q=quit\n");
	int k,i;
   tree  *t1=t;
	 btree  t_search ;
	switch (c) {
		case 'a':
			{
					char *x=(char*)malloc(20);

					sprintf(x,"%d",n);
					#ifdef key_string
					char b[20];
					sprintf(b,"%d",n);
					 string st;
					  st.assign(b);

					 t->insert(st,t->root,x);
					#else
					t->insert(n,t->root,x);
					#endif
			}
			break;
	   case 'g':
		{  	for(i=10;i<10*n;i+=10)
			{
			#ifdef key_string
					char b[20];
					sprintf(b,"%d",i);
					 string st;
					  st.assign(b);
			t->delete_n(st,t->root);
			#else
			t->delete_n(i,t->root);
			#endif
			}
		}
		break;

		case 'r':
		{
			t->RebuildIndexNode(t->root);
		}
		break;
		case 'x':
		{    char *x;
			for(i=1340000;i<1390000;i+=1)
			{	 x=(char *)malloc(20);
					sprintf(x,"%d",i);
				#ifdef key_string
					char b[20];
					sprintf(b,"%d",i);
					 string st;
					  st.assign(b);
				t->insert(st,t->root,x);
				#else

				t->insert(i,t->root,x);
				#endif
			}
		}
		break;
		case 'b':
		{    	int pos=-1;
			for(i=1340000;i<1390000;i+=1)
			{
				  pos=-1;
				  #ifdef key_string
						char b[20];
						sprintf(b,"%d",i);
						 string st;
						st.assign(b);
						 t_search=t->search(st,t->root,&pos);
					  #else
						t_search=t->search(i,t->root,&pos);
					#endif
			if(pos>=0)
		   {} //	printf("found key pos=%d,k=%d,k0=%d\n",pos,t_search->k[pos],t_search->k[0]);
			else
				printf(" key not found\n");
			}


		}
		break;
		case 't':
		{   char *x;

		  for(i=10;i<10*n;i+=10)
		   //	 for(i=10*n;i>0;i-=10)
			{
				x=(char *)malloc(10);
				if (x!=NULL) {


				sprintf(x,"%d",i);
			   if(i==641)
			   i=i;

				#ifdef key_string
						char b[20]={0};
						sprintf(b,"%d",i);
						 string st;
						st.assign(b);
				t->insert(st,t->root,x);
				#else
			   t->insert(i,t->root,x);
				#endif
			  // if(x!=NULL)
			  // free(x);

				}else{printf("malloc error");}

			}

			i=205;
					#ifdef key_string
			char b[20]={0};
			 char *x1=(char*)malloc(20);
				sprintf(x1,"%d",i);
					sprintf(b,"9test1");
						 string st;
						st.assign(b);
				 t->insert(st,t->root,x1);

					 i=300;
				 x1=(char*)malloc(20);
				sprintf(x1,"%d",i);
					sprintf(b,"8test2");
						// string st;
						st.assign(b);
				 t->insert(st,t->root,x1);

				 x1=(char*)malloc(20);
				sprintf(x1,"tttt" );
					sprintf(b,"7test2");
						// string st;
						st.assign(b);
				 t->insert(st,t->root,x1);

				#endif
			 /*	 char *x1=(char*)malloc(20);
				sprintf(x1,"%d",i);
				 t->insert(i,t->root,x1);

					i=215;
				 x1=(char*)malloc(20);
				sprintf(x1,"%d",i);
				 t->insert(i,t->root,x1);
					i=225;
				 x1=(char*)malloc(20);
				sprintf(x1,"%d",i);
				 t->insert(i,t->root,x1);
					i=235;
				 x1=(char*)malloc(20);
				sprintf(x1,"%d",i);
				 t->insert(i,t->root,x1);

			   */
			 if (t1!=NULL)
			 printf("insert %d\n",n);
			 else
				printf("insert error\n");


			}
			break;
		case 'c':
		 printf("btree count=%d\n",t->count());
			break;
		case 'd':
		   {
		  #ifdef key_string
						char b[20];
						sprintf(b,"%d",i);
						 string st;
						st.assign(b);
				t->delete_n(st,t->root);
				#else
		  t->delete_n(n,t->root);
		  #endif
		   }
			break;
		case 'e':
		{    int pos=-1;
			 char b[20];
			 for(i=10;i<10*n;i+=10)
			 {      pos=-1;
					#ifdef key_string

						sprintf(b,"%d",i);
						 string st;
						st.assign(b);
						 t_search=t->search(st,t->root,&pos);
					 #else
					 t_search=t->search(i,t->root,&pos);
					 #endif
				 if(pos<0)
					printf(" key  %d not found \n",i);

			  }
			}
			break;
		case 'f':
			t->deltree(t->root);
		break;
	  case 's':
			{	int pos=-1;

				#ifdef key_string
						char b[20];
						sprintf(b,"%d",n);
						 string st;
						st.assign(b);
		 t_search=t->search(st,t->root,&pos);
				#else
		 t_search=t->search(n,t->root,&pos);
			 #endif
		if(pos>=0)
			printf("found key pos=%d,k=%d,k0=%d\n",pos,t_search->k[pos],t_search->k[0]);
			else
				printf(" key not found\n");
			}
					break;
		case 'p':
			//printf("level=%d\n",btree_level);

		   t->print( );
			break;
		case 'm':
			printf("a=add, d=delete, e=empty, f=find, m=menu, p=print, q=quit\n");
		default:
			printf("a=add, d=delete, e=empty, f=find, m=menu, p=print, q=quit\n");
			break;
	}

	return t1;
	}


void menu_response(char *c, long *n)
{
	char s[1024];

	printf(">");
	fflush(stdout);
	*n = 0;
	if (fgets(s, sizeof(s), stdin) == NULL)
		*c = 'q';
	else {
		
	 
		*c = *s;
		 
		 if (strlen(s) > 1)
		 *n = atol(s+1);
	}
}

int main(int argc, char ** argv)
{
		char c;
		long n;
		 tree *t;
		 t=new tree();
	//t=	NewRoot(t1);
	do {
		menu_response(&c, &n);
		if (c != 'q')
			menu_do(c, t,n);
	} while (c != 'q');
	   //	t->deltree(t->root);
		return 1;
	exit(0);
	}