A-A+

前序遍历树算法(sql)笔记

2014年07月13日 Mysql 暂无评论 阅读 397 views 次
准备 sql  语句

/*declare table construct   定义表结构   lft左值  rgt右值  removed移动标志位*/
DROP TABLE IF EXISTS `nested_category`;CREATE TABLE `nested_category` (
`title` varchar(32) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL,
`parent` varchar(32) CHARACTER SET utf8 COLLATE utf8_bin DEFAULT NULL,
`lft` int(11) DEFAULT NULL,
`rgt` int(11) DEFAULT NULL,
`weight` int(11) DEFAULT NULL,
`cn_name` varchar(32) CHARACTER SET utf8 COLLATE utf8_bin DEFAULT NULL,
`removed` tinyint(4) DEFAULT '0'
) ENGINE=InnoDB DEFAULT CHARSET=utf8; 

/*Data for the table `nested_category`  导入初始数据 */LOCK TABLES `nested_category` WRITE;insert  into `nested_category`(`title`,`parent`,`lft`,`rgt`,`weight`,`cn_name`,`removed`) values ('Banana','Yello',8,9,NULL,'香蕉',0),('Beef','Meat',13,14,NULL,'牛肉',0),('Cherry','Red',4,5,NULL,'樱桃',0),('Food',NULL,1,18,NULL,'食物',0),('Fruit','Food',2,11,NULL,'水果 ',0),('Meat','Food',12,17,NULL,'肉',0),('Pork','Meat',15,16,NULL,'猪肉',0),('Red','Fruit',3,6,NULL,'红',0),('Yello','Fruit',7,10,NULL,'黄色',0);

UNLOCK TABLES;


备份与恢复

#复制表结构
CREATE TABLE `nested_category_origi` LIKE `nested_category`;
#复制表结构及数据
CREATE TABLE `nested_category_origi` SELECT * FROM `nested_category`;
#----------------恢复 begin ---------------
SET autocommit=0;
START TRANSACTION;
INSERT INTO `nested_category`
(     `title`,
`parent`,
`lft`,
`rgt`,
`weight`,
`cn_name`,
`removed`
)
(
SELECT
`title`,
`parent`,
`lft`,
`rgt`,
`weight`,
`cn_name`,
`removed`
FROM `nested_category_origi`
)
ON DUPLICATE KEY UPDATE
parent = VALUES(parent),
lft = VALUES(lft),
rgt = VALUES(rgt),
weight = VALUES(weight),
cn_name = VALUES(cn_name),
removed = VALUES(removed)
;#COMMIT;
ROLLBACK;
SET autocommit=1;

#----------------恢复 end---------------

 


数据结构及算法原理:

    我们先把树按照水平方式摆开从根节点开始(“Food”),然后他的左边写上1然后按照树的顺序(从上到下)给“Fruit”的左边写上2。这样,你沿着树的边界走啊走(这就是“遍历”),然后同时在每个节点的左边和右边写上数字最后,我们回到了根节点“Food”在右边写上18。下面是标上了数字的树,同时把遍历的顺序用箭头标出来了
遍历的次序是:
1 从树的根结点出发,先访问结点左值。
2 递归子结点左值。
3 遍历到树叶结点(rgt-lft=2)时,访问本结点的右值
4 查看是否有兄弟结点,若有按 2,3操作
5 递归退回父结点,若有未访问的子树时,按2,3,4 ,否则就访问结点的右值,并一直回退至根结点的右值,整个过程结束。
结点间的关系  比如说 a结点与b结点有4种关系
a左b右  ->  a.rgt<b.lft
a右b左  ->  b.rgt<a.lft
a祖b孙  ->  b.lft between a.lft and a.rgt 
b祖a孙  ->  a.lft between b.lft and b.rgt
s1

    我们称这些数字为左值和右值(如,“Food”的左值是1,右值是18)正如你所见,这些数字按时了每个节点之间的关系因为“Red”有3和6两个值,所以,它是有拥有1-18值的“Food”节点的后续。同样的,我们可以推断所有左值大于2并且右值小于11的节点,都是有2-11的“Fruit” 节点的后续这样,树的结构就通过左值和右值储存下来了。这种数遍整棵树算节点的方法叫做“改进前序遍历树”算法

表数据如下设计:

s2

 


核心算法SQL语句
#每个结点与祖先或自己结点的连接关系  这个很关键
SELECT node.title,node.lft,node.rgt, (parent.title) AS parent_title,parent.lft AS parent_lft,parent.rgt AS parent_rgt
FROM nested_category node, nested_category parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
order by node.lft asc ;
Image
#带深度的树 参考上面查询的结果,分组后出现的个数就是深度
SELECT node.`title`, MAX(node.`cn_name`),COUNT(1) AS depth
FROM `nested_category` node , `nested_category` parent
WHERE node.`lft` BETWEEN parent.`lft` AND parent.`rgt`
GROUP BY node.`title`
ORDER BY node.`lft` ASC;
#前序查询树结点,按title分组,lft排序,node.title出现次数就是本结点树深度
SELECT node.title,MAX(node.lft) AS lft,MAX(node.rgt) AS rgt, MAX(parent.title) AS parent_title,MAX(parent.lft) AS parent_lft,MAX(parent.rgt) AS parent_rgt,COUNT(1) AS deepth
FROM nested_category node, nested_category parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.title
ORDER BY node.lft ASC;#查某个子树的结构 指定一个父结点
SELECT node.title,MAX(node.lft) AS lft,MAX(node.rgt) AS rgt, MAX(parent.title) AS parent_title,MAX(parent.lft) AS parent_lft,MAX(parent.rgt) AS parent_rgt
FROM nested_category node, nested_category parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt AND parent.`title`='Food'
GROUP BY node.title
ORDER BY node.lft;

#查找祖先
SELECT parent.title,parent.cn_name,parent.lft
FROM nested_category node, nested_category parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND node.title = 'Banana'
ORDER BY parent.lft ASC

#  ---------插入结点  begin ------------------------

SET autocommit=0;
START TRANSACTION;

#表加写锁
LOCK TABLES nested_category WRITE;

#要插入的父结点title
SET @current_title = 'Red';
SET @new_titile='Lichee',@new_cn_name='荔枝';
#set @new_titile='Tomato',@new_cn_name='西红柿';

#设置当前结点右值变量
SELECT @currnt_right:=rgt FROM nested_category WHERE title = @current_title;

#更新右值比@currnt_right大的,全部+2
UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @currnt_right;

#更新右值比@currnt_right大的,全部+2
UPDATE nested_category SET lft = lft + 2 WHERE lft > @currnt_right;

#插入新记录,左传=@currnt_right(原父结点的右值)   右值=@currnt_right+1
INSERT INTO `nested_category`
(`title`,`parent`,`lft`,`rgt`,`weight`,`cn_name`)
VALUES (@new_titile,@current_title,@currnt_right,(@currnt_right+1),NULL,@new_cn_name);

#原父结点的右值自增2
UPDATE nested_category SET rgt = (@currnt_right+2) WHERE rgt = @currnt_right;

#释放表锁
UNLOCK TABLES;

#commit;
ROLLBACK;
SET autocommit=1;

#  ---------插入结点  end ------------------------

#  ---------删除结点  begin ------------------------

SET autocommit=0;
START TRANSACTION;

#表加写锁
LOCK TABLES nested_category WRITE;

SET @current_title='Lichee';

SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE title = @current_title;

#删除本结点及子树结点
DELETE FROM nested_category WHERE lft BETWEEN @myLeft AND @myRight;

UPDATE nested_category SET rgt = rgt - @myWidth WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - @myWidth WHERE lft > @myRight;

#释放表锁
UNLOCK TABLES;

#commit;
ROLLBACK;
SET autocommit=1;

#  ---------删除结点  end ------------------------

#移动一棵子树,从本质来讲就是删除旧子树,在目标结点下追加新子树(新子树内部结构与旧子树相同)。移动后source与target是父子关系(source.lft between target.lft and target.rgt)
#这里的子树,特例是子树只有一个结点,就等同于删除一个结点,在目标结点下面追加一个新结点,跟上面的操作是一样的 
#上面的新增与删除都是子树的特例(只有一个结点的树默认宽度就是2)
#子树操作中宽度(就是子树根结点的宽度)这个概念很重要逻辑:  node_width=rgt-lft+1     (树枝结点宽度>2   树叶结点宽度==2)
#移动的偏移量(target.rgt-source.lft),移动有三种情况,左移右,右移左,子移祖。子树内部结构不变,但是全部子树内的结点lft,rgt都要修改加上偏移量。
#操作逻辑:
#    1 计算子树宽度 @sub_tree_width=source.rgt - source.lft + 1
#    2 修改子树各结点删除标志位为true
#    3 修改受删除子树后受影响结点的左值右值(忽略删除标志位为0)      when rgt>=source.rgt and removed=false    then -> set rgt=rgt-@sub_tree_width  ; when lft>=source.rgt and removed=false   then -> set lft=lft-@sub_tree_width
#    4 计算位移偏移量 @shift_diff=target.rgt - source.lft    获取target.rgt
#    5 修改受新增子树后受影响的结点的左值右值   when rgt>=target.rgt and removed=false     then -> set rgt=rgt+@sub_tree_width  ; when lft>=target.rgt and removed=false    then -> set lft=lft+@sub_tree_width
#    6 按偏移量原子树(removed=true)的左值右值            when lft between source.lft and source.rgt and removed=true    then -> set lft=lft+@shift_diff , rgt=rgt+@shift_diff
#    7 更新source.parent=target.id  (可选)
#  --------移动子树  begin ------------------------
#表加写锁
LOCK TABLES nested_category WRITE;
SET autocommit=0;
START TRANSACTION;#整个方法的入参
SET @source_node_pk='Red',@target_node_pk='Meat';

#1 计算子树宽度 @sub_tree_width=source.rgt - source.lft + 1
SELECT (node.`rgt`-node.`lft`+1),node.`lft`,node.`rgt` INTO @sub_tree_width,@source_lft,@source_rgt
FROM `nested_category` node
WHERE node.`title`=@source_node_pk;

#SELECT @sub_tree_width,@source_lft,@source_rgt FROM DUAL;

#2 修改子树各结点删除标志位为1,假删除 removed=true
UPDATE `nested_category`
SET removed=TRUE
WHERE lft BETWEEN @source_lft AND @source_rgt;

#3 修改受删除子树后受影响结点的左值右值      when rgt>=source.rgt    then -> set rgt=rgt-@sub_tree_width  ; when lft>=source.rgt    then -> set lft=lft-@sub_tree_width
/*
SELECT (rgt - @sub_tree_width) AS rgt,title,cn_name
FROM nested_category
WHERE rgt > @source_rgt;
*/

UPDATE nested_category
SET rgt = rgt - @sub_tree_width
WHERE rgt > @source_rgt AND removed=FALSE;

/*
SELECT (lft - @sub_tree_width) AS lft,title,cn_name
FROM nested_category
WHERE lft > @source_rgt;
*/
UPDATE nested_category
SET lft = lft - @sub_tree_width
WHERE lft > @source_rgt AND removed=FALSE;

#4 计算位移偏移量 @shift_diff=target.rgt - source.lft 获取目标结点的右值
#SELECT (SELECT MAX(rgt) FROM nested_category WHERE title=@target_node_pk)-(SELECT MAX(lft) FROM nested_category WHERE title=@source_node_pk) INTO @shift_diff FROM DUAL;
#计算子树移动的偏移量SQL2
SELECT SUM(CASE title
WHEN @source_node_pk THEN -1*lft
WHEN @target_node_pk THEN rgt
ELSE 0
END) INTO @shift_diff
FROM nested_category ;
#查看偏移量
#SELECT @shift_diff FROM DUAL;

SELECT rgt INTO @target_rgt
FROM `nested_category`
WHERE title=@target_node_pk;

#5 修改受新增子树后受影响的结点的左值右值   when rgt>=target.rgt     then -> set rgt=rgt+@sub_tree_width  ; when lft>=target.rgt    then -> set lft=lft+@sub_tree_width

UPDATE nested_category
SET rgt=rgt+@shift_diff
WHERE rgt >= @target_rgt AND removed=FALSE;

UPDATE nested_category
SET lft=(lft+@shift_diff)
WHERE lft > @target_rgt AND removed=FALSE;

#6 按偏移量更新原子树(removed=true)的左值右值                   when lft between source.lft and source.rgt     then -> set lft=lft+@shift_diff , rgt=rgt+@shift_diff
UPDATE nested_category
SET lft=lft+@shift_diff,
rgt=rgt+@shift_diff
WHERE removed=TRUE;

#6 更新source.parent=target.id  (可选)
UPDATE `nested_category`
SET parent=@target_node_pk
WHERE title=@source_node_pk;

COMMIT;
#ROLLBACK;
SET autocommit=1;

#释放表锁
UNLOCK TABLES;

#  --------移动子树  end ------------------------
标签:
admin

给我留言

Copyright © 大师级 保留所有权利.   Theme  大师级 桂ICP备14003638号

用户登录

分享到: