How To Move A Node In Nested Sets With SQL

By , 8 January 2012

How To Move A Node In Nested Sets With SQL
How To Move A Node In Nested Sets With SQL

Moving nodes in nested sets is a complex operation. There were a few solutions on Stack Overflow for moving a node under a given parent, however this doesn't let you select the position of the node amongst it's siblings.

This solution lets you move a node to any position in the tree, with just a single input parameter - the new left position (newpos) of the node.

Fundamentally there are three steps:

  1. Create new space for the subtree.
  2. Move the subtree into this space.
  3. Remove the old space vacated by the subtree.

In psuedo-sql, it looks like this:

    /**
     *  -- create new space for subtree
     *  UPDATE tags SET lpos = lpos + :width WHERE lpos >= :newpos
     *  UPDATE tags SET rpos = rpos + :width WHERE rpos >= :newpos
     * 
     *  -- move subtree into new space
     *  UPDATE tags SET lpos = lpos + :distance, rpos = rpos + :distance
     *           WHERE lpos >= :tmppos AND rpos < :tmppos + :width
     * 
     *  -- remove old space vacated by subtree
     *  UPDATE tags SET lpos = lpos - :width WHERE lpos > :oldrpos
     *  UPDATE tags SET rpos = rpos - :width WHERE rpos > :oldrpos
     */
How To Move A Node In Nested Sets With SQL

The :distance variable is the distance between the new and old positions, the :width is the size of the subtree, and :tmppos is used to keep track of the subtree being moved during the updates. These variables are defined as:

    // calculate position adjustment variables
    int width = node.getRpos() - node.getLpos() + 1;
    int distance = newpos - node.getLpos();
    int tmppos = node.getLpos();
            
    // backwards movement must account for new space
    if (distance < 0) {
        distance -= width;
        tmppos += width;
    }

Here is some sample code of how this is done with OrmLite.

    public void move(Node node, int newpos) {
        try {
            refresh(node);
            
            // calculate position adjustment variables
            int width = node.getRpos() - node.getLpos() + 1;
            int distance = newpos - node.getLpos();
            int tmppos = node.getLpos();
            
            // backwards movement must account for new space
            if (distance < 0) {
                distance -= width;
                tmppos += width;
            }
            
            // create new space for subtree
            UpdateBuilder update1 = updateBuilder();
            update1.updateColumnExpression("lpos", "lpos + " + width);
            update1.where().ge("lpos", newpos);
            update(update1.prepare());
            
            UpdateBuilder update2 = updateBuilder();
            update2.updateColumnExpression("rpos", "rpos + " + width);
            update2.where().ge("rpos", newpos);
            update(update2.prepare());
            
            // move subtree into new space
            UpdateBuilder update3 = updateBuilder();
            update3.updateColumnExpression("lpos", "lpos + " + distance);
            update3.updateColumnExpression("rpos", "rpos + " + distance);
            update3.where().ge("lpos", tmppos)
                   .and().lt("rpos", tmppos + width);
            update(update3.prepare());
            
            // remove old space vacated by subtree
            UpdateBuilder update4 = updateBuilder();
            update4.updateColumnExpression("lpos", "lpos - " + width);
            update4.where().gt("lpos", node.getRpos());
            update(update4.prepare());
            
            UpdateBuilder update5 = updateBuilder();
            update5.updateColumnExpression("rpos", "rpos - " + width);
            update5.where().gt("rpos", node.getRpos());
            update(update5.prepare());
            
            // refresh local data
            refresh(node);
            getObjectCache().clearAll();
        } catch (SQLException e) {
            Log.e("Error moving node", e.getMessage());
        }
    }

Hope that helps you.

 

About I Like Spam

How To Move A Node In Nested Sets With SQL

Leave a Comment

Please visit https://ilikespam.com/how-to-move-a-node-in-nested-sets-with-sql to add your comments.

Comment posted by: Kim Pepper, 5 months ago

Thanks for this! I've added it to a PHP nested set library I am putting together. https://github.com/previousnext/nested-set

Comment posted by: Jesse Seger, last year

I have a question. 

                         1 Root 8

              2 Child1 5        6 Child2 7

             3 Child1.1 4

I want to move Child1 under Child2. The shift happens, but there becomes a gap in the tree. The problem I'm having is that Child2.Left is still 6. Then Child1.Left is also 6.  Like so.

1 Root 8

6 Child2 7

6 Child1 9

7 Child1.1 8 

It's like Child2 should shift over to Child.Left = 2 to fill the gap.  

Like many others trying this for the first time is SQL, my brain is fried.

Comment posted by: tyan4g, last year

It's useful for me.Although it took me a whole day to figure it out .I even considered the matrix encoding way to store the tree-like structure.But I choose nested set.So。。

it works like a charm. THANKS FOR THE POST.

Comment posted by: Vexal, 2 years ago

THANK YOU SO MUCH ! it works like a charm !

Answer to Ryan :

You need to compute newpos. As newpos is the left position where the subtree is targeted, you can do like this :

if target position is before a node, newpos = left position of this node

if target position is into a node (as a child), newpos = left position of this node + 1

if target position is after a node, newpos = right position of this node + 1

 

In your example, if you want groupA become a sub-group of groupB, new pos = 3 +1 = 4

Comment posted by: Ryan, 2 years ago

I am really interesting in implementing this, however I'm a bit confused:

Given the following structure :

id, name, lft, rgt

------------------

1, root, 1, 6

2, GroupA, 2, 5

3, GroupB, 3, 4

===========================

If I wanted to take GroupA and make it a sub-group of GroupB, basically flipping the two groups, how would I accomplish this using GroupA as the target node? How do you determine what the newLeftPosition is?

 

 

 

Comment posted by: ryan, 2 years ago

THANK YOU so much for this!

;)

Even with this walk through it took me a couple days to wrap my head around this. But this does work perfectly! I had missed the bit about going backwards and that hung me up for a bit as well.

Also, I'm using this with jstree. So figuring out the new position required some javascript finagling but it works. I can't believe it. It works. And it's so sexy!

 

Comment posted by: Alex, 2 years ago

Ok, this Java code works:

 

// Create space for subtree
        String hql = "UPDATE CatStructure SET lft = lft + " + width
                + " where lft > " + newParent.getLft();
        Query query = session.createQuery(hql);
        int _return = query.executeUpdate();

        hql = "UPDATE CatStructure SET rgt = rgt + " + width + " where rgt >= "
                + newParent.getLft();
        query = session.createQuery(hql);
        _return = query.executeUpdate();

        // Move subtree into new space
        hql = "UPDATE CatStructure SET lft = lft + " + distance
                + ", rgt = rgt + " + distance + " where lft >= " + tmpPos
                + " and rgt < " + (tmpPos + width);
        query = session.createQuery(hql);
        _return = query.executeUpdate();

        // remove old space
        hql = "UPDATE CatStructure SET lft = lft - " + width + " where lft > "
                + actualElement.getRgt();
        query = session.createQuery(hql);
        _return = query.executeUpdate();

        hql = "UPDATE CatStructure SET rgt = rgt - " + width + " where rgt > "
                + actualElement.getRgt();
        query = session.createQuery(hql);
        _return = query.executeUpdate();

Comment posted by: eddid, 2 years ago

This does not work. The major issue is that the lpos and rpos values of subtree are changed after the "create space" step. The "move" and "remove" steps still use old values of the node.

Comment posted by: eddid, 2 years ago

This does not work. The major issue is that the lpos and rpos values of subtree are changed after the "create space" step. The "move" and "remove" steps still use old values of the node.

Comment posted by: eddid, 2 years ago

This does not work. The major issue is that the lpos and rpos values of subtree are changed after the "create space" step. The "move" and "remove" steps still use old values of the node.

Comment posted by: ronny, 3 years ago

brilliant, 

works like it should, very good explanation, thank you!

Comment posted by: Your name, 3 years ago

Moving nodes in nested sets is a complex operation. There were a few solutions on Stack Overflow for moving a node under a given parent, however this doesn't let you select the position of the node amongst it's siblings.

This solution lets you move a node to any position in the tree, with just a single input parameter - the new left position (newpos) of the node.

Comment posted by: Chandara, 3 years ago

I follow in psuedo-sql but it still not work. I don't know why. Does it really work?

Comment posted by: Jens, 3 years ago

Saved my life! Superb!

Comment posted by: , 4 years ago

:newpos is the new left position of the node being moved. You have to provide that variable.

Comment posted by: Blaine Hilton, 4 years ago

 In your example what is :newpos?

Comment posted by: , 4 years ago

Don't worry, it took me more than a while to figure out too. Glad it helped you though. Don't forget to post a link/share/like to your blog or favourite social network. That way I'm motivated to write more.

Comment posted by: Adrian Wojas, 4 years ago
I've been trying to crack this algorithm all evening with no results. I've checked your solution and it seems to work. Your a genius:)
thank you!