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 ]
 LudovicoVan Posts: 4,165 From: London Registered: 2/8/08
Re: An Argument for the Subroot Node
Posted: Mar 11, 2008 8:16 PM

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