Re: Nested Sets Insertion

"Bob Badour" <bbadour_at_golden.net> wrote in message news:Dodwa.391$A17.74711092_at_mantis.golden.net...
> > ? In the example below vertices are marked as (preorder#,postorder#)
> >
> > (1,1) <- (2,3)
> > (1,1) <- (5,2)
> > (2,3) <- (3,5)
> > (2,3) <- (4,4)
> >
> > where "<-" is "parent of". Now if we change second coordinate to 6 -
> > postorder#, then the labeling is identical to Nested Sets.
>
> Mikito,
>
> How can the root be the first in both pre-order and post-order? Wouldn't
> (pre-order, post-order) have to be something like the following where the
> root is the first in one order and the last in the other order?
>
> (1,5) <- (2,3)
> (2,3) <- (3,1)
> (2,3) <- (4,2)
> (1,5) <- (5,4)

You are correct, my "postorder" actually was <root, right, left>.

Here is how to reduce the original case to Nested Intervals. (Nested Intervals don't have a property where interval length right - left equals number of descendants).

left = total#vertices - postorder# +1
right = 2*total#vertices - preorder#

In the example above

total#vertices = 5

(preorder=1,postorder=5) translates into (left=1,right=9)
(preorder=2,postorder=3) translates into (left=3,right=8)
(preorder=4,postorder=2) translates into (left=4,right=6)
(preorder=5,postorder=4) translates into (left=2,right=5)
(preorder=3,postorder=1) translates into (left=5,right=7)

Here intervals are allowed to overlap, but the criteria for 2 nodes being in accendant-descendant relationship is still nesting of the intervals.

It would be interesting to know if there is a linear transformation that can map (pre-order, post-order) labeling schema into Nested Sets. Received on Tue May 13 2003 - 23:48:52 CEST