Jump to content
  • Advertisement
Sign in to follow this  
Estauns

Binary Tree Problem - Finding Elements...

This topic is 5459 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This binary tree is kicking my butt to hell and back. I'm trying to write a find routine that returns the data associated with the node in a pointer, so that I can modify the data without reinserting it into the tree (is this the way to go?). The problem is, I just can't seem to win. If the return type is a pointer, than thats fine if I'm using a pointer but blows up when I try to use just uhh.. non-pointers. But if I use pointers, than the search type is just wrong because its searching for a pointer and not a value. Heres my search functions:
	T *Find(T Search)
	{
		CBinaryTreeNode<T> *pNode = Find(m_pRoot, Search);

		if(pNode == NULL)
			return NULL;
		else
			return pNode->GetData();
	}

	CBinaryTreeNode<T> *Find(CBinaryTreeNode<T> *pNode, T Search)
	{
		if(pNode == NULL)
			return NULL;
		else if(pNode->GetData() == Search)
			return pNode;
		else if(pNode->GetData() < Search)
			return Find(pNode->m_pLeft, Search);
		else
			return Find(pNode->m_pRight, Search);
	}

The second find is what the first find uses to find the node, so that the first find can return the data. But both of these break on me:
	CBinaryTree<int *> PointerTree;

	PointerTree.Add(new int(5));
	PointerTree.Add(new int(6));
	PointerTree.Add(new int(7));

	int *pInteger = PointerTree.Find(5);


Trying to .Find(5) doesn't work, because 5 isn't a pointer, its a static value and the template type (T) is declared as int *. Then this one:
	CBinaryTree<int> IntegerTree;

	IntegerTree.Add(7);
	IntegerTree.Add(13);
	IntegerTree.Add(666);

	int *pInteger = IntegerTree.Find(7);


That one doesn't work because its trying to convert an int to an int *, because T is declared as an int and not an int *. So how can I make it do what I want to do? I can't figure it out, I've been playing with it for the last few hours. The only thing I can think of is to convert it to a map, and use a Key, but I want to make that as a seperate structure at a later time. Right now I just want this tree to work.

Share this post


Link to post
Share on other sites
Advertisement
As far as I can tell there's no way with your generic template to know whether T is an object or a pointer to an object. So it can't know whether to search for T or *T. So I'm not sure if you can do what you're trying to do.

In any case, I'm not sure why you're making a tree of int* rather than just a tree of int. Then your compare function would work, and you could return the address of the node data in order to change it externally.

There are certainly some more complicated approaches you could take if you want to store pointers to objects and yet be able to perform searches on the values of the objects.

Share this post


Link to post
Share on other sites
i have no idea (or time to figure out) why your tree only works with pointers BUT, heres how you get around your prob of the pointer compare:

pass a funciton pointer to your Find Function. the funciton pointer should be a compare funciton that does the correct comparison (ie. dereferences the pointers and compares) this should be done by the user. STL uses this design quite comonly to allow for some flexibility with sorting routines etc.

Share this post


Link to post
Share on other sites
I second silvermace's comments.
One way to fix the first usage example is like this:

int *five = new int(5);
PointerTree.Add(five);

...

int *pInteger = PointerTree.Find(five);

btw, I also highly suggest you change your find function to:
	CBinaryTreeNode<T> *Find(CBinaryTreeNode<T> *pNode, T Search)
{
while (pNode != NULL)
{
if(pNode->GetData() < Search)
pNode = pNode->m_pLeft;
else if(pNode->GetData() > Search)
pNode = pNode->m_pRight;
else
break;
}
return pNode;
}
which is FAR more efficient and uses less stack space than the code you posted. There is no need for recursion here.
Remember, even in the best case of a perfectly balanced tree, half of the nodes are all the way at the bottom, most nodes you visit are not equal to the item you're searching for so do that test last (done with an else above).

No, this is NOT a case of "Premature optimisation is the root of ...", but a case of a trained mind producing better code to start with.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!