Move node in Nested Sets tree

Question

I am working on an adjacency list with mySQL and can not (atleast by myself) do the thinking needed to make a decent enough query to be able to move a set of nodes (together with eventual children nodes) around.

The table has following columns:

 id     name     left     right

Thanks a lot!

Answer 1

Here is a solution that 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 sets:

• Create new space for the subtree.
• Move the subtree into this space.
• 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
 */

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;
}

For a complete code example, see my blog at

https://rogerkeays.com/how-to-move-a-node-in-nested-sets-with-sql

If you like this solution, please up-vote.