The Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: An Argument for the Subroot Node
Replies: 28   Last Post: Mar 14, 2008 8:32 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Tony Orlow

Posts: 3,142
Registered: 8/23/06
Re: An Argument for the Subroot Node
Posted: Mar 14, 2008 12:44 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Julio Di Egidio wrote:
> I'll take my definition from Sedgewick, "Algorithms in C", 1990
> (1946), chapter "Fundamentals":
>
> "A _tree_ is a nonempty collection of _vertices_ and _edges_ that
> satisfies certain requirements. A vertex is a simple object (also
> referred to as a _node_) that can have a name and can carry other
> associated information; an edge is a connection between two vertices.
> A _path_ in a three is a list of distinct vertices in which
> successive vertices are connected by edges in the tree. One node in
> the tree is designated as the _root_ === the defining property of a
> tree is that there is exactly one path between the root and each of
> the other nodes in the tree. If there is more than one path between
> the root and some node, then what we have is a graph, not a tree."
>
> If I take this definition from granted, the appearance of a sub-root
> is indeed intrinsic to the structure so defined.


:)

>
> And, by "intrinsic", I mean not only it is not a contradiction, it is
> _actually_ required for "no-exception" implementations of the various
> algorithms, as Mr Sedgewick shows along the pages, and as any good
> programmer would do.


I certainly think it makes perfect sense, when one reverse-engineers the
tree, but it might introduce an exception in place of the one it
eliminates, if one insists on considering self reference to be a cycle.

>
> Maybe pure mathematics forgets that "this stuff" must "run
> somewhere", doesn't it? More seriously, I'd simply call this the
> "natural" definition of a tree.


The only funny part is that on level -1, where there should be 2^-1
nodes, or 1/2 of a node, there is one. But, it's its own half parent,
so...that kinda makes sense.

>
> BTW, sort of joking instead - if you don't get that concept of
> "exception-free", you wouldn't pass Informatics 1 around here. (Was
> puzzled by that article on American Math education: no mention for
> programming... not that in Italy they do it so much, anyway...)
>
> Diving a bit:
>
> The most primitive complex type presented in the book is the _array_.
> After that, you have the _linked-list_, where already you need your
> "dummy node" for self-contained computation, that is one
> exception-free.


It needs at least a max, for appending elements and such, one extra element.

>
> I said "already"? Actually, the array itself (think computer RAM) is
> implemented low level as a more or less convoluted form of a
> linked-list, so that _node_ and _egde_ is "foundational", and _root_
> defines _tree_.
>
> I'd call this: The "exclusiveness of the root". :)
>
> Indeed, there is not even an up-down direction: The position of the
> dummy is usually at the "leafs", though it really depends which
> "direction" you need to trasverse...
>
> Julio


Thanks for your input, Julio. :)

Tony


Date Subject Author
3/11/08
Read An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Virgil
3/11/08
Read Re: An Argument for the Subroot Node
G. Frege
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Virgil
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Virgil
3/11/08
Read Re: An Argument for the Subroot Node
G. Frege
3/11/08
Read Re: An Argument for the Subroot Node
J. Antonio Perez M.
3/11/08
Read Re: An Argument for the Subroot Node
G. Frege
3/11/08
Read Re: An Argument for the Subroot Node
G. Frege
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
briggs@encompasserve.org
3/14/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/14/08
Read Re: An Argument for the Subroot Node
David R Tribble
3/14/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
J. Antonio Perez M.
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/11/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/11/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/14/08
Read Re: An Argument for the Subroot Node
Tony Orlow
3/14/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/14/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/11/08
Read Re: An Argument for the Subroot Node
David R Tribble
3/11/08
Read Re: An Argument for the Subroot Node
LudovicoVan
3/11/08
Read Re: An Argument for the Subroot Node
LudovicoVan

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.