Re: Encoding materialized path in an atomic value.
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.
> 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