Thread: Binary Search Tree Using an array

  1. #1
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221

    Binary Search Tree Using an array

    Hello, i am trying to add items to a tree. I am finding no information in my book or the web about BST and arrays.
    Since all i can find is pointer based i am trying to convert
    that to array based and implement that. I am checking
    if ( aData < items[parent].instanceData)
    then add to the left or right . However, it seems all the items to be adding to the right.
    The indexes are not in the right order either. I was told i need a helper function that knows the index. I dont know why i would need one.

    driver

    Code:
    	data	aData;
    
    	cout << "Database Of Great Computer Scientists\n\n";
    
    	database.insert(data("Ralston, Anthony"));
    	database.insert(data("Liang, Li"));
    	database.insert(data("Jones, Doug"));
    	database.insert(data("Goble, Colin"));
    	database.insert(data("Knuth, Donald"));
    	database.insert(data("Kay, Alan"));
    	database.insert(data("Von Neumann, John"));
    Code:
    void BST::insert (const data& aData)
    {
    
    
    	if ( items[parent].empty ) 
    	{
    		items[parent].instanceData = aData;
    		items[parent].empty = false;
    		size++;
    	}
    	
     else if ( aData < items[parent].instanceData)
    	{
    		
    		if ( parent >= maxsize ) 
                           {
                            this->expand();
                            }
                             parent = (2 * parent)+ 1;
    		 this->insert(aData);
    		}
    			
    	}
    	else
    	{
    		
    		if ( parent >= maxsize ) 
    		{
                                 this->expand();
    			
    	             }
    	             parent = (2 * parent)+ 2;
    		this->insert(aData);
    	}
    
    
    
    }

    Code:
    bool operator< (const data& d1, const data& d2)
    {
    
    if ( strcmp( d1.getName(), d2.getName() ) == 1 )
        {
                return true;
        }
        else if ( strcmp( d1.getName(), d2.getName() ) == -1 )
        {
                return false;
        }
    
        return false;
    
           
    }
    is my logic off in the operator< function? it seems to want to add all items to the right.
    Also, parent goes from 0 to 2 to 6 to 14
    any help is much appreciated

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Your operator < would work, but it sorted descending and was far longer than it should be:
    Code:
    bool operator < (const data& d1, const data& d2)
    {
        return d1.getName() < d2.getName();
    }
    I mean, you are using std::strings right since this is C++?
    Code:
                    0
                  /   \
                /       \
              /           \
            1               2
           / \             / \
         /     \         /     \
        3       4       5       6
      /   \   /   \   /   \   /   \
     7    8  9    10 11   12 13   14
    0 -> 2 -> 6 -> 14 is indeed down the right hand side.
    Last edited by iMalc; 11-27-2009 at 07:14 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    I am suppose to store the names as char *
    i tried your suggestion and it didn't add correctly. That could be because of my insert function.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Well if you're forced to not use std::strings then you want just this:
    Code:
    bool operator < (const data& d1, const data& d2)
    {
        return strcmp(d1.getName(), d2.getName()) < 0;
    }
    If that doesn't work then the problem is elsewhere.
    I'm highly suspicious of where 'parent' comes from and what it is set to for starters. It doesn't seem to be declared locally.

    Unfortunately I think the whole way you're doing it is basically doomed . You can't store a tree with more than about 25-30 levels in an array this way, which can mean that even 30 items total can break it (assuming no balancing).
    If you drop the binary-heap style (child=2*parent+k) indexing and store child indexes within each node instead, then it can work. This however simply trades the concept of storing and using pointers for storing and using indexes instead. The array then is little more than a pool allocator.

    The better option is to simply learn and use pointers. If you're going to be a programmer then learning pointers is unaviodable.
    You can drop the "this->" bits throughout that code.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    Awesome, That worked. I am only adding 9 items so using this array shouldn't
    be a problem. My parent index starts at zero. When it adds "Goble, Colin" at index 7 like it suppose to, to the left. The next name is "knuth, Donald" that adds to the right like it suppose to. It suppose to go to index 8 however, parent goes
    from 7 to 16 and thats not what i want. My problem might be in my expand function?

    Am i suppose to always be comparing the new item with the first parent? or the last parent that was added?

    this is the order i am hoping to achieve.

    Code:
    	 << "Database Of Great Computer Scientists\n\n";
    
    	database.insert(data("Ralston, Anthony"));
    	database.insert(data("Liang, Li"));
    	database.insert(data("Jones, Doug"));
    	database.insert(data("Goble, Colin"));
    	database.insert(data("Knuth, Donald"));
    	database.insert(data("Kay, Alan"));
    	database.insert(data("Von Neumann, John"));
    	database.insert(data("Trigoboff, Michael"));
    	database.insert(data("Turing, Alan"));
    Required output...

    Ralston, Anthony 0
    Liang, Li 1
    Von Neumann, John 2
    Jones, Doug 3
    Trigoboff, Michael 5
    Goble, Colin leaf 7
    Knuth, Donald 8
    Turing, Alan leaf 12
    Kay, Alan leaf 17
    I changed the code a bit from the first post.

    Code:
    void BST::insert (const data& aData)
    {
    
    
    if ( items[parent].empty ) 
    	{
    		items[parent].instanceData = aData;
    		items[parent].empty = false;
    		size++;
    	
    	}
    
    	else if ( aData < items[parent].instanceData)
    	{
    
    		parent = (2 * parent)+ 1;
    
    		if(parent > maxsize)
    		{
    			this->expand();
    		}
    
    		this->insert(aData);
            
    	}
    	else
    	{
    		parent = (2 * parent)+ 2;
    		if(parent > maxsize)
    		{
    			this->expand();
    		}
    
    		this->insert(aData);
    		
    	}

    expand array.

    Code:
    void BST::expand()
    {
    
    
    	item *swap = new item[size+1]; 
    
    	for ( int index = 0; index < size*2; index++ ) 
    	{
    		if ( !items[index].empty )
    		{
    			swap[index].instanceData = items[index].instanceData;
    			swap[index].empty = false;
    		}
    	}
    	maxsize += size;
    	delete [] items;
    	items = NULL;
    	items = swap;
    
    
    }

    Code:
    BST::BST(int capacity) : size(0), parent(0),
    items(new item[capacity])
    {
    
    	maxsize = capacity;
    	items->empty = true;
    
    }

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Each insertion should always start at the first parent (the root).

    Don't you have a buffer overrun in your expand function?:
    Code:
    	item *swap = new item[size+1]; 
    
    	for ( int index = 0; index < size*2; index++ ) 
    	{
    		if ( !items[index].empty )
    You're only allocating one more than 'size' items but 'maxsize' is increased by 'size' which will typically be more than one, and you don't expand again until 'maxsize' is exceeded. So most of the time you'd be using memory off the end of the array.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    What would you propose i do about that then?


    item *swap = new item[size*2];

    for ( int index = 0; index < size; index++ )
    {
    if ( !items[index].empty )
    Last edited by mrsirpoopsalot; 11-28-2009 at 10:09 PM.

  8. #8
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    iMalc, thanks for helping me.. I got the insert working. I also got the recursive part of the add working.
    Code:
    item *swap = new item[maxsize*2];
    
    	for ( int index = 0; index < maxsize; index++ ) 
    	{
    		if ( !items[index].empty )
    		{

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by mrsirpoopsalot View Post
    iMalc, thanks for helping me.. I got the insert working. I also got the recursive part of the add working.
    Code:
    item *swap = new item[maxsize*2];
    
    	for ( int index = 0; index < maxsize; index++ ) 
    	{
    		if ( !items[index].empty )
    		{
    Yeah that looks fine now.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    Thats good
    Last edited by mrsirpoopsalot; 11-30-2009 at 10:58 PM.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    I am trying to display the contents of the tree i think inorder.
    What i am trying to do is print "leaf" for the leafs.
    For what i understand is that in order for it to be a leaf left child needs to be null and so does rightchild

    problem is it only prints one leaf.
    i commented out the code that prints way to many leafs.


    Code:
    void BST::displayArrayOrder (ostream& out) const
    {
    
    	out << ">>> array order:" << endl;
    	displayHeaders(out);
    
    
    	for(int index=0; index < maxsize+1; index++)
    	{
    
    		if (!items[index].empty) 
    		{
    			out << left
    				<< setw(37) << items[index].instanceData; 
    				
    			if(items[2 * index + 1 ].empty && items[2 * index + 2].empty)
    			{
    			    out << left
    
    				 << setw(17) << "leaf";
    			}
    			
    			out << setw(21) << index << ' ';
    			out << endl;
    			
    
    		}
             //  if(items[2 * index + 1 ].empty && items[2 * index + 2].empty) // print way too many leafs
    			//{
    			   // out << left
    
    				// << setw(17) << "leaf";
    			//}
    
    	}
    
    
    
    }

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You have two options. Just make a single loop over all positions in the array and output every non-empty item. No fancy child-parent calculations needed at all - very short code for this option.

    OR

    Write a recursive tree processing function that follows only the calculated child node positions which have actual children, and ignores the fact that items are even stored sequentially in memory.

    You can't do both at once!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 02:02 PM
  3. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  4. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM
  5. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM