Re: Encoding materialized path in an atomic value.

From: David Cressey <david.cressey_at_earthlink.net>
Date: Sat, 24 Sep 2005 19:59:39 GMT
Message-ID: <LeiZe.4395$q1.1085_at_newsread3.news.atl.earthlink.net>


"VC" <boston103_at_hotmail.com> wrote in message news:eYadnd0PbbUUyqjeRVn-jg_at_comcast.com...
>
> "David Cressey" <david.cressey_at_earthlink.net> wrote in message
> news:ewZYe.2909$vw6.917_at_newsread1.news.atl.earthlink.net...
> .
> ..
> > This only works for binary trees, but the same technique can be
> > generalized, or a technique can be used for reducing arbitrary trees to
> > binary tree equivalents.
>
> There is one-to-one mapping between binary trees and ordered trees. So
you
> can convert an arbitrary tree to an ordered tree by imposing some kind of
> [artificial] order amongst siblings, and then to a binary one at the
expense
> of changing the original tree topology -- the first sibling becomes the
new
> parent for the second sibling, and so on.
>

Yes. This is basically, IIUYR, the way Lisp represents arbitrary trees as lists of lists.
The "car" is the eldest child, and the "cdr" is the next sibling.

(The point about imposing an articicial order amongst siblings neatly summarizes an extended debate between dawn and many of the rest of us concerning the relationship between sets and list.)

> By the way, representing the materialized path as '1.22.7.16' rather than
> 'john.kate.bob.sam' is an example of converting an unordered tree to an
> ordered one.

Yes. And nested sets imposes an order as well.... the order in which the "little worm" visits the nodes. Received on Sat Sep 24 2005 - 21:59:39 CEST

Original text of this message