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.

Answer 2

I'm pretty sure that table is using the Nested Sets design, not Adjacency List. If it were using Adjacency List, it would have a column like parent_id instead of left and right.

Moving nodes is royal PITA in Nested Sets. You have to renumber all the left and right values for each node you move.

If you move a subtree, the easiest way to do this is to remove the nodes one at a time, renumbering the left and right fields after each node removal. Then once you have removed the whole subtree (and preserved the structure of the subtree in your application somehow), re-insert the subtree at its destination location in the tree, again re-numbering the left and right fields per insert.

---

update: I recently wrote a blog about how to move subtrees in a different hierarchical data design which I like better than nested sets. I call this design Closure Table.
See http://www.mysqlperformanceblog.com/2011/02/14/moving-subtrees-in-closure-table/