12 replies to this topic

[fread]

Im having problems developing and algorithm to search for the smallest number greater than a given key in a binary tree( a search tree).
The thing is if wei encounter a node greater than key say root, now i know if root has no left we should just return root. but if root has a left, then we have a whole new problem. The desired node can be any where in the left subtree of the current root node. It is possible to encounter nodes greater than and less than the key we seek.Go left go right...confused totally at this point...all algorithms thus far failed in pencil and paper, never made it to code stage. No work on right subtree done as yet. Creeping to walk.

any ideas, links etc would be appreciated

[dcs]

Eternally Confuzzled - Binary Search Trees I ?

[fread]

sinscere apologies. its not a search tree i meant to put. thats what been causing the problems. The searches is just kind of random, or like an inorder or preorder, jut return when found eventually. So deciding to go left or right is entirely based on the success of the search.
I apologise again for that

[WingedPanther]

You're thinking about it wrong. You will always have a temp pointer.

If the root is larger, you look for a left node of the root. If that node exists and is larger, you move your temp pointer to it and look at its left node. Repeat.

[fread]

WingedPanther said:

You're thinking about it wrong. You will always have a temp pointer.

If the root is larger, you look for a left node of the root. If that node exists and is larger, you move your temp pointer to it and look at its left node. Repeat.

Below is the binary tree we are searching. "B" is the node we want. "B" is less than "C" so we go left. "B" is less than "E" so we so we go left to "F". This is the confusing part. So we need to traverse the entire tree probably like an inorder so preorder and only return when found.
"B" is to the right of "E". This is possible b/c this is not a search tree.

                   

                 C

	    /   \

 	  /       \

           E          G

         /   \      /   \

       /       \  /       \

      F        B A       N

        \                /   \

          \            /       \

           H         J	      K

[WingedPanther]

So the location of the nodes is more or less random? If you are not keeping your elements ordered, you cannot even assume that B will be on the left branch of C. In that case, your options would be to sort the tree and THEN perform your search, or traverse the entire tree as if you were doing a selection search.

[fread]

WingedPanther said:

So the location of the nodes is more or less random? If you are not keeping your elements ordered, you cannot even assume that B will be on the left branch of C. In that case, your options would be to sort the tree and THEN perform your search, or traverse the entire tree as if you were doing a selection search.

Right. We threw in a couple of printf's to watch what values go where during the recursive calling, but even when we find it(with the code in original) it doesn't just return all the way back to first call. It still executes statements proceeding the 'test statement' and continues straight through going on and on comparing "key" against every other node. the problem is not finding the node, but, once found to return immediately as far up as possible one "backstep" at a time.
We were trying to do this without sorting.

[CPD]

The problem is no different from searching any random set unless you can give more structure to the binary tree. I read "smallest number greater than a given key" the same as a find the smallest algorithm:

int found = 0;

int smallest;


void find_min_impl(struct node *root, int key)

{

  if (root) {

    find_min_impl(root->left);


    if (!found) {

      if (root->key > key) {

        smallest = root->key;

        found = 1;

      }

    }

    else if (root->key > key && root->key < smallest)

      smallest = root->key;


    find_min_impl(root->right);

  }

}


void find_min(struct node *root, int key)

{

  if (root->key > key) {

    smallest = root->key;

    found = 1;

  }


  find_min_impl(root, key);

}

Or do you mean the smallest key back up the path to the root?

[fread]

I think we get the idea. The algorithm worked. Much thanks for your help. We are on a quest to solve every question in a text. Sooner or later we may post again.

[Steve.L]

The only way to solve your problem is to iterate through the entire tree, thus giving you the incredibly inefficient running time of O(n), instead of O(logn) from a BST.

[CPD]

Quote

thus giving you the incredibly inefficient running time of O(n), instead of O(logn) from a BST.

It's not a BST though, it's a BT. I don't remember linear time ever being described as "incredibly inefficient", even in hash table theory. "Undesirably inefficient" when simple algorithms are available that run faster, but never incredibly so. ;)

[Steve.L]

CPD said:

It's not a BST though, it's a BT. I don't remember linear time ever being described as "incredibly inefficient", even in hash table theory. "Undesirably inefficient" when simple algorithms are available that run faster, but never incredibly so. ;)

Consider when the number of nodes in your BT gets sufficiently large. O(n) is not very efficient, when you have to process and compare a few thousand values, as opposed to simply finding the correct value in a few steps. Using a BST here is essential.

Edited by Steve.L, 24 November 2008 - 02:48 PM.