左右值树形结构移动节点方法(modified preorder tree traversal move node)

2021-06-17

字数统计: 1.7k字 | 阅读时长≈ 8分

说明

在之前的文章：使用左右值树形数据结构实现树形菜单中记录了如何使用左右值增删改查节点，本次将记录一下如何移动节点，语言使用JAVA + MYSQL实现。

总体思路

移动节点的大致思路是记录移动节点和目标节点之间的左右值以及其子节点的左右值，移动节点及其子节点左右值和目标节点及其子节点的左右值相互加减。

举例

节点A的左右值是LEFT=1,RIGHT=2，节点B的左右值是LEFT=5,RIGHT=6，现在要将节点A移动到节点B前面，那么它的移动范围就是RIGHT - LEFT + 1，即：2 - 1 +1 = 2，也就是说节点A左右值+2，左右值小于节点B的左右值-2 。

结果：节点A的LEFT = 3 ,RIGHT = 4，节点B前面的节点左右值减了2变成了LEFT=1,RIGHT=2，相当于和节点A换了个位置，如此来达到移动节点的目的

后续的移动到节点B后面、移动到节点B作为其子节点思路相同。

更新

2021-6-22 更新

修复了BUG，最新代码请关注： https://github.com/reinershir/lui-auth 以下代码摘抄自菜单管理功能

代码示例

移动节点到目标节点的前面

将要移动的节点移动动目标节点的前面作为其兄弟节点，为防止在移动节点过程中左右值被修改，需要锁定表，代码示例如下：


/**
 * @Title: moveNodeBefore
 * @Description:  移动菜单到目标菜单前面 
 * @author xh
 * @date 2021年5月29日
 * @param moveId 被移动菜单ID
 * @param targetId 目标菜单ID
 * @return
 */
@Transactional
public Integer moveNodeBefore(Long moveId,Long targetId,boolean isUnlockTable ) {
	this.lockTable();
	   
	Menu moveMenu = this.selectById(moveId);
	
	Menu targetMenu = this.selectById(targetId);
	
	Integer nodeLeft = moveMenu.getLeftValue();
	Integer nodeRight = moveMenu.getRightValue();
	
	//要移动菜单的范围，即被移动菜单及其子节点的左右值范围
	Integer nodeDist = nodeRight - nodeLeft+1; //确定要移动的范围
	Integer level = moveMenu.getLevel();
	
	Integer targetLeft = targetMenu.getLeftValue();
	Integer targetLevel = targetMenu.getLevel();
	Integer moveNodeLeft = nodeLeft < targetLeft?nodeLeft:nodeLeft + nodeDist;
	if((targetLeft>=nodeLeft && targetLeft<= nodeRight)||(moveId==targetId)) {
		unlockTables();
		//is child node
		return -1;
	}
	
	Integer result = 0;
	
	StringBuilder sql = new StringBuilder("UPDATE ");
	sql.append(tableName);
	sql.append(" SET LEFT_VALUE = CASE WHEN LEFT_VALUE >= :targetLeft THEN LEFT_VALUE + :nodeDist ELSE LEFT_VALUE END ,");
	sql.append("RIGHT_VALUE = CASE WHEN RIGHT_VALUE >= :targetLeft THEN RIGHT_VALUE + :nodeDist ELSE RIGHT_VALUE END ");
	sql.append("WHERE RIGHT_VALUE >= :targetLeft");
	
	MapSqlParameterSource  params = new MapSqlParameterSource();
	params.addValue("nodeLeft", nodeLeft);
	params.addValue("nodeRight", nodeRight);
	params.addValue("targetLeft", targetLeft);
	params.addValue("nodeDist", nodeDist);
	
	NamedParameterJdbcTemplate namedParameterJdbcTemplate = new NamedParameterJdbcTemplate(jdbcTemplate);
	
	result+=namedParameterJdbcTemplate.update(sql.toString(),params);
	
	sql = new StringBuilder("UPDATE ");
	sql.append(tableName);
	sql.append(" SET LEFT_VALUE = LEFT_VALUE + :targetLeft - :moveNodeLeft ,");
	sql.append("RIGHT_VALUE = RIGHT_VALUE + :targetLeft - :moveNodeLeft ,");
	sql.append("LEVEL = LEVEL - :level + :targetLevel WHERE LEFT_VALUE >= :moveNodeLeft AND RIGHT_VALUE <= :moveNodeLeft + :nodeDist -1 ");
	
	params.addValue("moveNodeLeft", moveNodeLeft);
	params.addValue("level", level);
	params.addValue("targetLevel", targetLevel);
	result +=namedParameterJdbcTemplate.update(sql.toString(),params);
	
	sql = new StringBuilder("UPDATE ");
	sql.append(tableName);
	sql.append(" SET LEFT_VALUE = CASE WHEN LEFT_VALUE >= :moveNodeLeft THEN LEFT_VALUE - :nodeDist ELSE LEFT_VALUE END,");
	sql.append("RIGHT_VALUE = CASE WHEN RIGHT_VALUE > :moveNodeLeft THEN RIGHT_VALUE - :nodeDist ELSE RIGHT_VALUE END ");
	sql.append("WHERE RIGHT_VALUE > :moveNodeLeft ");
	
	result+= namedParameterJdbcTemplate.update(sql.toString(),params);
	if(isUnlockTable) {
		unlockTables();
	}
	return result;
}

public Integer moveNodeBefore(Long moveId,Long targetId) {
	return moveNodeBefore(moveId, targetId,true);
}

示例代码以移动菜单为例，LEFT_VALUE,RIGHT_VALUE分别对应左值和右值

lockTables()，mysql锁表代码：

1	jdbcTemplate.update("LOCK TABLES "+tableName+" WRITE")

unlockTable() 手动解除锁表：

1	jdbcTemplate.update("UNLOCK TABLES ");

之所以要锁表是因为在修改左右值过程中不能有其它事务修改数据，否则会造成左右值错乱，整张表的数据都坏掉，所以这种数据结构有好有坏，要根据场景来使用。

移动节点到目标节点后面

此代码还可以进一步优化，目前有点冗余

@Transactional
	public Integer moveNodeAfter(Long moveId,Long targetId ) {
		int result = this.moveNodeBefore(moveId, targetId,false);
		if(result>0) {
			result += moveNodeBackward(moveId, targetId);
			unlockTables();
		}
		return result;
	}
	
	private int moveNodeBackward(Long moveId,Long targetId) {
		Menu moveMenu = this.selectById(moveId);
		
		Menu targetMenu = this.selectById(targetId);
		
		Integer nodeLeft = moveMenu.getLeftValue();
		Integer nodeRight = moveMenu.getRightValue();
		
		Integer targetLeft = targetMenu.getLeftValue();
		Integer targetRight = targetMenu.getRightValue();
		
		Integer nodeDist = nodeRight - nodeLeft+1; //确定要移动的范围
		
		Integer targetDist = targetRight - targetLeft+1;
		
		List<Long> ids = jdbcTemplate.queryForList("SELECT ID FROM "+tableName+" WHERE LEFT_VALUE >= ? AND RIGHT_VALUE<=?",Long.class,targetLeft,targetRight);
		
		
		StringBuilder sql = new StringBuilder("UPDATE ");
		sql.append(tableName);
		sql.append(" SET LEFT_VALUE = CASE WHEN LEFT_VALUE >= :nodeLeft THEN LEFT_VALUE + :targetDist ELSE LEFT_VALUE END ,");
		sql.append("RIGHT_VALUE = CASE WHEN RIGHT_VALUE <= :nodeRight THEN RIGHT_VALUE + :targetDist ELSE RIGHT_VALUE END ");
		sql.append("WHERE LEFT_VALUE >= :nodeLeft AND RIGHT_VALUE <= :nodeRight");
		
		MapSqlParameterSource  params = new MapSqlParameterSource();
		params.addValue("nodeLeft", nodeLeft);
		params.addValue("nodeRight", nodeRight);
		params.addValue("targetLeft", targetLeft);
		params.addValue("targetRight", targetRight);
		params.addValue("nodeDist", nodeDist);
		params.addValue("targetDist", targetDist);
		params.addValue("ids", ids);
		
		NamedParameterJdbcTemplate namedParameterJdbcTemplate = new NamedParameterJdbcTemplate(jdbcTemplate);
		
		int result=namedParameterJdbcTemplate.update(sql.toString(),params);
		
		sql = new StringBuilder("UPDATE ");
		sql.append(tableName);
		sql.append(" SET LEFT_VALUE = LEFT_VALUE - :nodeDist,RIGHT_VALUE = RIGHT_VALUE - :nodeDist ");
		sql.append("WHERE LEFT_VALUE >= :targetLeft AND RIGHT_VALUE <= :targetRight AND ID IN (:ids) ");
		
		result+=namedParameterJdbcTemplate.update(sql.toString(),params);
		
		return result;
	}

移动节点到目标节点的子节点最后一位

移到节点到目标节点的下面，作为其子节点，并排在其子节点的最后一位，被移动节点的子节点也会跟着一并移动，代码示例：

/**
	 * @Title: moveNodeByParentAsLastChild
	 * @Description: 移动菜单到目标菜单下作为目标菜单的最后一个子菜单
	 * @author reinershir
	 * @date 2021年5月26日
	 * @param moveId 要移动的菜单ID
	 * @param targetId 目标父菜单ID
	 * @return
	 */
	@Transactional
	public int moveNodeByParentAsLastChild(Long moveId,Long targetId) {
		//LOCK TABLE
		this.lockTable();
		   
		Menu moveMenu = this.selectById(moveId);
		
		Menu targetMenu = this.selectById(targetId);
		
		Integer moveLeft = moveMenu.getLeftValue(); 
		
		Integer moveRight = moveMenu.getRightValue();
		////要移动菜单的范围，即被移动菜单及其子节点的左右值范围
		Integer moveDistance = moveRight - moveLeft+1; 
		
		Integer level = moveMenu.getLevel();
		
		Integer targetRight = targetMenu.getRightValue();
		
		Integer targetLevel = targetMenu.getLevel();
		
		
		if((targetMenu.getLeftValue()>=moveLeft&&targetRight<=moveRight)||(moveId==targetId)) {
			unlockTables();
			return -1;
		}
		Integer result = 0;
		//设置子节点的新值 
		StringBuilder sql = new StringBuilder("UPDATE ");
		sql.append(tableName);
		sql.append(" SET LEFT_VALUE = CASE WHEN LEFT_VALUE > :targetRight THEN LEFT_VALUE + :moveDistance ELSE LEFT_VALUE END ,");
		sql.append("RIGHT_VALUE = CASE WHEN RIGHT_VALUE >= :targetRight THEN RIGHT_VALUE + :moveDistance ELSE RIGHT_VALUE END ");
		sql.append("WHERE RIGHT_VALUE >= :targetRight");
		
		MapSqlParameterSource  params = new MapSqlParameterSource();
		params.addValue("moveLeft", moveLeft);
		params.addValue("moveRight", moveRight);
		params.addValue("targetRight", targetRight);
		params.addValue("moveDistance", moveDistance);
		
		NamedParameterJdbcTemplate namedParameterJdbcTemplate = new NamedParameterJdbcTemplate(jdbcTemplate);
		
		result+=namedParameterJdbcTemplate.update(sql.toString(),params);
		
		//再次查询 
		moveMenu = this.selectById(moveId);
		moveLeft = moveMenu.getLeftValue(); 
		moveRight = moveMenu.getRightValue();
		
		Integer newDistance = targetRight>=moveLeft?targetRight-moveLeft:moveLeft - targetRight;
		Integer newDistanceOperator = targetRight >=moveLeft?1:0;
		params.addValue("newDistanceOperator", newDistanceOperator);
		params.addValue("newDistance", newDistance);
		params.addValue("level", level);
		params.addValue("targetLevel", targetLevel);
		//重新塞入
		params.addValue("moveLeft", moveLeft);
		params.addValue("moveRight", moveRight);
		//移动节点
		sql = new StringBuilder("UPDATE ");
		sql.append(tableName);
		sql.append(" SET LEFT_VALUE = CASE WHEN :newDistanceOperator = 1 THEN LEFT_VALUE + :newDistance ELSE LEFT_VALUE - :newDistance END ,");
		sql.append("RIGHT_VALUE = CASE WHEN :newDistanceOperator = 1 THEN RIGHT_VALUE + :newDistance ELSE RIGHT_VALUE - :newDistance END ,");
		sql.append("LEVEL = LEVEL - :level +1 + :targetLevel WHERE RIGHT_VALUE <= :moveRight AND LEFT_VALUE >= :moveLeft");
	
		result += namedParameterJdbcTemplate.update(sql.toString(),params);
		sql = new StringBuilder("UPDATE ");
		sql.append(tableName);
		sql.append(" SET LEFT_VALUE = CASE WHEN LEFT_VALUE > :moveRight THEN LEFT_VALUE - :moveDistance ELSE LEFT_VALUE END,");
		sql.append("RIGHT_VALUE = CASE WHEN RIGHT_VALUE >= :moveRight THEN RIGHT_VALUE - :moveDistance ELSE RIGHT_VALUE END ");
		sql.append("WHERE RIGHT_VALUE >= :moveRight ");
		
		result+= namedParameterJdbcTemplate.update(sql.toString(),params);
		unlockTables();
		return result;
	}

附加说明

表字段对应上一章LEFT_VALUE对应L，RIGHT_VALUE对应R，其余字段名字相同

本文作者： reiner
本文链接： https://reiner.host/posts/cfc5b0c5.html
版权声明： 转载请注明出处，并附上原文链接