注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

小葫芦君(汉斯的博客)

博客迁移到新博客:https://blog.ssxingshou.com

 
 
 

日志

 
 
关于我

小小葫芦商城,为您提供高品质的商品,一流的产品,一流的包装服务,一流的物流服务,放心购买

网易考拉推荐

2012年03月15日-无限级分类:预排序遍历树算法与递归  

2012-03-15 09:27:52|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1 lft 代表左 left
2 rgt 代表右 right
下面这个图是一个典型的结构

2012年03月15日 - hans(汉斯) - 汉斯的博客

1 查看整个树(A)有多少节点(包含自己)
直接看根节点就行了 (right-left+1)/2 = (20-1+1)/2 = 10
这个数有10个节点
2 查看从节点A到E的路径
select * from tree where lft between 1 and 6 and rgt between 7 and 20 order by lft
得到的结果是A,B,D,E 这4个节点的数据,且按照访问路径的顺序

3 得到某个节点下面的所有节点,且按照树状结构返回
用B做例子
select * from tree t inner join tree t2 on (t.lft > t2.lft and t.rgt<t2.rgt) and t2.Id=@Id
拿到的结果是 C,D,E,F,而且顺序也是正确的。
要包含节点本身则:
select * from tree t inner join tree t2 on (t.lft between t2.lft and t2.rgt) and t2.Id=@Id

4 查询所有无分支的节点 条件:右边 = 左边L + 1
SELECT * FROM tree WHERE rgt = lft + 1;

5插入新节点
算法详解:
1.所有分类 左边和右边的值 > 插入节点的左边节点记录的右值 的全部 + 2
2.插入节点 左值 = 插入位置左边节点记录的右值 + 1, 右值 = 插入位置左边节点记录的右值 + 2
例子:
在 R = 9(L8, R9)与 L = 10(L10,R11) 节点之间插入一个新节点
那么所有 左值 和 右值 > 9 的节点的左值和右值需要 + 2
例如新节点右边的节点(L10,R11)左值右值都需要 + 2 那么插入后的新值为 L12 R13
新节点的左值为 9 + 1 = 10 右值为 9 + 2 = 11
SQL语句实现
LOCK TABLE nested_category WRITE;
SELECT @myRight := rgt FROM nested_category
WHERE name = 'TELEVISIONS';
UPDATE nested_category SET rgt = rgt + 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft + 2 WHERE lft > @myRight;
INSERT INTO nested_category(name, lft, rgt) VALUES('GAME CONSOLES', @myRight + 1, @myRight + 2);
UNLOCK TABLES;

6删除新节点
删除节点的算法与添加一个节点的算法相反

删除一个没有子节点的节点
LOCK TABLE nested_category WRITE;
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'GAME CONSOLES';
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;

删除一个分支节点和它所有的子节点
LOCK TABLE nested_category WRITE;
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'MP3 PLAYERS';
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;


删除一个节点后移动其字节点到
LOCK TABLE nested_category WRITE;
SELECT @myLeft := lft, @myRight := rgt, @myWidth := rgt - lft + 1
FROM nested_category
WHERE name = 'PORTABLE ELECTRONICS';
DELETE FROM nested_category WHERE lft = @myLeft;
UPDATE nested_category SET rgt = rgt - 1, lft = lft - 1 WHERE lft BETWEEN @myLeft AND @myRight;
UPDATE nested_category SET rgt = rgt - 2 WHERE rgt > @myRight;
UPDATE nested_category SET lft = lft - 2 WHERE lft > @myRight;
UNLOCK TABLES;

使用这种方法比使用递归快数十倍
预排序遍历树算法的核心就是牺牲了写的性能来换取读取的性能
当你的应用程序 读压力>写压力 时,可以尝试使用

  评论这张
 
阅读(1009)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017