1. 首页
  2. 综合应用
  3. 技术总结
  4. 正文

树形结构左右值分析与实现

2014/07/31 2975点热度 0人点赞 1条评论

左右值分析

表结构

B_Tree

id   

name  名称

leftValue  左值

rightValue  右值

treelevel  级别

左右值规则：

  某一节点的leftValue，rightValue

     leftValue为该节点包含子节点的开始

     rightValue为该节点包含子节点的左值的结束

     也就是 leftValue=<leftValue<=rightValue

     为这个节点包含子节点的所有范围

  

左右数据插入实现：

  pId==0

  如果是第一层：

     select max(rightValue) maxRight from B_Tree where treelevel=0;

     查询第一层最大的右值  maxRight

     新的数据的左右值为

       leftValue=maxRight+1;

       rightValue=maxRight+1;

  如果非第一层：pId！=0

     select leftValue p_leftValue, rightValue p_rightValue,treelevel p_treelevel from B_Tree where id=:pId;

     查询要添加节点（C）的父级一层的 p_leftValue,p_rightValue

       select  max(rightValue) maxRight from B_Tree  where treelevel=p_treelevel+1 and leftValue>p_leftValue and rightValue<p_rightValue

       获取要添加节点父节点（P）下一级节点最大的右值 maxRight 最大右值：maxLeft

       如果maxRight==0表示P下还没有子节点

          C 的左右值和treelevel为：

          maxRight=p_leftValue+1

          leftValue=maxRight;

          rightValue=maxRight;

 treelevel=p_treelevel+1;

       如果maxRight>0表示P下已经有子节点

          C 的左右值和treelevel为：

          maxRight++;

          leftValue=maxRight;

          rightValue=maxRight;

 treelevel=p_treelevel+1;

maxRight 已经是P节点包含的最大值

 update B_Tree set rigthValue=rigthValue+1 where rigthValue>=(maxRight-1)

 将原先右值>=maxRight的所有列的右值+1，

 update B_Tree set leftValue=leftValue+1 where leftValue>=maxRight

 将原先左值>=maxRight的所有列的左值+1

例如：

     左值 名称 右值  层级

    首次插入：

      1   首     1  0    

        表中没有数据，查到为0   添加数据的 左右值都为1

    第二次插入          

      2   第二   2  0                     

        表中有数据，查到maxRight为1 添加数据 的左右都为maxRight+1=2

    第三次插入

      3   第三   3  0                     

   

    插入子节点：             插入子节点后父节点层次的变更

      2 首一      2   1                 1   首次   2  0    3  第二   3    0    4   第三   4  0 

        在第三层级中插入子节点

 查到  maxRight=0  当前节点的左右值直接使用父节点的左值p_leftValue+1=2

           maxRight=2 

          update B_Tree set rigthValue=rigthValue+1 where rigthValue>=(maxRight-1)

 update B_Tree set leftValue=leftValue+1 where leftValue>=maxRight

   

      3 首二      3   1                 1   首次   3  0    4  第二   4    0    5   第三   5  0 

          查到  maxRight=2 当前节点的左右值直接使用父节点的左值=2+1

           maxRight=2 

          update B_Tree set rigthValue=rigthValue+1 where rigthValue>=(maxRight-1)

 update B_Tree set leftValue=leftValue+1 where leftValue>=maxRight

      4 首二（A） 4   2                 1   首次   4  0    5  第二   5    0    6   第三   6  0

          查到  maxRight=0 当前节点的左右值直接使用父节点的左值=p_leftValue+1=4

           maxRight=5 

          update B_Tree set rigthValue=rigthValue+1 where rigthValue>=(maxRight-1)

 update B_Tree set leftValue=leftValue+1 where leftValue>=maxRight

 获取该节点和子节点：  id

 select leftValue pleft,rightValue pright from B_Tree where id=:id;
 select * from  B_Tree  where leftValue>=pleft and rightValue<=pright;

合体后的查询

 select a.* from  B_Tree  a join (select leftValue pleft,rightValue pright from B_Tree where id=:id) b
 on 1=1  where leftValue>=b.pleft and rightValue<=b.pright;
 select a.* from  B_Tree  a 
 where exists (select 1 from B_Tree b where b.id=:id and a.leftValue>=b.leftValue and a.rightValue<=b.rightValue)

代码实现

注：该实现是基于hibernate建表的实体+spring+mybatis的实现

@Override
	public synchronized void saveTreeNode(T item) throws Exception{
		if(item!=null&&item.getpId()!=null){
			String tableName=ReflectGenricUtil.getTableName(item.getClass());
			Integer maxRight=0;
			//第一层
			if("0".equals(item.getpId())){
				StringBuffer maxRightSql=new StringBuffer();
				maxRightSql.append("select max(rightValue) MAXRIGHT from ").append(tableName).append(" where treeLevel=? ");
				Map<String, Object> mapMax = this.getBaseDao().findMapBySql(maxRightSql.toString(), 0);
				if(mapMax!=null&&mapMax.size()>0){
					maxRight=(Integer) mapMax.get("MAXRIGHT");
					if(maxRight==null){
						maxRight=0;
					}
				}
				maxRight++;
				item.setLeftValue(maxRight);
				item.setRightValue(maxRight);
			}else{
				StringBuffer parentSql=new StringBuffer();
				parentSql.append("select leftValue P_LEFTVALUE, rightValue P_RIGHTVALUE,treelevel P_TREELEVEL from ").append(tableName)
				         .append(" f ").append(" where id=?");
				Map<String, Object> parentMap = this.getBaseDao().findMapBySql(parentSql.toString(), item.getpId());
				
				if(parentMap!=null&&parentMap.size()>0){
					Integer p_rightValue=(Integer) parentMap.get("P_RIGHTVALUE");
					Integer P_leftValue=(Integer) parentMap.get("P_LEFTVALUE");
					Integer p_treelevel=(Integer)parentMap.get("P_TREELEVEL");
					StringBuffer rightMaxSql=new StringBuffer();
					rightMaxSql.append(" select  max(rightValue) MAXRIGHT from ").append(tableName)
					           .append("  where treelevel=").append(p_treelevel+1)
					           .append("  and leftValue>").append(P_leftValue)
					           .append("  and rightValue<? ");
					Map<String, Object> mapMax = this.getBaseDao().findMapBySql(rightMaxSql.toString(), p_rightValue);
					if(mapMax!=null&&mapMax.size()>0){
						maxRight=(Integer) mapMax.get("MAXRIGHT");
					}
					if(maxRight==null){
						 maxRight=P_leftValue+1;
					}else{
						maxRight++;
					}
					item.setLeftValue(maxRight);
					item.setRightValue(maxRight);
					item.setTreeLevel(p_treelevel+1);
				}
			}
			
			StringBuffer rightUpdateSql=new StringBuffer();
			rightUpdateSql.append("update ").append(tableName)
			              .append(" set rightValue=rightValue+1 ")
			              .append(" where rightValue>=?");
			StringBuffer leftUpdateSql=new StringBuffer();
			leftUpdateSql.append("update ").append(tableName)
			             .append(" set leftValue=leftValue+1 ")
			             .append(" where leftValue>=?");
			this.getBaseDao().updateBySql(rightUpdateSql.toString(), maxRight-1);
			this.getBaseDao().updateBySql(leftUpdateSql.toString(), maxRight);
			
			this.getBaseDao().save(item);
			
		}
	}

相关代码

/**
	 * 功能说明：根据注解获取类注解上的表名
	 * @author ducc
	 * @updated 
	 * @param clazz
	 * @return
	 */
	public static String getTableName(final Class clazz){
		Table table = (Table) clazz.getAnnotation(Table.class);
		return table.name();
	}
	public Map<String,Object> findMapBySql(String sql,Object... obj )throws SQLException{
		SqlRunner sr=new SqlRunner(getSqlSession().getConnection());
		List<Map<String,Object>> selectAll=sr.selectAll(sql, obj);
		if(selectAll!=null&&selectAll.size()>0){
			return selectAll.get(0);
		}
		return null;
	}
	public Integer updateBySql(String sql,Object... obj)throws SQLException{
		SqlRunner sr=new SqlRunner(getSqlSession().getConnection());
		return sr.update(sql, obj);
	}
	public Integer save(T item) {
		generateId(item);
		return this.getSqlSession().insert(getSqlName(SQL_SAVE),item);
	}

测试结果

相关文章：

  1. (转)SQL中EXISTS的用法
  2. java版SmartWeatherAPI 获取天气信息 工具类
  3. hibernate异常解决
  4. Tomcat中配置mysql/oracle jndi数据库连接
  5. jquery ui 模态alert confirm
  6. 记一次生产慢sql查询的解决
  7. 从一次图文消息推导微信发文流程
  8. 我遇到的生产事故
  9. 链路追踪之sleuth全生命周期分析
  10. DDD应用架构内部分享-没错我又来了
标签：
最后更新：2014/08/02

yxkong

这个人很懒，什么都没留下

文章评论

  • luo

    预排序遍历树算法牺牲写性能的改进http://wenku.baidu.com/view/634656b0561252d381eb6e8f

    2016/06/19
    回复
    • 取消回复

    COPYRIGHT © 2022 我要编程. ALL RIGHTS RESERVED.

    Theme Kratos Made By Seaton Jiang

    京ICP备15055556号