Di chuyển nút trong tập hợp lồng nhau

Tôi hiểu rồi, đó là chủ đề khá cũ, nhưng dù sao thì nó vẫn chưa được giải đáp. Tôi đến đây từ Google và không tìm thấy câu trả lời trực tiếp nào cho câu hỏi này.

Vì vậy, sau khi nghiên cứu một chút, tôi đã tìm ra giải pháp khá dễ dàng.

Tất cả mọi thứ, những gì chúng ta cần để di chuyển nút của mình là:vị trí nút trái và phải, vị trí nút cha mới sang phải. Sau đó, nút đến vị trí mới có thể được di chuyển trong bốn bước đơn giản:

1. Thay đổi vị trí của nút và tất cả các nút con của nó thành giá trị âm, bằng với giá trị hiện tại theo mô-đun.
2. Di chuyển tất cả các vị trí "lên trên", tức là nhiều hơn, vị trí bên phải của nút hiện tại.
3. Di chuyển tất cả các vị trí "xuống dưới", tức là vị trí khác ở vị trí bên phải của nút mẹ mới.
4. Thay đổi vị trí của nút hiện tại và tất cả các nút con của nó để bây giờ nó sẽ chính xác là "sau" (hoặc "xuống") của nút mẹ mới.

Đó là lý thuyết, bây giờ - thực hiện thuật toán này trong MySQL (ví dụ sử dụng PHP):

-- step 0: Initialize parameters.
SELECT
    @node_id := 1, --put there id of moving node 
    @node_pos_left := 0, --put there left position of moving node
    @node_pos_right := 1, --put there right position of moving node
    @parent_id := 2, --put there id of new parent node (there moving node should be moved)

    @parent_pos_right := 4; --put there right position of new parent node (there moving node should be moved)
SELECT
    @node_size := @node_pos_right - @node_pos_left + 1; -- 'size' of moving node (including all it's sub nodes)

-- step 1: temporary "remove" moving node

UPDATE `list_items`
SET `pos_left` = 0-(`pos_left`), `pos_right` = 0-(`pos_right`)
WHERE `pos_left` >= @node_pos_left AND `pos_right` <= @node_pos_right;

-- step 2: decrease left and/or right position values of currently 'lower' items (and parents)

UPDATE `list_items`
SET `pos_left` = `pos_left` - @node_size
WHERE `pos_left` > @node_pos_right;
UPDATE `list_items`
SET `pos_right` = `pos_right` - @node_size
WHERE `pos_right` > @node_pos_right;

-- step 3: increase left and/or right position values of future 'lower' items (and parents)

UPDATE `list_items`
SET `pos_left` = `pos_left` + @node_size
WHERE `pos_left` >= IF(@parent_pos_right > @node_pos_right, @parent_pos_right - @node_size, @parent_pos_right);
UPDATE `list_items`
SET `pos_right` = `pos_right` + @node_size
WHERE `pos_right` >= IF(@parent_pos_right > @node_pos_right, @parent_pos_right - @node_size, @parent_pos_right);

-- step 4: move node (ant it's subnodes) and update it's parent item id

UPDATE `list_items`
SET
    `pos_left` = 0-(`pos_left`)+IF(@parent_pos_right > @node_pos_right, @parent_pos_right - @node_pos_right - 1, @parent_pos_right - @node_pos_right - 1 + @node_size),
    `pos_right` = 0-(`pos_right`)+IF(@parent_pos_right > @node_pos_right, @parent_pos_right - @node_pos_right - 1, @parent_pos_right - @node_pos_right - 1 + @node_size)
WHERE `pos_left` <= [email protected]_pos_left AND `pos_right` >= [email protected]_pos_right;
UPDATE `list_items`
SET `parent_item_id` = @parent_id
WHERE `item_id` = @node_id;

Hãy cẩn thận - vẫn có thể có một số lỗi cú pháp trong mã SQL, bởi vì tôi thực sự sử dụng thuật toán này trong PHP như thế này:

$iItemId = 1;
$iItemPosLeft = 0;
$iItemPosRight = 1;
$iParentId = 2;
$iParentPosRight = 4;
$iSize = $iPosRight - $iPosLeft + 1;
$sql = array(

    // step 1: temporary "remove" moving node

    'UPDATE `list_items`
    SET `pos_left` = 0-(`pos_left`), `pos_right` = 0-(`pos_right`)
    WHERE `pos_left` >= "'.$iItemPosLeft.'" AND `pos_right` <= "'.$iItemPosRight.'"',

    // step 2: decrease left and/or right position values of currently 'lower' items (and parents)

    'UPDATE `list_items`
    SET `pos_left` = `pos_left` - '.$iSize.'
    WHERE `pos_left` > "'.$iItemPosRight.'"',
    'UPDATE `list_items`
    SET `pos_right` = `pos_right` - '.$iSize.'
    WHERE `pos_right` > "'.$iItemPosRight.'"',

    // step 3: increase left and/or right position values of future 'lower' items (and parents)

    'UPDATE `list_items`
    SET `pos_left` = `pos_left` + '.$iSize.'
    WHERE `pos_left` >= "'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iSize : $iParentPosRight).'"',
    'UPDATE `list_items`
    SET `pos_right` = `pos_right` + '.$iSize.'
    WHERE `pos_right` >= "'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iSize : $iParentPosRight).'"',

    // step 4: move node (ant it's subnodes) and update it's parent item id

    'UPDATE `list_items`
    SET
        `pos_left` = 0-(`pos_left`)+'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iItemPosRight - 1 : $iParentPosRight - $iItemPosRight - 1 + $iSize).',
        `pos_right` = 0-(`pos_right`)+'.($iParentPosRight > $iItemPosRight ? $iParentPosRight - $iItemPosRight - 1 : $iParentPosRight - $iItemPosRight - 1 + $iSize).'
    WHERE `pos_left` <= "'.(0-$iItemPosLeft).'" AND i.`pos_right` >= "'.(0-$iItemPosRight).'"',
    'UPDATE `list_items`
    SET `parent_item_id` = "'.$iParentItemId.'"
    WHERE `item_id`="'.$iItemId.'"'
);

foreach($sql as $sqlQuery){
    mysql_query($sqlQuery);
}

Cũng xin lưu ý rằng mã đó có thể được tối ưu hóa, nhưng tôi sẽ để nó như vậy để dễ đọc hơn. Cũng nên xem xét khóa bảng nếu bạn đang sử dụng các tập hợp lồng nhau trong hệ thống nhiều người dùng.

Mong rằng thông điệp của tôi sẽ giúp ích cho bất kỳ ai, những người sẽ tìm kiếm giải pháp sau tôi. Mọi ý kiến ​​đóng góp và chỉnh sửa cũng đều được hoan nghênh.