creating general b tree. can't find the damn bug!

koopey (160)
I can't find the error no matter how hard I try. Error starts if no of input >=4.
know shouldn't post entire code but don't know where is the error. so...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 
#include <iostream>
using namespace std;
const int d=1;
typedef
struct btnode
{
	int c;
	int keys[2*1+1];
	btnode* childptr[2*1+2];
}* btptr;
void inssort(btptr temp,int key, btptr &root,btptr newnode);

void overflow(btptr T,btptr &root)
{
	btptr N=new struct btnode, temp=root;

	int j, k,tag=0;
    N->c=0;
	for(int i=0;i<2*1+2;i++)
	N->childptr[i]=NULL;
	int median=d+1;
	k=median;
	for(j=0;k<2*1+1 ;j++)
	{
		N->keys[j]=T->keys[k];N->c++;
		N->childptr[j]=T->childptr[k];k++;
	}
	N->childptr[j]=T->childptr[k];
	T->c=d;

	if(T==root)
	{
		btptr B=new struct btnode;B->c=0;
		for(int l=0;l<2*1+2;l++)
		B->childptr[l]=NULL;
		B->childptr[0]=T;
		B->childptr[1]=N;
		B->keys[0]=T->keys[median-1];B->c++;
		root=B;
	}
	else
	{
		j=0;
		while(tag==0)
		{
			for( j=0;j<temp->c;j++)
			{
				if(T->keys[0]<temp->keys[j])
				{if(temp->childptr[j]==T)
				 {break;tag=1;}
				 else
				 {temp=temp->childptr[j];break;
				 }
				}
			}
		}
		inssort(temp,T->keys[median-1],root,N);
		if(temp->c>2*1)
		overflow(temp,root);
	}
}

void inssort(btptr temp,int key, btptr &root,btptr newnode)
{	int i;
	for(i=temp->c-1;i>=0;i--)
	{if(key<temp->keys[i])
	 {temp->keys[i+1]=temp->keys[i];
	  temp->childptr[i+2]=temp->childptr[i+1];
	 }
	 else
	 break;
	}
	temp->keys[i+1]=key;
	temp->childptr[i+2]=newnode;
	temp->c++;
	if(temp->c>2*1)
	overflow(temp,root);
}

void createbt(btptr temp,int key, btptr &root)
{
	int i=0;
	if(temp->childptr[0]!=NULL)//changed to if from intially while
	{
		for(i=0;i<temp->c;i++)
		{if(key<temp->keys[i])
		 {createbt(temp->childptr[i],key,root);break;
		 }
		}
		if(i==temp->c)
		createbt(temp->childptr[i],key,root);
	}
	if(temp->childptr[0]==NULL)
	{inssort(temp,key,root,NULL);}
}

void printLDR(btptr B)
{
    if(B!=NULL)
    {
        for(int i=0;i<B->c;i++)
        {
            printLDR(B->childptr[i]);
            cout<<B->keys[i]<<endl;
        }
        printLDR(B->childptr[B->c]);
    }
}

int main()
{
	btptr root=new struct btnode;
	root->c=0;
	int n,input;
	for(int i=0;i<4;i++)
	root->childptr[i]=NULL;
	cout<<"Enter no of datas: ";
	cin>>n;
	for(int i=0;i<n;i++)
	{cin>>input;
	createbt(root,input,root);
	}	cout<<"printing: "<<endl;
cout<<root->keys[0]<<endl<<root->childptr[0]->keys[0]<<endl<<root->childptr[1]->keys[0]<<endl;
cout<<root->c<<endl<<root->childptr[0]->c<<endl<<root->childptr[1]->c<<endl;

//printLDR(root);

}



Last edited on
MikeyBoy (5631)
What error? What behaviour are you seeing, and how does it differ from the behaviour you expect?
koopey (160)

if n(no of inputs)=4 and let the inputs be 4,7,1 and 9, after entering '9', it enters an infinite loop, i don't know why. but if n=3, i.e. input are 4, 7, and 1, the program works fine.
I have been stuck in this since yesterday afternoon!!

Edit: I changed a simple ' while' to if and the program works up to 5 but from the sixth input, again infinite loop. Let the inputs be 4,7,1,9, 2 and 8. Infinite loop after 8 is entered! code above is also changed.
Last edited on
mbozzi (3944)
In your function void overflow(btptr T,btptr &root) called from inssort(), your code enters an infinite loop because tag is zero forever.

What is supposed to happen when the condition on line 48 if(T->keys[0]<temp->keys[j]) is false?

On line 50, do you actually intend to break from the loop before setting the tag to one?

Some notes:
Code that typedef's the object tag names typedef struct foo {} foo, *pfoo; isn't required in C++, only C. This is because C stores the tag names of objects in a different (second-class) namespace, where C++ doesn't. I recommend avoiding elaborated type specifiers in C++ (and C) because the explicit use of the tag names as opposed to the type name enables a class of bugs where names in different namespaces can shadow each other: code like struct foo foo;, int foo(); struct foo; is actually valid. In C, use of typedefs instead of tag names makes the code a bit safer and less verbose, in C++, use of typedefs is unnecessary; going out of the way to use tag names is detrimental.

It's a bit odd to pass a parameter called temp into a function, especially by reference (pointer).
Consider using lvalue references instead of pointers where possible.

Instead of manually initializing each btnode, just write a constructor.
Consider using smart pointers instead of raw pointers to make the ownership of child nodes explicit (and to save you from having to implement the rule of three).

I see no delete anywhere in your code. Don't forget to deallocate your memory!

In your main function, why did you dynamically allocate the root node?
Topic archived. No new replies allowed.