Calling fire and forget methods.

[Davy J]

Hi all.
I've got a Binary tree implementation that I need a little help with.
my problem is the recursive lhs.Add(item) and rhs.Add(item) call, is there
any way I could refactor this to remove the stack dependancy?

the application is written in Net.2.0 , so no fancy linq replys please :)

Cheers

Dave.

the psudeo code for the Add function. (written in gmail's c# editor)

public void Add(T item)
{
if (this.item == null)
{
this.item = item;
return;
}
if (item < this.item)
{
if (lhs == null)
{
lhs = new TreeNode<T>();
}
lhs.Add(item);
}
else
{
if (rhs == null)
{
rhs = new TreeNode<T>();
}
rhs.Add(item);
}
}

===================================
This list is hosted by DevelopMentor® http://www.develop.com

View archives and manage your subscription(s) at http://discuss.develop.com

[Stoyan Damov]

Sure -

current item = root item

while (item being added less than current item)
{
current item = current item.left child
}

while (item being added bigger than current item)
{
current item = current item.right child
}

current item.add(item)

That helps?

Cheers

Post by Davy J
Hi all.
I've got a Binary tree implementation that I need a little help with.
my problem is the recursive lhs.Add(item) and rhs.Add(item) call, is there
any way I could refactor this to remove the stack dependancy?
the application is written in Net.2.0 , so no fancy linq replys please :)
Cheers
Dave.
the psudeo code for the Add function. (written in gmail's c# editor)
public void Add(T item)
{
if (this.item == null)
{
this.item = item;
return;
}
if (item < this.item)
{
if (lhs == null)
{
lhs = new TreeNode<T>();
}
lhs.Add(item);
}
else
{
if (rhs == null)
{
rhs = new TreeNode<T>();
}
rhs.Add(item);
}
}
===================================
This list is hosted by DevelopMentor(R) http://www.develop.com
View archives and manage your subscription(s) at http://discuss.develop.com

===================================
This list is hosted by DevelopMentor® http://www.develop.com

View archives and manage your subscription(s) at http://discuss.develop.com

[Ryan Heath]

Be careful, this [1] is written in gmail's c# editor too ;)

HTH
// Ryan

[1]

TreeNode parent = this;
bool added = false;

while ( !added)
{
if ( parent.item == null)
{
parent.item = item;
added = true;
}
else if ( item < parent.item)
{
if ( parent.lhs == null)
{
parent.lhs = new TreeNode();
}
parent = parent.lhs;
}
else
{
if ( parent.rhs == null)
{
parent.rhs = new TreeNode();
}
parent = parent.rhs;
}
}

Post by Davy J
Hi all.
I've got a Binary tree implementation that I need a little help with.
my problem is the recursive lhs.Add(item) and rhs.Add(item) call, is there
any way I could refactor this to remove the stack dependancy?
the application is written in Net.2.0 , so no fancy linq replys please :)
Cheers
Dave.
the psudeo code for the Add function. (written in gmail's c# editor)
public void Add(T item)
{
if (this.item == null)
{
this.item = item;
return;
}
if (item < this.item)
{
if (lhs == null)
{
lhs = new TreeNode<T>();
}
lhs.Add(item);
}
else
{
if (rhs == null)
{
rhs = new TreeNode<T>();
}
rhs.Add(item);
}
}
===================================
This list is hosted by DevelopMentor(R) http://www.develop.com
View archives and manage your subscription(s) at http://discuss.develop.com

===================================
This list is hosted by DevelopMentor® http://www.develop.com

View archives and manage your subscription(s) at http://discuss.develop.com

[Frans Bouma]

It seems you didn't implement this as an array? With an array, it's very
simple.
See: http://en.wikipedia.org/wiki/binary_tree
for details.

FB

Post by Davy J
I've got a Binary tree implementation that I need a little help with.
my problem is the recursive lhs.Add(item) and rhs.Add(item) call, is there
any way I could refactor this to remove the stack dependancy?
the application is written in Net.2.0 , so no fancy linq replys please :)
Cheers
Dave.
the psudeo code for the Add function. (written in gmail's c# editor)
public void Add(T item)
{
if (this.item == null)
{
this.item = item;
return;
}
if (item < this.item)
{
if (lhs == null)
{
lhs = new TreeNode<T>();
}
lhs.Add(item);
}
else
{
if (rhs == null)
{
rhs = new TreeNode<T>();
}
rhs.Add(item);
}
}
===================================
This list is hosted by DevelopMentorR http://www.develop.com
View archives and manage your subscription(s) at http://discuss.develop.com

===================================
This list is hosted by DevelopMentor� http://www.develop.com

View archives and manage your subscription(s) at http://discuss.develop.com

[Davy J]

Thanks all,

case of couldn't see the wood for the trees there. for info I don't know
if the tree will be balanced or not, so the array implementation wouldn't
fit.

Here's the finished method, shaves 10 seconds off of my previous best
try.


internal void Add(T newItem)
{
if (this.value == null) //Short cut for the first pass.
{
this.value = newItem;
this.valueComparer = (IComparable)pi.GetValue(value, null);
return;
}


TreeNode<T> parent = this; //set up our point to the
current node we're checking
IComparable newObject = (IComparable)pi.GetValue(newItem, null);
//Get an IComparable for property to sort by
while (true) //we exit with a break.
{
if(parent.value == null){ //we've found an empty base
object, fill it in
parent.value = newItem;
parent.valueComparer = newObject; //Pass our IComparable
to save time.
break; //the real exit to the while.
}
//if the parent value is bigger than the new object.
if (parent.valueComparer.CompareTo(newObject) > 0)
{
//Add it to our left side.
if (parent.leftNode == null)
{
parent.leftNode = new TreeNode<T>(pi); //Add the
left node
}
parent = parent.leftNode; //Move our pointer
}
else
{
if (parent.rightNode == null) //It's either the same
or bigger than our parent
{
parent.rightNode = new TreeNode<T>(pi); //No node to
fill? add one.
}
parent = parent.rightNode; //Move our pointer
}
}
}

===================================
This list is hosted by DevelopMentor® http://www.develop.com

View archives and manage your subscription(s) at http://discuss.develop.com

[Frans Bouma]

Post by Davy J
case of couldn't see the wood for the trees there. for info I don't know
if the tree will be balanced or not, so the array implementation wouldn't
fit.

unless you get the tree handed to you in the structure you've to work
with, building the binary tree in an array-based approach is always balanced.
Sure, you've to keep it balanced, though that has many advantages.

I'd seriously look into an array based approach, the code is simpler
and many binary tree implementations in various languages use that approach,
so the algorithm is well documented. A balanced version of a binary tree for
example offers a simple calculation to reach any child. With a node-based
tree, you've to traverse the path.

Though, if balancing isn't required, it might indeed be too much
overhead.

One tip which often occurs with 2/multi path tree structures: if
you're not careful, you're creating clones in your code: code which is similar
for left AND right and as this code is intertwined into eachother, it's hard
to recognize. Not sure if your structure is suitable to make things more
general (i.e. work on left/right regardless of left/right with 1 set of
routines, not 2). The less clones you have in your code, the more maintainable
the code is.

FB

Post by Davy J
Here's the finished method, shaves 10 seconds off of my previous best
try.
internal void Add(T newItem)
{
if (this.value == null) //Short cut for the first pass.
{
this.value = newItem;
this.valueComparer = (IComparable)pi.GetValue(value, null);
return;
}
TreeNode<T> parent = this; //set up our point to the
current node we're checking
IComparable newObject = (IComparable)pi.GetValue(newItem, null);
//Get an IComparable for property to sort by
while (true) //we exit with a break.
{
if(parent.value == null){ //we've found an empty base
object, fill it in
parent.value = newItem;
parent.valueComparer = newObject; //Pass our IComparable
to save time.
break; //the real exit to the while.
}
//if the parent value is bigger than the new object.
if (parent.valueComparer.CompareTo(newObject) > 0)
{
//Add it to our left side.
if (parent.leftNode == null)
{
parent.leftNode = new TreeNode<T>(pi); //Add the
left node
}
parent = parent.leftNode; //Move our pointer
}
else
{
if (parent.rightNode == null) //It's either the same
or bigger than our parent
{
parent.rightNode = new TreeNode<T>(pi); //No node to
fill? add one.
}
parent = parent.rightNode; //Move our pointer
}
}
}
===================================
This list is hosted by DevelopMentorR http://www.develop.com
View archives and manage your subscription(s) at http://discuss.develop.com

===================================
This list is hosted by DevelopMentor� http://www.develop.com

View archives and manage your subscription(s) at http://discuss.develop.com