Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 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

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 Tony Orlow
3/11/08 Virgil
3/11/08 G. Frege
3/11/08 Tony Orlow
3/11/08 Virgil
3/11/08 Tony Orlow
3/11/08 Virgil
3/11/08 G. Frege
3/11/08 J. Antonio Perez M.
3/11/08 G. Frege
3/11/08 G. Frege
3/11/08 Tony Orlow
3/11/08 briggs@encompasserve.org
3/14/08 Tony Orlow
3/14/08 David R Tribble
3/14/08 LudovicoVan
3/11/08 Tony Orlow
3/11/08 J. Antonio Perez M.
3/11/08 Tony Orlow
3/11/08 Tony Orlow
3/11/08 Tony Orlow
3/11/08 LudovicoVan
3/11/08 LudovicoVan
3/14/08 Tony Orlow
3/14/08 LudovicoVan
3/14/08 LudovicoVan
3/11/08 David R Tribble
3/11/08 LudovicoVan
3/11/08 LudovicoVan