February 21st, 2013, 08:48 AM

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 09:05 AM.
February 21st, 2013, 10:09 AM

Yay!
i did it. :D
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 10:12 AM.
February 22nd, 2013, 09:12 AM

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, 09:49 AM

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.
February 22nd, 2013, 01:10 PM

Hi salem.
what does INT_MAX represent?
February 22nd, 2013, 02:00 PM

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, 02:14 PM

Consider a tree like
Code:
10
/ \
2 12
/ \
1 8
and searching for 8.
February 22nd, 2013, 02:57 PM

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, 02:59 PM

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.
February 23rd, 2013, 06:28 AM

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.