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