idont understand why i get this resolt

[alex lotel]

ihave built all the functions for the binary tree
i added a members

i built a search method

and it says that there is no such object
i cant understand why???
[code]

public class main {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
btree t=new btree();
int x=7;

t.insert(x);
t.insert(x);
t.insert(x);

System.out.println(t.find(x));
}

}



public class bnode {

private bnode left;
private bnode right;
private Object data;


bnode(Object data)
{
this.data=data;
left=null;
right=null;

}
public void insert(Object x)
{
double i;
i=Math.random();
if (i>=0.5)
{
if (right==null){
this.right=new bnode(x);
}
else
{
right.insert(x);
}

}
if (i<0.5){
if (left==null){
this.left=new bnode(x);
}
else
{
left.insert(x);
}
}
}
public boolean find(Object x){

if (this.data.equals(x)) {
return true;

}
else
{
if (right!=null){
right.find(x);
}

if (left!=null){
left.find(x);
}
}
return false;
}
}



public class btree {
bnode root;

btree()
{
root=null;
}

public void insert(Object x)
{
if (root==null){
root=new bnode(x);
}
else
{
root.insert(x);
}
}

public boolean find(Object x)
{

if (root.equals(x)){
return true;
}
else
{
root.find(x);

}

return false;
}
}

[/code

[Joanne Neal]

When you do find a match, you are not allowing this result to return up your recursive tree. You need to check the result of the call to right.find() and, only if it is false, should you call left.find(). If right.find returns true, you should return true straight away, otherwise you should return the result of left.find().

[Ernest Friedman-Hill]

Well, at first glance, I see three categories of major problems here. First of all, sometimes you say something like "if (node.equals(x))" when in fact you mean "if (node.x.equals(x))". I think the best way to deal with this is just not to use equals() -- instead, give bnode a "contains" method, which makes the intent clearer, and then perhaps have contains() throw an exception if called with a bnode as an argument -- this will let you find programming problems quickly.

The second kind of problem is that you call functions recursively, but ignore the results. Your find() method will call find() on each of its subtrees, ignore their return values, then return false unconditionally. find() has to check whether the recursive call(s) succeed and if so, return true!

Thirdly, this is a pretty crazy tree in that it stores things randomly in one subtree or another. The performance of find() is therefore linear in the number of items in the tree, instead of logarithmic, since the tree has no idea where to find an object! The left/right decision should be based on something repeatable -- whether the return value of x.hashCode() is even or odd, for example.

[Ravikanth kolli]

the main problem occurs in the find method of the btree. The search is actually implemented at the bnode level and "find" in the bnode searches the entire tree for the node, and thus returns a value.
It would be sufficient to call bnode find method in btree find method and return that value and that would work.

The actual problem here is that the elements are added into the B Tree but there is a simple logical error in the implementation.

Thanks hope this helps

[alex lotel]

what simple logical error???

i have written a search function than when it finds the object it returns true and there the method stops


if it wont find anything it will return false in the end

what the problem with that???

in this case my object is in the root
so in the first IF in the btree class
it was supposed to return true

what is the error??

[Ravikanth kolli]

The problems are the same identified by Ernest.

In line

if (root.equals(x)){

a comparision is being made between the bnode and an object. which can never be equal. The point is that bnode contains an object of type "data" that should be used for comparing.

So it should be something like

 if(root.data.equals(x))  

And also

  public boolean find(Object x)
{
 
if (root.equals(x)){
return true;
}
else
{
root.find(x);
 
}
 
return false;
}  

The else part calls the method find from bnode which returns "true" if the element is present in the complete tree.
The error here is that you are not taking care of the value returned from the find method of bnode. So the above code just returns false if the element is not present in the root.
if you had something like return root.find(x); then it would have worked.

[alex lotel]

so i need to change it like that??

public boolean find(Object x){ 
if (root.equals(x)){return true;
}
else{
return root.find(x); 
} 
return false;
}  

[Ravikanth kolli]

just a call to find method of bnode is sufficient

So you should be changing the "find method" of btree something like

  public boolean find(Object x)
{
return root.find(x);
}  

this would call the find method of bnode which searches the complete list of elements in the tree and returns true if it finds the element or false if it doesnot

[Rob Spoor]

Technically the following is sufficient, since bnode.find(Object) already checks its own object:

public boolean find(Object x)
{
    if (root == null)
    {
        return false;
    }
    else
    {
        return root.find(x);
    }
    // return false here will not compile since this code will never be reached!
}

Or shorter:

public boolean find(Object x)
{ 
    return (root == null ? false : root.find(x));
}

using the ternary operator.

[Jim Yingst]

Or:

public boolean find(Object x)
{ 
    return (root != null) && root.find(x);
}

[ March 04, 2008: Message edited by: Jim Yingst ]

[alex lotel]

// return false here will not compile since this code will never be reached!



why it wont be reached
is it because bnode will give you all the options??
??
[ March 04, 2008: Message edited by: donaldth smithts ]

[Campbell Ritchie]

Originally posted by donaldth smithts:
why it wont be reached
is it because bnode will give you all the options??
??[ March 04, 2008: Message edited by: donaldth smithts ]

No, but because the rpeceding code has a "return" in an "else" block. Follow the execution with pencil and paper and see what happens should the "if" condition NOT be fulfilled. You get the "else." Whatever follows the "return" cannot ever be executed. Hence the compiler error.

[Rob Spoor]

The same goes for throwing exceptions, or looping without a break:

while (true)
{
    // do something
}
// no code can go here unless there is a break in the loop

This is because this code can never ever be reached. Now of course the compiler could have ignored the code and give a warning, but Sun has decided to make it an error instead.