利用左值右值实现树状结构

image.png

1. 查询

1.1. 得到节点 Node 下的所有节点，并按树状排序

SELECT * FROM tree WHERE lft BETWEEN Node.Lft AND Node.Rgt ORDER BY lft ASC;

1.2. 得到节点 Node 的路径:

SELECT * FROM tree WHERE lft < Node.Lft AND rgt > Node.Rgt ORDER BY lft ASC;

1.3. 节点 Node 的子节点总数

(Node.Rgt-Node.Lft-1)/2

2. 修改

2.1. 增加一个节点

假设新节点的父节点是 Father，如果，这是它的第一个子节点，

nCurrent = Father.Lft;

否则，假设插入点的前一个兄弟为 Brother，

nCurrent = Brother.Rgt;

改变所有位于新节点右侧的数值:

UPDATE tree SET rgt = rgt+2 WHERE rgt > nCurrent;
UPDATE tree SET lft = lft+2 WHERE lft > nCurrent;

这样就为新插入的节点腾出了空间:

INSERT INTO tree(lft, rgt) VALUES(nCurrent+1, nCurrent+2);

2.2. 删除一个节点 Node

DELETE Node;
UPDATE tree SET rgt = rgt - 2 WHERE rgt > Node.rgt;
UPDATE tree SET lft = lft - 2 WHERE lft > Node.rgt;

2.3. 子树 SubTree 从 Father1 迁移至 Father2

相当于先插入子树，再删掉原来的子树。
子树根的左右值:

nSubTreeLeft = SubTree.Lft;
nSubTreeRight = SubTree.Rgt;

子树上所有的节点数(包括子树的根):

nSubTreeNodeNum = (nSubTreeRight - nSubTreeLeft - 1) / 2 + 1;

如果，这是 Father2 的第一个子节点，

nCurrent = Father2.Lft; 

否则，假设插入点的前一个兄弟为 Brother，

nCurrent = Brother.Rgt;

腾子树空间:

UPDATE tree SET lft=lft + 2* nSubTreeNodeNum WHERE lft > nCurrent; UPDATE tree SET rgt=rgt + 2* nSubTreeNodeNum WHERE rgt > nCurrent;

移动子树:

UPDATE tree SET lft = lft + nCurrent + 1 - nSubTreeLeft, rgt = rgt + nCurrent + 1 - nSubTreeLeft WHERE lft BETWEEN nSubTreeLeft AND nSubTreeRight;

删掉原来子树占的空间:

UPDATE tree SET lft=lft -2* nSubTreeNodeNum WHERE lft > nSubTreeRight; 
UPDATE tree SET rgt=rgt -2* nSubTreeNodeNum WHERE rgt > nSubTreeRight;

重构左右值

假设表结构类似:

image.png

/**
     * 重构左右值
     *
     * @param rootId 根节点id
     * @param left   左值开始值
     * @return
     */
    public int rebuildTree(int rootId, int left) {
        int right = left + 1;
        List<Category> categories = categoryMapper.selectByParentCategoryID(rootId);
        for (Category category : categories) {
            right = rebuildTree(category.getId(), right);
        }
        Category category = categoryMapper.selectByPrimaryKey(rootId);
        category.setLft(left);
        category.setRgt(right);
        categoryMapper.updateByPrimaryKey(category);
        return right + 1;
    }