GeeCON Prague 2014*
The moose likes Java in General and the fly likes idont understand why i get this resolt Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Java » Java in General
Bookmark "idont understand why i get this resolt" Watch "idont understand why i get this resolt" New topic
Author

idont understand why i get this resolt

alex lotel
Ranch Hand

Joined: Feb 01, 2008
Posts: 191
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
Rancher

Joined: Aug 05, 2005
Posts: 3600
    
  15
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().


Joanne
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

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.


[Jess in Action][AskingGoodQuestions]
Ravikanth kolli
Ranch Hand

Joined: Feb 10, 2008
Posts: 179

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


-kolli
alex lotel
Ranch Hand

Joined: Feb 01, 2008
Posts: 191
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
Ranch Hand

Joined: Feb 10, 2008
Posts: 179

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


And also



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
Ranch Hand

Joined: Feb 01, 2008
Posts: 191
so i need to change it like that??

Ravikanth kolli
Ranch Hand

Joined: Feb 10, 2008
Posts: 179

just a call to find method of bnode is sufficient

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



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
Sheriff

Joined: Oct 27, 2005
Posts: 19697
    
  20

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

Or shorter:

using the ternary operator.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
Or:

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

"I'm not back." - Bill Harding, Twister
alex lotel
Ranch Hand

Joined: Feb 01, 2008
Posts: 191
// 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
Sheriff

Joined: Oct 13, 2005
Posts: 39044
    
  23
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
Sheriff

Joined: Oct 27, 2005
Posts: 19697
    
  20

The same goes for throwing exceptions, or looping without a break:
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.
 
GeeCON Prague 2014
 
subject: idont understand why i get this resolt