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

php开发lamp

《西安--木木》-经历丰富了生活。 架构师QQ群: 246695517

 
 
 

日志

 
 

基于左右值的无限级分类算法 – 插入节点  

2014-04-01 10:38:26|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

关系型数据库一般都是以平面方式来存储我们的数据,这就造成了我们在实现一些数据结构上的麻烦,比如说如何实现高效的无限级的网站分类,这里MySQL的《Managing Hierarchical Data in MySQL》给出了一个比较好的办法,基于一种左右值的算法,这也是我目前接触到的查询比较高效的算法了,另外Gijs Van Tulder在sitepoint也写过一篇《Storing Hierarchical Data in a Database》文章专门讲解这个算法,我在这里再总结一下,首先看下面的这张图:

基于左右值无限级分类.png

通 过这张图大家应该能很清晰的看出对于一种简单的树形结构分类的左右值处理的方式,这是一种类似于树的深度优先的遍历,其次这些左右权值很清晰的表明了一种 隶属的包含关系,比如Fruit的左右值分别为1~6,那么说,所有在这个之间的值都是其子节点(Child Node)。对于数据库的遍历,我们可以很轻松的指定一个范围,然后执行一条SELECT查询语句。

下面我就先增加做个讲解,假设数据表的结构如下:

1
2
3
4
5
6
7
8
9
+-------------+-----------------+
| name        | type            |
+-------------+-----------------+
| ID          | INT AUTOINC     |
| Name        | VARCHAR     	|
| PID         | INT             |
| LeftValue   | INT             |
| RightValue  | INT             |
+-------------+-----------------+

首 先ID表示节点的唯一ID标识,Name表示节点的名称,PID表示所继承的父节点ID,LeftValue和RightValue顾名思义分别代表了左 右值,由这些可以知道我们可以通过ID和Name的值定位到一个节点,当然这里的前提是Name必须是唯一的,否则我们只能使用ID来定位,在下面的讲解 中,我将只采用ID的方式定位一个节点。

我在这里用伪码将一些操作总结一下,假设以this代表这张关系表,假设我们插入一个节点,节点的右值始终大于节点的左值,对于表空的情况来说,右值比左值大1个单位。那么简单的插入函数可以像下面这样表示:

1
2
3
4
5
6
function insertNode(value) 
{ 
  left = value + 1; 
  right = value + 2; 
  this.insert(left, right);  
}

这里很明显,如果表为空,那么value就为0,然后我们就插入了第一个节点,可能有童鞋要问,value是神马东东?下面的讲解中我将告诉你。

当 插入第二个节点时,问题就来了,我们遇到了三个问题,第一是这时插入分为两种情况,同级节点和子级节点,第二个问题是如果得到自身的左右权值,第三个问题 是先前插入的节点权值要发生改变,是的,但是是怎样的改变法呢?不着急,让我们先看第一个问题,第一个问题很好解决,我们分两种情况讨论就可以了,先讨论 第一种情况同级节点插入(Same level node insert),什么是同级关系,所谓的同级关系也就是说是同等级的节点,该节点与被插入位置的节点是并列关系,也就是说是邻居节点 (Neighbours’Node)。比如我们希望插入节点后结构图变成这样:

同级邻居节点的插入.png

原 先表中只有Fruit,后来插入了Animal,那么Animal和Fruit就是一种并列关系,接下来让我们看下第二个问题,如何知道自身的左右值?再 回到刚才讲解insertNode(value)这个地方,嘿,这时我们的value发挥作用了,它给我们提供了一个基准,首先大家发现任何一个叶子节点 的右值减去左值都得到1,这个是必然的,也是我们insertNode函数里面的+1和+2的由来,那么如何得到value这个基准值呢?你可以试着将这 张图拓展一下,然后多列出一些同级节点,然后就像我那样画出箭头,然后用手指优雅的划一下,然后你就会发现,第一次访问到我们新插入的同级节点是从该节点 的左边第一个同级节点访问到的,这句话比较讲,这样吧,我们看图,比如说Animal是我们后插入的,那么根据箭头,我们第一次访问到Animal这个节 点时是从Fruit这个节点过来的,Fruit是Animal的第一个左节点,同样的你会发现一个规律,计数也恰巧从Fruit的右值开始,6、7、8, 难道是巧合,这不是巧合,你多试几次就能发现规律,那么我们的基准值value也很明显了,那就是所有同级节点(不包括待插入节点)的右值的最大值,下面 我们要直面第三个问题,Fruit的值要改变?要改变吗?不需要!那么第三个问题不需要管了么,答案是否定的,大家发现每个节点的左值小于新插入节点的左 值时说明该节点左值没有越界,所以不需要更新,同样的,每个节点的右值小于新插入节点的左值时也说明不需要更新,那么什么情况下需要更新呢?让我们先看 图:

同级插入节点其他节点左右值更新示意图.png

从 图中不难看出先前我们的插入属于结尾附加,所以不需要更新任何节点,然而当节点树比较复杂时,有可能会出现中间新插入的现象,那么我们就有必要更新所有插 入之后的节点的左右数值了,更新的基准是什么?更新多少?从上图大家可能会发现,我们插入的节点所赋予的新的左右权值为6和7,如果插入位置位于段中的 话,那么势必要占去原节点群6和7这两个权值,是的,所有大于5的都要向后挪,具体挪几个,刚才已经说,占去的只是6和7两个权值,那么就是要挪2个位 置,即在原有的权值的基础上增加2,判断的基准就是5,5是什么,想必大家能够猜到,5就是前面我讲的insertNode(value)的value基 准值。

基于上面的论点,首先我们来看段根据指定的基准条件进行权值增加的伪码算法:

1
2
3
4
5
6
7
8
9
10
11
12
function addAllNodeValues(new_left, new_right, fn_compare) 
{ 
  while(this = this.next) { 
    left = this.node.left; 
    right = this.node.right; 
    if (fn_compare(left)) 
        left = left + new_left; 
    if (fn_compare(right)) 
        right = right + new_right; 
    this.update(left, right); 
  } 
}

上 述算法中,new_left是新增加的左值,new_right为新增加的右值,注意,这里是指在原有的基础上进行加权,fn_compare是个回调函 数,返回true是才进行加权,这个回调函数仅一个参数,即遍历所有节点所获得的左(右)的权值。下面改进过的插入同级节点的算法如下:

1
2
3
4
5
6
7
function insertSameLevelNode(parent_id) 
{ 
  // 如果找不到就返回0 
  value = this.nodes(parentId == parent_id).rights.maxValue; 
  addAllNodeValues(2, 2, function(cmp_value){return (cmp_value > value)}); 
  insertNode(value); 
}

到 这里同级节点插入已经讲解完了,接下来将要谈谈子节点的插入,我们回到文章开始的那幅图,假设Fruit节点下插入Apple,根据上面同级节点的插入同 理可知,Apple这个节点的左右值是基于Fruit的左值得到的,大家可以看箭头的方向,那么value基准值即为Fruit的左值。同样的我们仍然需 要判断value是否越界,判断的方式和上面一样,综合来看得到算法如下:

1
2
3
4
5
6
7
function insertChildNode(parent_id) 
{
  // 因为父节点是唯一的,所以只要获取第一个左值即可
  value = this.nodes(id == parent_id).lefts[0]; 
  addAllNodeValues(2, 2, function(cmp_value){return (cmp_value > value)}); 
  insertNode(value); 
}

至此,关于插入节点的算法已经讲解完毕!

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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