Velocity Reviews > Binary trees

Binary trees

n.noumia@gmail.com
Guest
Posts: n/a

 05-03-2007
- with 10 nodes, give one example of an unbalanced binary tree and
one example of a balanced binary tree
- what is the advantage of having a balanced binary tree over an
unbalanced tree?
- number your nodes, then give the order in which nodes will be
visited by a depth-first-search
- explain the differences between traversing the tree pre-order, in-
order and post-order

Dave Vandervies
Guest
Posts: n/a

 05-04-2007
In article <(E-Mail Removed). com>,
<(E-Mail Removed)> wrote:
> - with 10 nodes, give one example of an unbalanced binary tree and
>one example of a balanced binary tree

Example of a balanced binary tree: [IMAGE]
Example of an unbalanced binary tree: [IMAGE]

> - what is the advantage of having a balanced binary tree over an
>unbalanced tree?

A balanced tree won't fall over when you stop holding it.

> - number your nodes, then give the order in which nodes will be
>visited by a depth-first-search

42, pi, 17, e, 105, 69, i, sqrt(2), 3, -1.

> - explain the differences between traversing the tree pre-order, in-
>order and post-order

The order you traverse it in is different.

DYODH.

dave

--
Dave Vandervies http://www.velocityreviews.com/forums/(E-Mail Removed)
Hey, I can beat him on the Impressive But Useless certificates thing.
I have a PhD.
--Dan Holdsworth in the scary devil monastery

Eric Sosman
Guest
Posts: n/a

 05-04-2007
(E-Mail Removed) wrote:
> - with 10 nodes, give one example of an unbalanced binary tree and
> one example of a balanced binary tree

from Knuth, TAOCP 2.3.3 equation 3)

To balance the tree, put another one on the other pan.

> - what is the advantage of having a balanced binary tree over an
> unbalanced tree?

the unbalanced tree, the balanced tree that's over it will fall
at the same time and save you the work of cutting it down.

> - number your nodes, then give the order in which nodes will be
> visited by a depth-first-search

Numbers: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Depth-first order: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

> - explain the differences between traversing the tree pre-order, in-
> order and post-order

With pre-order, the pizza is ready when you arrive at the
shop and you needn't wait. With in-order, you may need to pay
a restaurant tax to eat the pizza on the premises. With post-
order, the pizza reaches you three to five business days later
and is unpalatable.

--
Eric Sosman
(E-Mail Removed)lid

Chris Dollin
Guest
Posts: n/a

 05-04-2007
(E-Mail Removed) wrote:

> - with 10 nodes, give one example of an unbalanced binary tree and
> one example of a balanced binary tree
> - what is the advantage of having a balanced binary tree over an
> unbalanced tree?
> - number your nodes, then give the order in which nodes will be
> visited by a depth-first-search
> - explain the differences between traversing the tree pre-order, in-
> order and post-order

I think you should have posted to comp.lazy.domyhomework, since (a)
this is homework; having someone else do it for you misses the point;
(b) it's off-topic, since it isn't about C at all.

--
Not A Number, A Free Hedgehog
Meaning precedes definition.

Clever Monkey
Guest
Posts: n/a

 05-04-2007
(E-Mail Removed) wrote:
> - with 10 nodes, give one example of an unbalanced binary tree and
> one example of a balanced binary tree

http://en.wikipedia.org/wiki/Binary_tree

> - what is the advantage of having a balanced binary tree over an
> unbalanced tree?

A balanced tree will not fall over in a storm, as long as the wind blows
evenly from all directions.

> - number your nodes, then give the order in which nodes will be
> visited by a depth-first-search

http://en.wikipedia.org/wiki/Binary_...th-first_order

> - explain the differences between traversing the tree pre-order, in-
> order and post-order
>

http://en.wikipedia.org/wiki/Binary_...rder_traversal.

--
clvrmnky

Direct replies will be blacklisted. Replace "spamtrap" with my name to
contact me directly.

Dave Vandervies
Guest
Posts: n/a

 05-04-2007
In article <6NI_h.7930\$(E-Mail Removed)!nnrp1.uunet.ca >,
Clever Monkey <(E-Mail Removed)> wrote:
>(E-Mail Removed) wrote:

>> - what is the advantage of having a balanced binary tree over an
>> unbalanced tree?

>A balanced tree will not fall over in a storm, as long as the wind blows
>evenly from all directions.

But the wind in most storms doesn't blow evenly from all directions.
If you're going for storm tolerance, you really want an unbalanced tree,
but the problem with that is that every time the wind changes you have
to go out and re-unbalance it for the new wind direction.

dave

--
Dave Vandervies (E-Mail Removed)
And there was nothing insulting about it. Some people would rather
take being called a ``normal person'' as an insult.
--Nils Goesche in comp.lang.c

Dave Vandervies
Guest
Posts: n/a

 05-04-2007
In article <(E-Mail Removed)>,
Eric Sosman <(E-Mail Removed)> wrote:
>(E-Mail Removed) wrote:
>> - with 10 nodes, give one example of an unbalanced binary tree and
>> one example of a balanced binary tree

>
> Unbalanced tree: AB,C'K'EH:FJ:G: (notation adapted
>from Knuth, TAOCP 2.3.3 equation 3)

Unless you have a different edition than I do (3rd), I think you meant
equation 4.

dave

--
Dave Vandervies (E-Mail Removed)
The DS 9000 is a conforming implementation.
The DS 9001 is so cleverly designed that experts can't agree whether it
is conforming or not! --Christian Bau in comp.lang.c

Eric Sosman
Guest
Posts: n/a

 05-04-2007
Dave Vandervies wrote On 05/04/07 16:08,:
> In article <(E-Mail Removed)>,
> Eric Sosman <(E-Mail Removed)> wrote:
>
>>(E-Mail Removed) wrote:
>>
>>> - with 10 nodes, give one example of an unbalanced binary tree and
>>>one example of a balanced binary tree

>>
>> Unbalanced tree: AB,C'K'EH:FJ:G: (notation adapted

>
>>from Knuth, TAOCP 2.3.3 equation 3)

>
> Unless you have a different edition than I do (3rd), I think you meant
> equation 4.

The renumbering was part of the adaptation.

--
(E-Mail Removed)

Clever Monkey
Guest
Posts: n/a

 05-04-2007
Dave Vandervies wrote:
> In article <6NI_h.7930\$(E-Mail Removed)!nnrp1.uunet.ca >,
> Clever Monkey <(E-Mail Removed)> wrote:
>> (E-Mail Removed) wrote:

>
>>> - what is the advantage of having a balanced binary tree over an
>>> unbalanced tree?

>> A balanced tree will not fall over in a storm, as long as the wind blows
>> evenly from all directions.

>
> But the wind in most storms doesn't blow evenly from all directions.
> If you're going for storm tolerance, you really want an unbalanced tree,
> but the problem with that is that every time the wind changes you have
> to go out and re-unbalance it for the new wind direction.
>

So true. I think I'm barking up the wrong tree here. We better leaf
this alone for while, or we might end up branching off into the wrong
direction. If I twig onto anything else, I'll let you know, but I think
this conversation will not bear any new fruit. Either that, or I'm the
fall guy and can't see the tree for the forest.

--
clvrmnky

Direct replies will be blacklisted. Replace "spamtrap" with my name to
contact me directly.