Re: Adjacency list to Nested set model statement

In article <c0d87ec0.0202271438.12a87592_at_posting.google.com>, "--CELKO--" <71062.1056_at_compuserve.com> wrote:

> Here is the code; can you make it better?
>
> /* Stack holds the nested sets model; it is the push down stack for the
> tree traversal. Would an index or key help here? */
>
>

Do you really need a stack here? Traversing a tree consists of iteratively taking one of three moves, in this order of priority: down, right, up. Given the last node visited, it seems simple enough to figure out what the next one should be.

Maybe something like this:

create table node(

         node_id integer primary key, -- unique id
         parent_id integer null,  -- null only at root
         nodenum integer null  -- traversal ordinal, initially null
         maxchild null  -- the max. nodenum for subtree
         )

/*

The traversal order will be depth first, ordering siblings by node_id.

Each node will be given a nodenum when first encountered (on the way down/across). On the way up, nodenum's are already set, but maxchild can be brought up from below (although it's redundant IMHO).

*/

declare @last_node_visited integer;
declare @last_nodenum integer;

set @last_node_visited = @root_node -- assume this is passed in

set @last_nodenum = 1

update node set nodenum = 1 where node_id = @root_node

set @did_something = 1;

while ( @did_something = 1 ) /* 0 if no more moves */ begin

    set @did_something = 0

    /* down - look for unvisited child */     if exists (select * from tree where parent_id = @last_node_visited

               and nodenum is null )
         begin
          set @did_something = 1;

          /* get leftmost child */
          set @next_node = (select min(node_id) from node c
            where  c.parent_id = @last_nodenum
            )

          set @last_nodenum = @last_nodenum + 1;

          update node set nodenum = @last_nodenum 
          where node_id = @next_node;

          set @last_node_visited = @next_node;
         end  /* down  */

    /* across - look for right sibling */     else if exists (select * from node c, node c2

                    where c.node_id = @last_node_visited
                    and c.parent_id = c2.parent_id
                    and c2.node_id > c.node_id )
         begin
              set @did_something = 1;

              set @next_node = 
                 (select min(c2.node_id)
                 from node c, node c2
                 where c.node_id = @last_node_visited
                 and c.parent_id = c2.parent_id
                 and c2.node_id > c.node_id )

                set @last_nodenum = @last_nodenum + 1;

                update node set nodenum = @last_nodenum 
                where node_id = @next_node;

                set @last_node_visited = @next_node;
         end  /* across */

     /* up - set maxchild */
     else if exists (select * from node c
                     where c.node_id = @last_node_visited
                     and c.parent_id is not null )
         begin
              set @did_something = 1;
              set @next_node = 
                     (select parent_id from node c
                     where c.node_id = @last_node_visited
                     and c.parent_id is not null )

              /* don't increment @last_nodenum */

              /* set maxchild for node; nodenum should already be set */
              update node set maxchild  = @last_nodenum 
                where node_id = @next_node;

              set @last_node_visited = @next_node;
 
         end /* up */

end /* while */

This is pretty brutal, untested coding, but I think the idea is visible somewhere in there. I could probably get it a lot cleaner with a bit of rework, but I'm sleepy.

Feedback *is* appreciated.

Thanks,

Kendall Received on Thu Feb 28 2002 - 02:40:44 CST