# Re: Nested Sets Insertion

Date: Tue, 13 May 2003 16:39:13 -0400

Message-ID: <Dodwa.391$A17.74711092_at_mantis.golden.net>

"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)Received on Tue May 13 2003 - 22:39:13 CEST