2-3 tree Algorism bug(memory allocation)

[toby1a05]

i am trying to bulid 2-3 tree insertion function,it seem successfully in the beginning(from 1 to 14),but when i input 15,the output will beocme infinite and the program crashed.I used 3days to debug but still cannot find out the problem(maybe memory allocation?),thx!

#include<stdio.h>
#include<stdlib.h>
#define m 3 //n=number of data,m=max child,rounding up((m-1)/2)-1=<n<=m-1

typedef struct bNode{
	int indegree;
	int data[m];/*data store at most store 2 data and store 3 child;when 3 child ,it will split*/
	struct bNode **pointer[m+1];
	struct bNode **parent;//use 2pointer to store the address of the B;
}bNode;

void printbtree(bNode **B){
	
	if(B==NULL){
	return;	
	}
	
int i=0;

while(i<(*B)->indegree){
printf("%d\n",(*B)->data[i]);
i++;	
}

for(i=0;i<(*B)->indegree+1;i++){
printf("%d:",i);
printbtree((*B)->pointer[i]);	
}

}

void list_Init(int *a){
	int i;
	for(i=0;i<m;i++){
		a[i]=INT_MAX;
	}
}

void AInsertion(bNode **cur,bNode **pre);

void list_Insert(bNode *cur,int *a,bNode ***b,int data,bNode **pre){
	int i,j;	
	for(i=0;i<m;i++){
		if(data<=a[i])
		break;
	}
	for(j=m-1;j>i;j--){
		a[j]=a[j-1];
		b[j+1]=b[j];
	}

	if(!pre)
	cur->indegree++;
	a[i]=data;
	

	b[i]=cur->pointer[0];
	b[i+1]=cur->pointer[1];
	bNode **q=cur->pointer[0];

	
	if(q){
		(*q)->parent=pre;
		
	}
	q=cur->pointer[1];
		if(q){
		(*q)->parent=pre;
	}
	

}
void InitBNode(bNode **N){
(*N)=(bNode*)malloc(sizeof(bNode));

int i;

(*N)->indegree=0;

for(i=0;i<m+1;i++){
(*N)->pointer[i]=NULL;	
}

(*N)->parent=NULL;

list_Init((*N)->data);
}

bNode** B_Tree_Search(bNode **B,bNode*** pre,int ele){
int i=0;

if((*B)==NULL){
	return NULL;
}

while(i<(*B)->indegree){
	if(ele>(*B)->data[i]){
		i++;
	}
	else if (ele<(*B)->data[i]&&(*B)->pointer[i]!=NULL){
		*pre=B;
	
		return B_Tree_Search((*B)->pointer[i],pre,ele);
	}
	else{
		break;
	}
}

if(i==m-1&&(*B)->pointer[i]!=NULL||(*B)->pointer[i]!=NULL){//if the pointer is not null,then can go to the next stage,otherwise stay at the same stage
	*pre=B;

	return B_Tree_Search((*B)->pointer[i],pre,ele);
}
else{
	return B;
}

}

void split(bNode **cur){//e,g, [6,7,8] spilie to (left)<6>,(root)<7>,<8>(right)
bNode **a=(bNode**)malloc(sizeof(bNode*));

InitBNode(a);
(*a)->data[0]=(*cur)->data[0];
(*a)->pointer[0]=(*cur)->pointer[0];
(*a)->pointer[1]=(*cur)->pointer[1];
(*a)->indegree++;

bNode **c=(bNode**)malloc(sizeof(bNode*));
InitBNode(c);
(*c)->data[0]=(*cur)->data[2];
(*c)->pointer[0]=(*cur)->pointer[2];
(*c)->pointer[1]=(*cur)->pointer[3];
(*c)->indegree++;

bNode **b=(bNode**)malloc(sizeof(bNode*));
*b=NULL;
InitBNode(b);
(*b)->data[0]=(*cur)->data[1];
(*b)->pointer[0]=a;
(*b)->pointer[1]=c;
(*b)->indegree++;

(*b)->parent=(*cur)->parent;
(*c)->parent=b;
(*a)->parent=b;


free(*cur);
(*cur)=*b;


if((*cur)->parent){
 

AInsertion(cur,(*cur)->parent);

}

}

void AInsertion(bNode **cur,bNode **pre){//******
	(*pre)->indegree++;

	list_Insert(*cur,(*pre)->data,(*pre)->pointer,(*cur)->data[0],pre);//current node,previous data array,previoud pointer array,previous node



	if((*pre)->indegree==m){

		split(pre);
	}


}

void Insertion(bNode **pre,bNode **cur,int data){
int i,n;

	list_Insert((*cur),(*cur)->data,(*cur)->pointer,data,NULL);//current node,current data array,previous pointer,data,previous node

	if(pre){
	(*cur)->parent=pre;	
	}	
	else{
	(*cur)->parent=NULL;	

	}
			
	

	
	if((*cur)->indegree==m){
		split(cur);
	}


}

void B_Tree_Insertion(bNode **B){//this B not equal to main B
	int data;
	bNode **pre=NULL,**cur=NULL;
	int i; 

	for(i=1;i<30;i++){//<--15 chagne to 16,problem will occur
		pre=NULL;
	cur= B_Tree_Search(B,&pre,i);//pre to store the address of B
	Insertion(pre,cur,i);	



	}
}

int main(){
int choice;
bNode *B=(bNode*)malloc(sizeof(bNode));
InitBNode(&B);


B_Tree_Insertion(&B);
printbtree(&B);
printf("\n\n");


}

[kbw]

Your naming and formatting makes your code unreadable.

However, working thru it, it's a bit of a mess.

To begin with, I assume B is your tree. Clearly, it should be a struct bNode*, not a struct bNode**.

You call InitBNode, but never define it. I expect it should something like be:

void InitBNode(struct bNode** node) {
    *node = (struct bNode*)calloc(1, sizeof(struct bNode));
    if (!*node)
        exit(1);
}

Then you call B_Tree_Insertion, which I would expect to insert a value into the tree, but it doesn't take a value as a parameter, just the tree.

[toby1a05]

thx, i correct it but it still doesn't work, i try to delete line 150free(*cur);, the program stop crash but the output is weird, can you tell me the reason of that?thx a lot!!!

[kbw]

I think you're being a little careless.

Consider main(). You've written:

void list_Init(int *a){
    int i;
    for (i = 0; i < m; i++) {
        a[i] = INT_MAX;
    }
}

void InitBNode(bNode **N) {
    (*N) = (bNode*)malloc(sizeof(bNode));

    int i;

    (*N)->indegree = 0;

    for (i = 0; i < m+1; i++) {
        (*N)->pointer[i] = NULL;	
    }
    (*N)->parent=NULL;

    list_Init((*N)->data);
}

int main() {
    bNode *B=(bNode*)malloc(sizeof(bNode));
    InitBNode(&B);
    // ... 

Why are your variables uppercase? But more importantly, what happens to B in main()?

[toby1a05]

thx all of u, i solve it finally.

[EmmaOlivia]

Windows 7 VS windows 10?
Hallo guys

There is an issue hear i would like to talk about. As most of you might already know Microsoft has already already announced windows 10 a few days ago. I am a windows 7 user and i a have been using it for years now and have got tired of it and i now want a change. I am planning to upgrade to windows 10 once it comes out but my question is will windows 10 be better than windows 7? Or will it be a dumb like windows 8?

I hope some of you may have some idea since you have seen the technical preview Microsoft has released on windows 10 a few days ago .

[kbw]

Please create a new thread in The Lounge as this isn't about programming.