Re: Nested Sets Insertion

From: Mikito Harakiri <mikharakiri_at_ywho.com>
Date: Tue, 13 May 2003 10:02:47 -0700
Message-ID: <dF9wa.6$Hl.73@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. Received on Tue May 13 2003 - 12:02:47 CDT