Search algorithm of the Binary Search Tree
Could someone please tell me if this is the correct way to implement the search algorithm of the Binary Search Tree? (Using a standard Binary Search Tree)
abstract class BST {
public int data;
public BST left;
public BST right;
static public BST find(BST root, int value);
}
public class findBST extends BST {
static public BST find(BST root, int value)
{
if (root == null)
return null;
if (value < root)
return find(left, value);
else if (value > root)
return find(right, value);
else
return root;
}
}
[624 byte] By [
spazzzer] at [2007-11-11 8:15:51]
# 1 Re: Search algorithm of the Binary Search Tree
Usually a Tree has nodes which contain a value and references to the children (if one or both of them exist) of the node. The "root" of the tree (or subtree) refers to the node which does not have a parent.
You access the root and compare its value with the value you're looking for. If the values are equal, you're done. If the value in the root is larger than your search value, you move to its left child, otherwise root's right child.
Keep going until you hit "NULL" or find the value.
nspils at 2007-11-11 22:35:57 >
# 2 Re: Search algorithm of the Binary Search Tree
Thanks for the timely reply. Yeah I understand that, I just wanted someone to tell me if my search algorithm would work on a standard binary search tree.
# 3 Re: Search algorithm of the Binary Search Tree
What is your "can't find" condition? If your root doesn't have a child in the direction you're going to go, you haven't found the item ... what do you return, then?
nspils at 2007-11-11 22:38:01 >
# 5 Re: Search algorithm of the Binary Search Tree
Since this is your project I was interested in how you thought you should handle this.
Is your interest just knowing that you have found a value in your tree? If this is the case, I think a boolean value is what you want to return - a yes or a no.
If you are going to do something with the result of your search, such as insert or delete or print or modify a value or whatever, you want to have a reference to the node where the value exists, OR, something you can use for the purpose of signalling that you did not find a value and now you want to do something ... for this purpose, you probably want to return a reference to the node of the tree where your search ended.
nspils at 2007-11-11 22:39:59 >
# 6 Re: Search algorithm of the Binary Search Tree
Case 1 the tree is empty: then "value" is not present.
Case 2 left == right (the item is at the root): then the item "right", at the root is returned
Case 3 left < right : recursively search the left subtree.
Case 4 left > right : recursively search the right subtree.
your code seems to be adhering to the above rules.
arul at 2007-11-11 22:41:03 >
