文档章节

左右值树(转)

黄正文
 黄正文
发布于 2013/08/26 14:48
字数 1282
阅读 520
收藏 5
采用左右值编码实现无限分级树形结构

无限分级树形结构是在系统开发中很常见的,如下图
tree-menu


在之前实现这样的菜单一直是使用传统的方法,看数据表结构就一目了然
tree-traditional-db-structure


parent_id记录其直接父节点,组合树形结构的关键字段;parent_list记录其所有父节点,便于查询某个节点下所有子节点(一般使用MySQL的FIND_IN_SET函数),相对冗余。
对于这种结构生成树形的关键算法:根据parent_id组合一个父子(直接关系)节点映射表,即
2 => array(3, 4), 3 =>
array(5),然后递归优先遍历每个节点的子节点。
如果还需要按顺序排列,比如移动某个节点,则需要再添加一个字段来记录顺序。
优点:简单清晰,通俗易懂,添删改节点都很容易实现
缺点:查询效率不高(但一般树形结构都比较小)


再看另一种实现方式-左右值编码
其数据结构比较简单,但左右值需要经过遍历计算得到,很难看出直接父子关系的节点
tree-lr-db-structure


通过图了解左右值如何定义,类似前序遍历,父节点先访问,再访问子节点,递增标记,每个节点访问两次,分左右值。

所有子节点的左右值一定在父节点的左右值范围,所以通过语句left
> $parent_left AND right <
$parent_right就可以查询某个节点下所有的子节点,比FIND_IN_SET优雅。而查找直属的子节点只需要加上layer = $parent_layer
+ 1限制。


生成树操作
只需要按left字段从小到大顺序输出就行,缩进层次的就根据layer值,简单。


新增操作
比如在服务端类别添加一个子节点Python,一个节点占用2个值,新增的节点就是左右值就是父节点的右值和右值+1,而影响到的节点值(蓝色)都是大于等于父节点的右值(即>=10),都是原先的值加2。
新增前

新增后


删除操作
删除可参考新增操作,只是将>=父节点右值的所有节点值减去2


移动操作
主要是改变父节点和同层节点调换操作
移动操作基本基于一个公式:任何树所占的数字数目 = 根的右值
– 根的左值 + 1。


1.改变父节点
先看下移动PHP到客户端,即PHP的父节点换成客户端,这种情况下树节点上的变化
改变前

改变后

以PHP为根的树(虽然只有一个节点)的节点值变化是以新父节点的原右值为依据,如上图,新父节点的原右值为6,那PHP新的左值就是6,这样重新遍历PHP为根的树,就相当于这棵子树上的每个节点更新为:原值
– (根的原左值 – 根的新左值),所以PHP的右值就等于7 = 9 – (8 –
6)。
而除了PHP为根的树,其他节点更新的有一定范围,范围就是新父节点的右值和PHP原先的左值(或旧父节点的左值),因为PHP是向前移,范围内的节点值是往后移,需要加上PHP树的所占的数字数目,见上面公式,这里可以总结一个定律:
新父节点_right
<= ([left, right] + (移动_right – 移动_left + 1)) < 移动_left


再看下PHP向后移的情况,与前移类似,也是更新一定范围的节点,变成减定律:
移动_right < ([left, right] –
(移动_right – 移动_left + 1)) < 新父节点_left


2.同层节点调换
这里同层节点调换是指兄弟节点顺序调换,为了简化,一般是移到某个兄弟节点(参考点)后面,特殊情况是移到最前,这种情况参考点就是父节点。

如图,把语言一类移到兄弟节点-数据库后面。参考点是数据库,影响范围是语言的right与数据库的right之间的值,这类移动属于后移,根据上面提到的后移减定律,可得到公式:
移动_right
< ([left, right] – (移动_right – 移动_left + 1)) <=
参考点_right
而前移公式:参考点_right < ([left, right] + (移动_right – 移动_left + 1))
< 移动_left
如果是移到最前,只是前移公式的范围的左边界换为父节点_left,即公式为:父节点_left < ([left,
right] + (移动_right – 移动_left + 1)) <
移动_left。
对于是前移还是后移,可以根据移动节点的left值与参考点的right值的大小关系判断。


至此,关于左右值编码实现树形结构的关键操作都已说明,主要也是公式,范围是哪些,是加还是减,我也是纠结了几天,所以上面显得有点啰嗦,如果有兴趣的还是亲手推断,也许会发现比上面更简单的更新操作。

© 著作权归作者所有

黄正文
粉丝 14
博文 25
码字总数 14020
作品 0
巴南
程序员
私信 提问
二叉平衡树AVL Java实现

二叉平衡树 因为如果连续插入已经排好序的键到二叉查找树,二叉查找树相当于变成了一个链表,查找的时间会是,为了解决这个问题,二叉平衡树应运而生. 它是一 棵空树或它的左右两个子树的高度差的...

选择_9820
2018/06/14
0
0
[LeetCode] Count Univalue Subtrees 计数相同值子树的个数

/ 1 5/ 5 5 5 public: }; 解法二: class Solution {public: }; 我们还可以变一种写法,让递归函数直接返回以当前节点为根的相同值子树的个数,然后参数里维护一个引用类型的布尔变量,表示以...

机器的心脏
2017/12/15
0
0
[LeetCode] Longest Univalue Path 最长相同值路径

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root. Note: The length of path......

机器的心脏
2017/12/06
0
0
[LeetCode] Symmetric Tree 判断对称树

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric: 1/ 2 2/ / 3 4 4 3 But the following is......

机器的心脏
2017/12/11
0
0
数据结构与算法3- 二叉搜索树

数据结构与算法3- 二叉搜索树 小书匠 数据结构与算法 算法工程师 1. 二叉搜索树的定义: 二叉搜索树是一颗二叉树,可以为空。满足以下性质: 2. 二叉搜索树的基本操作: 查找最小值:在树的最...

NaiveCoder
2018/10/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

重新开始学Java——反射

概念 reflection:自省 反射:镜子可以反射阳光一个java类 或 对象 通过照"镜子"来认知自己 Java语言中是怎么实现照镜子? java.lang.reflect 包 提供了"照镜子"API(应用程序接口) 如果要...

大家都是低调来的
27分钟前
6
0
爬取720万条城市历史天气数据

内容爬虫完毕,校验完毕,缺失信息暂未统计。总数据720万,地区3200个,年份从2011-2019,大小950Mb,原始数据已丢失,需要的朋友可以自己运行脚本挂一晚上。中间遇到了很多坑,有机会我再写...

八音弦
30分钟前
21
0
python的字典类型

1、新建字典 通过键值对 dict_1 = {'a':1,'b':2,'c':3} 通过dict()函数 list_1 = ['adam', 'bob', 'cathy', 'david', 'emma'] list_2 = [1,2,3,4,5] dict_2 = dict(zip(list_1,list_2)) 2、字......

davidwbnu
32分钟前
7
0
springcloud vue.js 前后分离 activiti工作流

本商品为 :springcloud + Springboot 微服务\分布式 工作流 前后分离 + 跨域 版本 (权限控制到菜单和按钮) 后台框架 :springcloud Greenwich.SR1 + springboot 2.1.4 + activiti6.0.0 + ...

java框架开发者
38分钟前
12
0
【jQuery基础学习】07 jQuery表单插件-Form

本文转载于:专业的前端网站➦【jQuery基础学习】07 jQuery表单插件-Form 作用:jQuery Form插件的作用是为了让我们可以很方便地用ajax的方式提交表单,从而使我们提交表单的时候页面不用进行...

前端老手
47分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部