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!

Protectorate

Answer 1

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/

Krilov

Answer 2

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.

Combative

Your example really helped me to understand the algorithm but every time you put all the method body into a try block God kills a kitten you know :) – Osiris

Answer 3

The steps to move a subtree around in a category tree using the nested set model (with left and right columns) are: 1. transform the lft and rgt columns in their negative counterparts for the category you wish to move and its subcategories (this will "remove" the subtree from the tree, for the time being) 2. if you are moving the subtree up (or "left" in the nested set representation), move all the categories between the new parent of the subtree and its old left(or right, in the second case) limit to the right, otherwise (when moving the subtree down) to the right. This involves setting the left and right columns of these categories to their values plus (or minus, in the second case) the distance between the left and right column of the subtree (or the category to be moved) 3. after this, all you have to do is to revert the left and right columns to the positive values and in the same time substract (or add, in the second case) the difference between its left limit and the new parent left column (or between the parent left and the right limit in the second case)

This all seems very complicated, expressed in one case, so I broke it down to the two cases:

$step = 1+ $this->_categoriesTable->rgt
                - $this->_categoriesTable->lft;
$lft = $this->_categoriesTable->lft;
$rgt = $this->_categoriesTable->rgt;
$id = $this->_categoriesTable->id;
$distance = $lft - $parentLeft - 1;
                $query = '
                    UPDATE %s SET lft=-lft, rgt=-rgt
                        WHERE lft>=%d AND lft<=%d;
                    UPDATE %s SET lft=lft+%d WHERE lft>%d AND lft<%d;
                    UPDATE %s SET rgt=rgt+%d WHERE rgt>%d AND rgt<%d;
                    UPDATE %s SET lft=-lft-%d, rgt=-rgt-%d WHERE lft<=-%d
                        AND lft>=-%d;
                    UPDATE %s SET parent_id=%d, title=%s, description=%s,
                        metadescription=%s WHERE id=%s';

                $query = sprintf($query,
                    $this->_db->nameQuote('#__categories'),
                        $lft, $rgt,
                    $this->_db->nameQuote('#__categories'), $step,
                        $parentLeft, $lft,
                    $this->_db->nameQuote('#__categories'), $step,
                        $parentLeft, $lft,
                    $this->_db->nameQuote('#__categories'), $distance,
                        $distance, $lft, $rgt,
                    $this->_db->nameQuote('#__categories'),
                        $data['parent_id'], 
                        $this->_db->Quote($this->_categoriesTable->title),
                        $this->_db->Quote($this->_categoriesTable->description),
                        $this->_db->Quote(
                            $this->_categoriesTable->metadescription),
                        $this->_db->Quote($id));

// and for the moving to the "right" case
$step = 1+ $this->_categoriesTable->rgt
                - $this->_categoriesTable->lft;
$distance = $parentLeft - $this->_categoriesTable->rgt;

// Memorize this because we bind and we need the old values
$lft = $this->_categoriesTable->lft;
$rgt = $this->_categoriesTable->rgt;
$id = $this->_categoriesTable->id;

$query = sprintf($query,
                    $this->_db->nameQuote('#__categories'),
                        $lft, $rgt,
                    $this->_db->nameQuote('#__categories'), $step,
                        $rgt, $parentLeft,
                    $this->_db->nameQuote('#__categories'), $step,
                        $rgt, $parentLeft,
                    $this->_db->nameQuote('#__categories'), $distance,
                        $distance, $lft, $rgt,
                    $this->_db->nameQuote('#__categories'),
                        $data['parent_id'],
                        $this->_db->Quote($this->_categoriesTable->title),
                        $this->_db->Quote($this->_categoriesTable->description),
                        $this->_db->Quote(
                            $this->_categoriesTable->metadescription),
                        $this->_db->Quote($id));

Pa

Answer 4

Ive got a simpler and easier to read sql, it works perfectly for me. It made for a typical nested set structure with id, rgt, lft, level (works without level too):

#Set IDs
SET @dirId := :dirId; #folder (subtree) you wanna move
SET @targetId := :folderId; #target

#get datas
SELECT rgt, lft, rgt-lft+1, level INTO @dir_rgt, @dir_lft, @dir_size, @dir_level FROM files WHERE id = @dirId;

#put the moving tree aside (lft and rgt columns must allow negative int)
UPDATE files SET lft = 0-lft, rgt = 0-rgt WHERE lft BETWEEN @dir_lft AND @dir_rgt;

#fill the empty space        
UPDATE files SET rgt = rgt-@dir_size WHERE rgt > @dir_rgt;
UPDATE files SET lft = lft-@dir_size WHERE lft > @dir_rgt;

#get datas of the target-folder      
SELECT lft, level INTO @target_lft, @target_level FROM files WHERE id = @targetId;

#create space in the target-folder        
UPDATE files SET rgt = rgt+@dir_size WHERE rgt >= @target_lft;
UPDATE files SET lft = lft+@dir_size WHERE lft > @target_lft;

#edit all nodes in the moving-tree
UPDATE files SET
   lft     = 0 - lft - (@dir_lft - @target_lft - 1), #this formula fits for all moving directions
   rgt     = 0 - rgt - (@dir_lft - @target_lft - 1), 
   level   = level - (@dir_level - @target_level) + 1

WHERE 
   lft < 0; #that could be more precise...

Drake

Thank you very much. After 6 hours of searching and testing so many solutions, finally the one that suited my needs. – Sec

Answer 5

When you think about it mathematically, you could do it all with a single UPDATE statement. For any move operation, when you know the LEFT and RIGHT of your node and the insertion position you want it to end up at, you can recompute all of the LEFTs and RIGHTs in your tree in one go. You only need to make sure, the new position is not within the moving node itself, which can be done with a simple WHERE clause:

-- moves a subtree before the specified position
-- if the position is the rgt of a node, the subtree will be its last child
-- if the position is the lft of a node, the subtree will be inserted before
-- @param l the lft of the subtree to move
-- @param r the rgt of the subtree to move
-- @param p the position to move the subtree before
update tree
set
    lft = lft + if (:p > :r,
        if (:r < lft and lft < :p,
            :l - :r - 1,
            if (:l <= lft and lft < :r,
                :p - :r - 1,
                0
            )
        ),
        if (:p <= lft and lft < :l,
            :r - :l + 1,
            if (:l <= lft and lft < :r,
                :p - :l,
                0
            )
        )
    ),
    rgt = rgt + if (:p > :r,
        if (:r < rgt and rgt < :p,
            :l - :r - 1,
            if (:l < rgt and rgt <= :r,
                :p - :r - 1,
                0
            )
        ),
        if (:p <= rgt and rgt < :l,
            :r - :l + 1,
            if (:l < rgt and rgt <= :r,
                :p - :l,
                0
            )
        )
    )
where :r < :p or :p < :l;

See https://sedna-soft.de/articles/nested-sets-move-subtree/

Bil

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Armada