[C] Simple operations - binary search tree.

Hi!

I've got a few problems with implementation BST using an array. I have to use array, where 2i - left child, 2i + 1 - right child - 2/i - parent of i.

Maximum size of any table must be maxmium 4096 bytes (1024*sizeof(int)) - I don't know how to solve it(currently i've got simple table), maybe table of pointers at another table ??. The height of tree is maximum 30.


There are 3 operations: adding new item, finding max and min.


This is what I've done:

Code:

int add(int *tree,int number,int *counter)
{
	if(tree[*counter] == -1)
	{
		tree[*counter]=number;
		return 0;
	}
	else if(liczba > tree[*counter])
	{
		*counter = 2*(*counter);
		add(tree,liczba,counter);
	}
	else
	{
		*counter = 1+(2*(*counter));
		add(tree,liczba,counter);
	}
}

int max(int *tree,int i)
{
	int max = tree[i];
	if(tree[2*i+1] != -1)
	{
		max=tree[2*i+1];
		max(tree,++i);
	}
	printf("%d\n",max);
	return 0;
}
int min(int *tree,int i)
{
	int min = tree[i];
	if(tree[2*i] != -1)
	{
		min=tree[2*i];
		min(tree,++i);
	}
	printf("%d\n",min);
	return 0;
}

Finding max and min seems to not work, maybe because of bad adding function :P

Thanks for any help.

I don't know why you recursively call max inside of max. Just always go to the right until you can't go to the right any more and that's the max. Similarly just always go to the left and you'll find the min.

This doesn't feel right:

Code:

int add(int *tree,int number,int *counter)
{
	if(tree[*counter] == -1)
	{
		tree[*counter]=number;
		return 0;
	}
	else if(liczba > tree[*counter])
	{
		*counter = 2*(*counter);
		add(tree,liczba,counter);
	}
	else
	{
		*counter = 1+(2*(*counter));
		add(tree,liczba,counter);
	}
}

Originally Posted by hk_mp5kpdw

This doesn't feel right:

Code:

int add(int *tree,int number,int *counter)
{
	if(tree[*counter] == -1)
	{
		tree[*counter]=number;
		return 0;
	}
	else if(liczba > tree[*counter])
	{
		*counter = 2*(*counter);
		add(tree,liczba,counter);
	}
	else
	{
		*counter = 1+(2*(*counter));
		add(tree,liczba,counter);
	}
}

Oooh -- the more important part is probably "shouldn't counter go up by one when you add something to the tree"? (Assuming that's the point of counter, otherwise why it is a pointer?)

Oh yes, I pasted wrong code, should be:

Code:

int max(int *tree,int i)
{
	int maxy = tree[i];
	if(tree[2*i+1] != -1)
	{
		maxy=tree[2*i+1];
		max(tree,++i);
	}
	printf("%d\n",maxy);
	return 0;
}
int min(int *tree,int i)
{
	int miny = tree[i];
	if(tree[2*i] != -1)
	{
		miny=tree[2*i];
		min(tree,++i);
	}
	printf("%d\n",min);
	return 0;
}

@tabstop

This line is in charge of changing counter:

Code:

*counter = 2*(*counter);

@hk_mp5kpdw

Ya, i'm aware, but i don't know what is the purpose of it.


Thanks all for answers.

Okay, so counter just goes back to wherever you placed the element, not necessarily the actual number of elements. That's fine.

There is still no possible way that "max(tree, ++i)" could be correct. Just go to the right -- in the tree, not in the array itself.

EDIT: And at some point, you'll need to check that you don't go over the magic number of 1024 or whatever it is.

@tabstop

You're not very helpful at all...

Originally Posted by milky

@tabstop

You're not very helpful at all...

You've got the "to the right" bit, which is 2*i+1. There is nothing else to do. There is no i++, because (if we're doing this right) we're already on the right hand node, which means i++ takes us all the way back to the left which is very bad for finding a max in a BST.

EDIT: So just keep going to the right. Keep doing 2*i+1 until they make you stop.

Sth like that?

Code:

int min(int *tree,int i)
{
	int miny = tree[i];
	while(tree[2*i] != -1)
	{
		i=2*i;
		miny=tree[i];
	}
	printf("%d\n",min);
	return 0;
}

It doesn't work.

How can you print min? Why not print miny?

Oh, silly mistake, thanks. But still not working. Maybe I paste here my input code:

Code:

int *tree;
	tree = (int*)malloc(1000*sizeof(int));
	memset(tree,-1,1000*sizeof(int));
	int i;
	char sign;
	int number;
	int counter = 1;
	int *wsk;
	wsk = &counter;
while(scanf("%s %d",&sign,&number) > 0)
	{
		if(sign == '+')
		{	
			add(tree,number,wsk);
		}
		if(sign == 'h')
			max(tree,1);
		if(sign == 'l')
			min(tree,1);
	
	}
}

When i type "l", nothing is happen, i don't know why...

What if you type "l 1"?

EDIT: Also, and this is kind of important, there's a difference between %s and %c.

Oh, another silly mistake. Now it's working, thank you very much. Would you mind to help me with the problem of maximum size of array. What should i do? Array of pointers to some another array? Max height of tree is 30, so array must have size 2^30, right?

Maximum size of any array must be less than 4096 bytes.

A maximum height of 30? In an array based setup? Where you're required to do 2i and 2i+1? Yow. With 1024 elements you can have a depth of 10, which means an array of arrays would still only get you to a depth of 20, meaning you need an array of array of arrays. At this point nothing good can come of this. (And you won't get that on the stack anyway: 2^30 integers would take 4GB of memory.)

You've already set your array size dynamically, so what's the problem? You aren't actually building a tree, you're just calculating the maximum possible jumps to hit every possible square.
4K / 2 = 2K
2K / 2 = 1K
1K / 2 = 512
512/ 2 = 256
256/ 2 = 128
128/ 2 = 64
64 ...
32
16
8
4
2
1

13 possible jumps to hit any given square.


Quzah.