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;

	
	
}

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.