#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    132
    Rep Power
    3

    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.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    132
    Rep Power
    3
    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.
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    132
    Rep Power
    3
    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?
  6. #4
  7. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,413
    Rep Power
    1871
    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
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    132
    Rep Power
    3
    Hi salem.

    what does INT_MAX represent?
  10. #6
  11. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,413
    Rep Power
    1871
    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.
    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
  12. #7
  13. Transforming Moderator
    Devshed Supreme Being (6500+ posts)

    Join Date
    Mar 2007
    Location
    Washington, USA
    Posts
    14,232
    Rep Power
    9400
    Consider a tree like
    Code:
        10
       /  \
      2    12
     / \
    1   8
    and searching for 8.
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    132
    Rep Power
    3
    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...
  16. #9
  17. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,242
    Rep Power
    2222
    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.
  18. #10
  19. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    132
    Rep Power
    3
    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.

IMN logo majestic logo threadwatch logo seochat tools logo