在嵌套集树中移动节点

Question

我正在使用mySQL创建一个邻接列表,并且不能(至少我自己)做出必要的思考,以便能够移动一组节点(与最终的子节点一起).

该表包含以下列:

 id     name     left     right

非常感谢!

Answer 1

这是一个解决方案,它允许您将节点移动到树中的任何位置,只需一个输入参数 - 节点的新左侧位置(newpos).

从根本上说有三套:

• 为子树创建新空间.
• 将子树移动到此空间.
• 删除子树腾出的旧空间.

在psuedo-sql中,它看起来像这样:

//
 *  -- 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
 */

:distance变量是新旧位置之间的距离,:width是子树的大小,并且:tmppos用于跟踪在更新期间移动的子树.这些变量定义为:

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

有关完整的代码示例,请参阅我的博客

http://www.ninthavenue.com.au/how-to-move-a-node-in-nested-sets-with-sql

如果你喜欢这个解决方案,请投票.