Binary Tree Help
I have a project where I need to build a binary tree with random floats and count the comparisons made. The problem I'm having is I'm not sure where to place the comaprison count in my code. Here's where I have it:
publicvoid insert(float idata)
{
Node newNode =new Node();
newNode.data = idata;
if(root==null)
root = newNode;
else
{
Node current = root;
Node parent;
while(true)
{
parent = current;
if(idata < current.data)
{
comp++;
current = current.leftc;
if(current ==null)
{
parent.leftc = newNode;
return;
}
}
else
{
current = current.rightc;
if(current ==null)
{
parent.rightc = newNode;
return;
}
}
}
}
}//end insert
Do I have it in the right place? Also, if I'm building the tree for 10,000 numbers would I get a new count for each level or would I get one count for comparisons? I'd appreciate anyone's help on this.
[2019 byte] By [
Nic_C78a] at [2007-11-27 8:56:16]
Plz give implementation of Node
What do you mean? You need to see all of my code?
if idata is equal to, or larger than current.data then you're not increasing your counter, but you DID make a comparison. Move the comp++; above theif(idata < current.data).
> Sweet, Thanks!You're welcome.
one more question. Should I only be receiving one count of comparisons or will I get several for each level? I'm supposed to be generating a random set of 10,000 floats and keeping track of the number of comparisons. I'm getting many different numbers in my output.
> one more question. Should I only be receiving one
> count of comparisons or will I get several for each
> level?
One comparison will represent one hop to the next level of your tree.
> I'm supposed to be generating a random set
> of 10,000 floats and keeping track of the number of
> comparisons. I'm getting many different numbers in
> my output.
That is not surprising at all. Take the following trees with the same nodes for example:
Tree A, insert order: 5,3,7,1,6,8,4
5
/ \
/\
37
/ \/ \
24 68
Tree B, insert order: 7,8,6,5,4,3,2
7
/ \
68
/
5
/
4
/
3
/
2
Now try inserting the number 1 in both trees.
what I mean is, I'm getting a list of numbers in my output like this as an example:
0
3
4
16
20...
It keeps going until it reaches somewhere around 30 thousand. Is that right or do I have something wrong in my code? I thought I should just get one number telling me the amount of comparisons made.
> what I mean is, I'm getting a list of numbers in my
> output like this as an example:
>
> 0
>
> 3
>
> 4
>
> 16
>
> 20...
>
> It keeps going until it reaches somewhere around 30
> thousand. Is that right or do I have something wrong
> in my code? I thought I should just get one number
> telling me the amount of comparisons made.
You never reset the comp variable, so each time you insert into the tree, it adds the number of inserts to the previous value.
> what I mean is, I'm getting a list of numbers in my output
> like this as an example:
> ...
I looks like you're printing your counter while a test is running. Only print it when you're done testing.
> It keeps going until it reaches somewhere around 30
> thousand. Is that right or do I have something wrong
> in my code? I thought I should just get one number
> telling me the amount of comparisons made.
Yes, I thought that that was your aim. And that number can vary quite a lot between different tests like I showed in my example.
> ...> You never reset the comp variable, so each time you> insert into the tree, it adds the number of inserts> to the previous value.Yes, or something like that. I'm not sure what the OP really means.
> > ...
> > You never reset the comp variable, so each time
> you
> > insert into the tree, it adds the number of
> inserts
> > to the previous value.
>
> Yes, or something like that. I'm not sure what the OP
> really means.
Yeah, it's hard to be sure without seeing the rest of the code.
> > what I mean is, I'm getting a list of numbers in my
> output
> > like this as an example:
> > ...
>
> I looks like you're printing your counter while a
> test is running. Only print it when you're done
> testing.
>
>
> > It keeps going until it reaches somewhere around
> 30
> > thousand. Is that right or do I have something
> wrong
> > in my code? I thought I should just get one
> number
> > telling me the amount of comparisons made.
>
> Yes, I thought that that was your aim. And that
> number can vary quite a lot between different tests
> like I showed in my example.
ok, so the last number that I see in my output is the total comparison count. Am I understanding that correctly?
> > > ...
> > > You never reset the comp variable, so each time
> > you
> > > insert into the tree, it adds the number of
> > inserts
> > > to the previous value.
> >
> > Yes, or something like that. I'm not sure what the
> OP
> > really means.
>
> Yeah, it's hard to be sure without seeing the rest of
> the code.
Sorry, I thought I had already posted my code for you to look at.
Here's a copy of it:
class Node
{
public float data;
public Node leftc;
public Node rightc;
}
public class Btree
{
private Node root;
private int comp;
//-
public Btree(int value)
{
root = null;
}
//-
public void insert(float idata)
{
Node newNode = new Node();
newNode.data = idata;
if(root==null)
root = newNode;
else
{
Node current = root;
Node parent;
while(true)
{
parent = current;
comp++;
if(idata < current.data)
{
current = current.leftc;
if(current == null)
{
parent.leftc = newNode;
return;
}
}
else
{
current = current.rightc;
if(current == null)
{
parent.rightc = newNode;
return;
}
}
}
}
}//end insert
//
public void display()
{
//System.out.print();
System.out.println("");
System.out.println(comp);
}
} //end Btree
//-
class BtreeApp
{
public static void main(String[] args)
{
int value = 10000;
Btree theTree = new Btree(value);
for(int j=0; j<value; j++)
{
float n = (int) (java.lang.Math.random() *99);
theTree.insert(n);
theTree.display();
}
}
}
>
> ...> ok, so the last number that I see in my output is the> total comparison count. Am I understanding that> correctly?Yes, if all you N-nodes have been inserted, the counter will hold the total number of hops made by all nodes.
> ...> Sorry, I thought I had already posted my code for you> to look at. > Here's a copy of it:> > ...Ok, just move the linetheTree.display();in your BtreeApp class after the for-statement is done inserting.
that fixed it. Thank you so much for your time and help!!!
