Need help with BST and search function

Dev Shed Forums Sponsor:

February 21st, 2013, 07:48 AM

so.very.tired

Contributing User

Join Date: Nov 2012

Posts: 112

Time spent in forums: 1 Day 4 h 12 m 48 sec
Reputation Power: 1

Need help with BST and search function

Hi guys.

i need to write a recursive function that takes three parameters: tree's root, key, and a pointer to a function that measure the distance between two given keys, and returns the node that holds the closest key to the given key.
according to my assignment instructions, i'm not allowed to change the function prototype, and i have to deal with what i've got.

so, here's the prototype:

Code:

node_t FindClosestNode(node_t root, key_t key, dist_func_t distanceFunc );

node_t and key_t are pointers to void:

Code:

typedef void* key_t;
typedef void* node_t;

dist_func_t is a pointer:

Code:

typedef int (*dist_func_t)(key_t key1, key_t key2);

distanceFunc returns the distance between two keys (either strings or integers).

as you probably already noticed, it's impossible to compare between the given key and a current.node->key.
i can only measure distance between them. :|
which makes this assignment a big pain. so i can really use some help here.

after countless efforts and attempts, i managed to write something the works (kind of):

Code:

node_t FindClosestNode(node_t root, key_t key, dist_func_t distance)
{
	struct node* iterator=root; //casting

	if (distance(iterator->key, key)>distance(iterator->left->key, key)) //if the given key is closer to the left child
		return FindClosestNode(iterator->left, key, distance);
	else if (distance(iterator->key, key)>distance(iterator->right->key, key)) //if the given key is closer to the right child
		return FindClosestNode(iterator->right, key, distance);
	else  //else - the given key is closer to current node
		return iterator; 
}

my problem is this:
i couldn't think of any exit condition, and - most importantly - i couldn't figure out how to handle the cases where a node has no left/right child.
and that obviously causing a segmentation fault, since "distance" has to measure the distance between non valid keys.

any help would greatly appreciated.
also, i'd love to hear about other ideas on how to implement this function.
thanks in advanced!

Last edited by so.very.tired : February 21st, 2013 at 08:05 AM.

February 21st, 2013, 09:09 AM

so.very.tired

Contributing User

Join Date: Nov 2012

Posts: 112

Time spent in forums: 1 Day 4 h 12 m 48 sec
Reputation Power: 1

Yay!
i did it.

Code:

node_t FindClosestNode(node_t root, key_t key, dist_func_t distance)
{
	struct node* iterator=root; //casting

	if (iterator->left)
		if (distance(iterator->key, key)>distance(iterator->left->key, key))
			return FindClosestNode(iterator->left, key, distance);
	if (iterator->right)
		if (distance(iterator->key, key)>distance(iterator->right->key, key))
			return FindClosestNode(iterator->right, key, distance);
	return iterator;
}

and i know it's kind of an ugly code, but it works...

Last edited by so.very.tired : February 21st, 2013 at 09:12 AM.

February 22nd, 2013, 08:12 AM

so.very.tired

Contributing User

Join Date: Nov 2012

Posts: 112

Time spent in forums: 1 Day 4 h 12 m 48 sec
Reputation Power: 1

nope.
it has a major bug in it.

i can really use guidance:
how can i find closest node without the abilty to compare between the keys?

February 22nd, 2013, 08:49 AM

salem

Contributed User

Join Date: Jun 2005

Posts: 3,840

Folding Points: 153 Folding Title: Novice Folder

Time spent in forums: 2 Months 3 Weeks 2 Days 19 h 19 m 34 sec
Reputation Power: 1774

Don't you want something like

Code:

d1 = distance(iterator->key, key);
d2 = iterator->left ? distance(iterator->left->key, key) : INT_MAX;
d3 = iterator->right ? distance(iterator->right->key, key) : INT_MAX;

if d1 is smallest, then the current node is the answer.
if d2 < d3, then go left, otherwise go right.

__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper

February 22nd, 2013, 12:10 PM

so.very.tired

Contributing User

Join Date: Nov 2012

Posts: 112

Time spent in forums: 1 Day 4 h 12 m 48 sec
Reputation Power: 1

Hi salem.

what does INT_MAX represent?

February 22nd, 2013, 01:00 PM

salem

Contributed User

Join Date: Jun 2005

Posts: 3,840

Time spent in forums: 2 Months 3 Weeks 2 Days 19 h 19 m 34 sec
Reputation Power: 1774

Well in terms of the code posted, it means the furthest possible distance.

If you're after what INT_MAX is in C terms, try google.

February 22nd, 2013, 01:14 PM

requinix

Still alive

Join Date: Mar 2007

Location: Washington, USA

Posts: 12,711

Folding Points: 417516 Folding Title: Super Ultimate Folder - Level 1

Time spent in forums: 5 Months 1 Week 4 Days 6 h 45 m 38 sec
Reputation Power: 8969

Send a message via Google Talk to requinix

Consider a tree like

Code:

and searching for 8.

__________________
Site rules and FAQ | Project Suggestions | mod_rewrite guide | PHP New User Guide and FAQ - PHP Stickies | Regex Resources

February 22nd, 2013, 01:57 PM

so.very.tired

Contributing User

Join Date: Nov 2012

Posts: 112

Time spent in forums: 1 Day 4 h 12 m 48 sec
Reputation Power: 1

thanks salem.
but as requinix pointed out, this code won't work.

I was thinking maybe to try adopting some ideas from here, but i just can't make that work without comparing two keys...

February 22nd, 2013, 01:59 PM

dwise1_aol

Contributing User

Dev Shed God 2nd Plane (6000 - 6499 posts)

Join Date: Jan 2003

Location: USA

Posts: 6,138

Time spent in forums: 2 Months 2 Weeks 3 Days 21 h 36 m 57 sec
Reputation Power: 1974

Quote:

Originally Posted by so.very.tired

Hi salem.

what does INT_MAX represent?

Or you could read the limits.h header file.

HINT: with the finite number of bits in an integer type, there are minimum and maximum limits to the values you can represent with that many bits. There are times in your program when you would want to know what those minimum and maximum values are. Also bear in mind that the size of an int can be different with different compilers, so that information is provided to you through the limits.h header file.

#10

February 23rd, 2013, 05:28 AM

so.very.tired

Contributing User

Join Date: Nov 2012

Posts: 112

Time spent in forums: 1 Day 4 h 12 m 48 sec
Reputation Power: 1

OK.

that's the best i could come up with:

Code:

node_t FindClosestNode(node_t root, key_t key, dist_func_t distance)
{
	struct node* iterator=root, leftNode=NULL, rightNode=NULL;
	int dCurrent, dLeft, dRight;
	dCurrent=distance(iterator->key, key);

	if (iterator->left)
	{
		leftNode=FindClosestNode(iterator->left, key, distance);
		dLeft=distance(leftNode->key, key);
	}
	if (iterator->right)
	{
		rightNode=FindClosestNode(iterator->right, key, distance);
		dRight=distance(rightNode->key, key);
	}

	if ((!iterator->right)&&(!iterator->left))
		return iterator;
	if (!iterator->right)
		return dLeft<=dCurrent ? leftNode : iterator;
	if (!iterator->left)
		return dRight<=dCurrent ? rightNode : iterator;
	if ((iterator->right)&&(iterator->left))
	{
		if (dRight<=dCurrent) return rightNode;
		else if (dLeft<=dCurrent) return leftNode;
		else return iterator;

}

if anyone have tips/advices/ideas on how to make this code more efficient, i'd love to hear.

Need help with BST and search function

Developer Shed Advertisers and Affiliates