Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> 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 - 16:48:52 CDT