Re: Nested Sets Insertion

"Mikito Harakiri" <mikharakiri_at_ywho.com> wrote in message news:dF9wa.6$Hl.73_at_news.oracle.com...
>
> "san" <sans11_at_hotmail.com> wrote in message
> news:8e29a54a.0305130547.1e9e47a1_at_posting.google.com...
> > Hi,
> > I had a question regarding the nested set idea. Can we use another
> > approach for such tree problems? We can assign each node two numbers
> > (preorder,postorder). preorder is the number in preorder traversal and
> > postorder is the postorder traversal number. Then, a node i is a
> > descendant of node j if preorder(i) < preorder(j) and postorder(i) >
> > postorder(j). This handles the queries in pretty much the same way as
> > the nested set model.
>
> Did you mean
>
> preorder(i) < preorder(j) and postorder(i) < postorder(j)
>
> ? 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)

Or do I have pre-order and post-order reversed? ...

(5,1) <- (3,2)
(3,2) <- (1,3)
(3,2) <- (2,4)
(5,1) <- (4,5)