[C] Simple operations - binary search tree.

This is a discussion on [C] Simple operations - binary search tree. within the C Programming forums, part of the General Programming Boards category; Hi! I've got a few problems with implementation BST using an array. I have to use array, where 2i - ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    40

    [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.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,803
    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);
    	}
    }
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by hk_mp5kpdw View Post
    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?)

  5. #5
    Registered User
    Join Date
    Nov 2009
    Posts
    40
    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.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  7. #7
    Registered User
    Join Date
    Nov 2009
    Posts
    40
    @tabstop

    You're not very helpful at all...

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by milky View Post
    @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.
    Last edited by tabstop; 05-17-2010 at 01:59 PM.

  9. #9
    Registered User
    Join Date
    Nov 2009
    Posts
    40
    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.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    How can you print min? Why not print miny?

  11. #11
    Registered User
    Join Date
    Nov 2009
    Posts
    40
    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...

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    What if you type "l 1"?

    EDIT: Also, and this is kind of important, there's a difference between %s and %c.
    Last edited by tabstop; 05-17-2010 at 02:32 PM.

  13. #13
    Registered User
    Join Date
    Nov 2009
    Posts
    40
    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.

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.)

  15. #15
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 08:11 AM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21