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 ]
LudovicoVan

Posts: 4,151
From: London
Registered: 2/8/08
Re: An Argument for the Subroot Node
Posted: Mar 11, 2008 8:16 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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 three 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.

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.

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.

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


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.