Binary Tree Search

This is a discussion on Binary Tree Search within the C++ Programming forums, part of the General Programming Boards category; Howdy, I was reading Preludes Binary Tree Search article, and figured I'd give it a go myself. Heres what I ...

  1. #1
    Banned nickname_changed's Avatar
    Join Date
    Feb 2003
    Location
    Australia
    Posts
    986

    Binary Tree Search

    Howdy,

    I was reading Preludes Binary Tree Search article, and figured I'd give it a go myself.

    Heres what I managed to get, but it doesn't seem to be working :S

    Code:
    #include <iostream>
    #include <windows.h>
    #include <string>
    
    using std::string;
    using std::cout;
    using std::cin;
    using std::endl;
    
    //=============================================
    //		Tree Branch
    //=============================================
    class TreeBranch
    {
    public:
    	int Data;
    	TreeBranch * Branches[2];
    	TreeBranch()
    	{
    		Data = 0;
    		Branches[0] = NULL;
    		Branches[1] = NULL;
    	}
    };
    
    
    class TreeTop
    {
    public:
    	TreeTop()
    	{
    		Size = 0;
    		Header = NULL;
    	}
    	int Size;
    	TreeBranch * Header;
    	bool Find(int SearchKey);
    	bool Insert(TreeBranch * NewValue, int New);
    };
    
    //=============================================
    //		TreeTop::Find()
    //=============================================
    bool TreeTop::Find(int SearchKey)
    {
    	TreeBranch * Walk;
    	int Direction;
    	
    	Walk = Header;
    	for (;;)
    	{
    		if (Walk == NULL)
    		{
    			// Reached the end :(
    			return false;
    		}
    		if (Walk->Data == SearchKey)
    		{
    			// Found what we were looking for!
    			return true;
    		}
    		Direction = Walk->Data < SearchKey;
    		Walk = Walk->Branches[Direction];
    	}
    }
    
    
    //=============================================
    //		TreeTop::Insert()
    //=============================================
    bool TreeTop::Insert(TreeBranch * NewValue, int New)
    {
    	// Search for a dead link
    	TreeBranch * Walk;
    	TreeBranch ** Save;
    	int Direction;
    	
    	Save = &this->Header;
    	Walk = Header;
    	for (;;)
    	{
    		if (Walk == NULL)
    		{
    			// Reached a dead link
    			break;
    		}
    		else if (Walk->Data == NewValue->Data)
    		{
    			// The value already exists!
    			cout << "New value of " << 
    				NewValue->Data << " already exists!" << endl;
    			return false;
    		}
    		
    		// Ok, we didn't find it, but we do have branches left...
    		Direction = Walk->Data < NewValue->Data;
    		Save = &Walk->Branches[Direction];
    		Walk = Walk->Branches[Direction];
    	}
    	
    	*Save = NewValue;
    	this->Size++;
    	
    	cout << endl << "New value (" << NewValue->Data 
    		<< ") inserted at: " << &Save << endl;
    	return true;
    }
    
    //=============================================
    //		Main()
    //=============================================
    int main()
    {
    	cout << "Creating new tree... ";
    	TreeTop Tree;
    	Tree.Size = 0;
    	Tree.Header = NULL;
    	cout << "OK" << endl;
    
    	cout << "Populating Tree... ";
    	TreeBranch * NewValue = new TreeBranch;
    	NewValue->Data = 9;
    	Tree.Insert(NewValue, 9);
    	NewValue->Data = 8;
    	Tree.Insert(NewValue, 8);
    	NewValue->Data = 5;
    	Tree.Insert(NewValue, 5);
    	NewValue->Data = 2;
    	Tree.Insert(NewValue, 2);
    	NewValue->Data = 8;
    	Tree.Insert(NewValue, 8);
    	NewValue->Data = 7;
    	Tree.Insert(NewValue, 7);
    	delete NewValue;
    	cout << "OK" << endl;
    
    	cout << "Searching the tree for '2'... ";
    	if (Tree.Find(2) == true)
    	{
    		cout << "Found!" << endl;
    	}
    	else cout << "Not Found!" << endl;
    	
    	return 0;
    }
    When I run it, I get:
    Code:
    Creating new tree... OK
    Populating Tree...
    New value (9) inserted at: 0012FEF0
    New value of 8 already exists!
    New value of 5 already exists!
    New value of 2 already exists!
    New value of 8 already exists!
    New value of 7 already exists!
    OK
    Searching the tree for '2'...
    And it freezes when it tries to find the new values... whats going on?:S I think I've done something wrong with the pointers somewhere, gosh I hate them!
    Last edited by nickname_changed; 01-11-2004 at 06:05 PM.

  2. #2
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    As you've created this in main():
    TreeBranch * NewValue = new TreeBranch;
    then passed it to the insert function, the tree holds the same address as main()'s pointer, meaning the tree and NewValue are pointing to the same thing. Changing the value of the data in main() affects the data pointed to by the tree, which is why the tree thinks most of the data already exists.

    You should be creating leaves in the tree class, not in main, and copying the data to them.

    Also, these shouldn't be in main():
    Tree.Size = 0;
    Tree.Header = NULL;
    They should be private members of the class, so that no-one can screw up the tree except the class itself
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Hammer beat me to it (I'm slowing down in my old age ), but here is the (ugly as sin) code for one of my test drivers for the basic functions from that article. It may help you...somehow:
    Code:
    #ifdef TEST_DRIVER
    
    #include <stdio.h>
    #include <stdlib.h>
    
    void print_node ( int value, int level )
    {
      int i;
    
      for ( i = 0; i < level; i++ )
        printf ( "\t" );
      printf ( "%d\n", value );
    }
    
    void print_tree_structure ( struct pretree_node *node, int level )
    {
      if ( node == NULL )
        print_node ( -1, level );
      else {
        print_tree_structure ( node->link[1], level + 1 );
        print_node ( node->data, level );
        print_tree_structure ( node->link[0], level + 1 );
      }
    }
    
    int main ( void )
    {
      struct pretree tree = {0};
      struct pretree_node *node;
      int i;
    
      for ( i = 0; i < 20; i++ ) {
        node = malloc ( sizeof *node );
        if ( node == NULL )
          break;
        node->data = rand() % 10;
        node->link[0] = node->link[1] = NULL;
        pretree_insert ( &tree, node, node->data );
      }
      print_tree_structure ( tree.header, 0 );
      while ( tree.header != NULL ) {
        printf ( "\n-----------------------------------\n" );
        printf ( "Item to remove: " );
        fflush ( stdout );
        pretree_remove ( &tree, &node, getchar() - '0' );
        getchar();
        print_tree_structure ( tree.header, 0 );
      }
    
      return 0;
    }
    
    #endif
    My best code is written with the delete key.

  4. #4
    Banned nickname_changed's Avatar
    Join Date
    Feb 2003
    Location
    Australia
    Posts
    986
    Ahhhh ok, I understand, thanks guys Since I was changing the same place in memory that was being used by the tree, the data in the tree was also changed (since really its the same data...) gotcha

    This is what main() looks like:
    Code:
    int main()
    {
    	cout << "Creating new tree... ";
    	TreeTop Tree;
    	cout << "OK" << endl;
    
    	cout << "Populating Tree... ";
    	TreeBranch * NewValue = new TreeBranch;
    	NewValue->Data = 9;
    	Tree.Insert(NewValue, 9);
    	
    	TreeBranch * NewValue2 = new TreeBranch;
    	NewValue2->Data = 7;
    	Tree.Insert(NewValue2, 7);
    
    	TreeBranch * NewValue3 = new TreeBranch;
    	NewValue3->Data = 2;
    	Tree.Insert(NewValue3, 2);
    
    	TreeBranch * NewValue4 = new TreeBranch;
    	NewValue4->Data = 6;
    	Tree.Insert(NewValue4, 6);
    
    	delete NewValue;
    	delete NewValue2;
    	delete NewValue3;
    	delete NewValue4;
    	
    	cout << "OK" << endl;
    
    	cout << "Searching the tree for '2'... ";
    	if (Tree.Find(2) == true)
    	{
    		cout << "Found!" << endl;
    	}
    	else cout << "Not Found!" << endl;
    	
    	return 0;
    }
    I also had to be careful not to delete a NewValue variable before they were created.

    Now however its still pausing when searching for the number 2, even though it has been put in. The Find() function hasn't changed since I first posted... what could be causing this problem?
    Last edited by nickname_changed; 01-12-2004 at 02:52 AM.

  5. #5
    Banned nickname_changed's Avatar
    Join Date
    Feb 2003
    Location
    Australia
    Posts
    986
    Hm interesting,

    I did a little looking and found the loop in Find() only ever runs once right to the end of the loop. Then it seems to go to start again, but nothing happens, then I get an application error.

    VC++ says its an Unhandled exception, access invalid (I think), on this line:
    if (Walk->Data == SearchKey)

    Hm... could it be because ones an int, and the other is an int but one that is in a part of memory that belongs to another part of the application? Although that shouldn't matter should it...

    This is the output I managed to get before it crashed:
    Code:
    Creating new tree... OK
    Populating Tree...
    New value (9) inserted at: 0012FEB4
    
    New value (7) inserted at: 0012FEB4
    
    New value (2) inserted at: 0012FEB4
    
    New value (6) inserted at: 0012FEB4
    OK
    Searching the tree for '2'...

  6. #6
    Banned nickname_changed's Avatar
    Join Date
    Feb 2003
    Location
    Australia
    Posts
    986
    Omg I'm so naughty, I deleted the memory that it was stored in, so therefore I didn't own that memory, which explains the access violation. Its all fixed now, I wont use new and delete I'll just make them as regular variables hehe... thanks for all the help guys

    And thanks for the great tutorial Prelude! I haven't finished reading it all but I plan to.

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I wont use new and delete I'll just make them as regular variables hehe...
    You'll have more luck with new and delete, but new creates a node that is placed in the tree. The memory should only be released when the node is removed from the tree, which is usually only two cases:

    1) A single node is removed from the tree by a call to a remove routine. This is the hardest as you have to unlink the node, fix the structure of the tree, then release the memory, resulting in a stable tree.
    2) All nodes in the tree are removed, usually with a postorder recursive traversal. This is easier as you only have to worry about releasing the nodes in the correct order so that you can reach all of them. The structure of the tree after this operation is irrelevant.
    My best code is written with the delete key.

  8. #8
    Banned nickname_changed's Avatar
    Join Date
    Feb 2003
    Location
    Australia
    Posts
    986
    This is what my code is currently, not a problem as far as I can tell:
    Code:
    #include <iostream>
    #include <windows.h>
    #include <string>
    
    using std::string;
    using std::cout;
    using std::cin;
    using std::endl;
    
    //=============================================
    //		Tree Branch
    //=============================================
    class TreeBranch
    {
    public:
    	int Data;					
    	TreeBranch * Branches[2];	
    	TreeBranch()
    	{
    		Data = 0;
    		Branches[0] = NULL;
    		Branches[1] = NULL;
    	}
    };
    
    
    class TreeTop
    {
    public:
    	TreeTop()
    	{
    		Size = 0;
    		Header = NULL;
    	}
    	int Size;	
    	TreeBranch * Header;			
    	bool Find(int SearchKey);				
    	bool Insert(TreeBranch * NewValue, int New);
    	bool NewInsert(int New);
    };
    
    //=============================================
    //		TreeTop::Find()
    //=============================================
    bool TreeTop::Find(int SearchKey)
    {
    	TreeBranch * Walk;
    	int Direction;
    	
    	Walk = Header;
    	for (;;)
    	{
    		if (Walk == NULL)
    		{
    			// Reached the end :(
    			return false;
    		}
    		if (Walk->Data == SearchKey)
    		{
    			// Found what we were looking for!
    			return true;
    		}
    		
    		// Ok, we didn't find it, but we do have 
    		// branches left...
    		Direction = Walk->Data < SearchKey;
    		Walk = Walk->Branches[Direction];
    
    		cout << ".";
    	}
    }
    
    
    //=============================================
    //		TreeTop::Insert()
    //=============================================
    bool TreeTop::Insert(TreeBranch * NewValue, int New)
    {
    	// Search for a dead link
    	TreeBranch * Walk;
    	TreeBranch ** Save;
    	int Direction;
    
    	Save = &this->Header;
    	Walk = Header;
    	for (;;)
    	{
    		if (Walk == NULL)
    		{
    			// Reached a dead link
    			break;
    		}
    		else if (Walk->Data == NewValue->Data)
    		{
    			// The value already exists!
    			cout << "New value of " << 
    				NewValue->Data << "
    				already exists!" << endl;
    			return false;
    		}
    		
    		// Ok, we didn't find it, but we do have
    		// branches left...
    		Direction = Walk->Data < NewValue->Data;
    		Save = &Walk->Branches[Direction];
    		Walk = Walk->Branches[Direction];
    	}
    	
    	*Save = NewValue;
    	this->Size++;
    	
    	cout << endl << "New value (" << NewValue->Data 
    		<< ") inserted at: " << &Save << endl;
    	return true;
    }
    
    bool TreeTop::NewInsert(int New)
    {
    	// Search for a dead link
    	TreeBranch * Walk;
    	TreeBranch ** Save;
    	int Direction;
    
    	TreeBranch * NewValue = new TreeBranch;
    	if (NewValue == NULL)
    	{
    		return false;
    	}
    	
    	NewValue->Data = New;
    
    	Save = &this->Header;
    	Walk = Header;
    	for (;;)
    	{
    		if (Walk == NULL)
    		{
    			// Reached a dead link
    			break;
    		}
    		else if (Walk->Data == NewValue->Data)
    		{
    			// The value already exists!
    			cout << "New value of " << 
    			NewValue->Data << " already 
    			exists!" << endl;
    			return false;
    		}
    		
    		// Ok, we didn't find it, but we do have 
    		// branches left...
    		Direction = Walk->Data < NewValue->Data;
    		Save = &Walk->Branches[Direction];
    		Walk = Walk->Branches[Direction];
    	}
    	
    	*Save = NewValue;
    	this->Size++;
    	
    	cout << endl << "New value (" << NewValue->Data 
    		<< ") inserted at: " << &Save << endl;
    	
    	return true;
    }
    
    //=============================================
    //		Main()
    //=============================================
    int main()
    {
    	cout << "Creating new tree... ";
    	TreeTop Tree;
    	cout << "OK" << endl;
    
    	cout << "Populating Tree... ";
    	
    	Tree.NewInsert(6);
    	Tree.NewInsert(7);
    	Tree.NewInsert(3);
    	Tree.NewInsert(32);
    	Tree.NewInsert(45);
    	Tree.NewInsert(67);
    	Tree.NewInsert(1);
    	Tree.NewInsert(12);
    	Tree.NewInsert(8);
    	Tree.NewInsert(2);
    	Tree.NewInsert(9);
    	
    	cout << "OK" << endl;
    
    	cout << "Searching the tree for '2'... ";
    	if (Tree.Find(2) == true)
    	{
    		cout << "Found!" << endl;
    	}
    	else cout << "Not Found!" << endl;
    	
    	return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 08:11 AM
  3. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  4. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 09:18 AM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

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