
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 subroot > 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 "noexception" 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 reverseengineers 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 > "exceptionfree", 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 _linkedlist_, where already you need your > "dummy node" for selfcontained computation, that is one > exceptionfree.
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 > linkedlist, 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 updown 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

