Array based Binary search tree- Searching

This is a discussion on Array based Binary search tree- Searching within the C++ Programming forums, part of the General Programming Boards category; I am trying to retrieve a name as a key in the tree recursively. my tree is as follows. 0,1,3,7,8,17,2,5,12 ...

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

    Array based Binary search tree- Searching

    I am trying to retrieve a name as a key in the tree recursively.
    my tree is as follows. 0,1,3,7,8,17,2,5,12 atleast thats
    how it was added. I am searching for index 5 "Trigoboff, Michael"
    parent =0;
    it suppose to go from parent(index) 0,2,5 however its going from 0,2,6 in the retrieve function...

    Is my comparison wrong? or is it something to do with my retrieve function?
    I have been working on this for 4 days and im ready to give up!

    main()
    Code:
    	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"));
    	displayDatabase(true);
    	retrieveItem("Trigoboff, Michael", aData);
    	retrieveItem("Kaye, Danny", aData);
    one header

    Code:
    
    #include "data.h"
    
    class BST								// a Binary Search Tree (BST)
    {
    public:
    	BST(int capacity = 5);				// constructor (default if no arg supplied)
    	BST(const BST& aTable);				// copy constructor
    	~BST();								// destructor
    
    	void insert(const data& aData);		
    	bool remove(const char *key);
    	bool retrieve(const char *key, data& aData) const;
    	void displayArrayOrder(ostream& out) const;		
    	void displayPreOrder(ostream& out) const;
    	void displayInOrder(ostream& out) const;
    	void displayPostOrder(ostream& out) const;
    	int getSize(void) const;
    
    private:
    
        int size;
        int maxsize;  
        int parent;
        
     
        void expand();
    
    	struct item
    	{
    		bool	empty;
    		data instanceData;
    		bool  isLeaf;
    	};
    	
    	item *items;
    	
    	void insert(int index, const data & aData ); 
    	void displayHeaders(ostream& out)const;
    	void BST::displayPreOrder(std::ostream &out, int parent)const;
    	void BST::displayInOrder(std::ostream &out, int parent)const;
    	void BST::displayPostOrder(std::ostream &out, int parent)const;
    	bool BST::retrieve(const char *key, data& aData, int parent) const;
    	void itemsPrinted(ostream &out,int size)const;
    };
    
    
    #endif // BST_H
    retrieve functions...

    Code:
    bool BST::retrieve(const char *key, data& aData) const
    {
    
    	retrieve(key, aData, parent);
    
    	if (key == aData)
    	{
    		return true;
    	}
    	else
    	{
    		return false;
    	}
    
    
    
    }

    Code:
    bool BST::retrieve(const char *key, data &aData, int parent) const
    {
    
    
    	if (!items[parent].empty )
    	{
    
    		if (key == items[parent].instanceData.getName())
    		{
    			aData.setName(key);
    			return true;
    		}
    		else if (key < items[parent].instanceData.getName() )
    		{
    			parent =(2*parent) + 1;
    			retrieve(key, aData, parent);
    		}
    		else
    		{
    			parent =( 2*parent) + 2;
    			retrieve(key, aData, parent);
    		}
    		return 0;
    
    	} 
    }

    BOTH comparison operators..

    Code:
    bool operator< (const data& d1, const data& d2)
    {
    
     return strcmp(d1.getName(), d2.getName()) < 0;
    	
    
    }
    
    // return true if d1 is "equal to" d2, false otherwise
    bool operator== (const data& d1, const data& d2)
    {
    
    return strcmp(d1.getName(), d2.getName()) == 0;
    
    	
    	
    }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    No, it should not go from (0, 2, 5) it should go (0, 2, 6, 14, 29) if you're searching for the item containing 5. Draw the tree you're building by inserting the values in that order:
    Code:
    0
     \
      1
       \
        3
       / \
      2   7
         / \
        5   8
             \
              17
             /
            12
    Now traverse:
    0 -> Go right: 0*2+2 = 2
    2 -> Go right: 2*2+2 = 6
    6 -> Go right: 6*2+2 = 14
    14 -> Go left: 14*2+1 = 29
    Item found = "5". This is correct for the scheme you're using.

    I mentioned earlier how storing nodes in this way is particularly horrible because with only say 30 items you could require up to more memory than your computer has. This is what you get for trying to build a binary tree without using pointers.
    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 Search Tree
    By willmhmd in forum C Programming
    Replies: 2
    Last Post: 12-16-2005, 12:35 PM
  2. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 02:56 PM
  3. binary search in an array
    By brianptodd in forum C++ Programming
    Replies: 4
    Last Post: 11-12-2002, 01:05 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

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