php:树形结构的算法 3

来源：     作者：     时间：2008-08-17     点击：

那么对于这样的结构我们该如何增加，更新和删除一个节点呢？ 增加一个节点一般有两种方法：
  
  保留原有的name 和parent结构，用老方法向数据中添加数据，每增加一条数据以后使用rebuild_tree函数对整个结构重新进行一次编号。
  效率更高的办法是改变所有位于新节点右侧的数值。举例来说：我们想增加一种新的水果"Strawberry"（草莓）它将成为"Red"节点的最后一个子节点。首先我们需要为它腾出一些空间。"Red"的右值应当从6改成8，"Yellow 7-10 "的左右值则应当改成 9-12。 依次类推我们可以得知，如果要给新的值腾出空间需要给所有左右值大于5的节点 （5 是"Red"最后一个子节点的右值） 加上2。 所以我们这样进行数据库操作：
  
  UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
  UPDATE tree SET lft=lft+2 WHERE lft>5;
  这样就为新插入的值腾出了空间，现在可以在腾出的空间里建立一个新的数据节点了， 它的左右值分别是6和7
  
  INSERT INTO tree SET lft=6, rgt=7, name='Strawberry';
  
  再做一次查询看看吧！怎么样？很快吧。
  好了，现在你可以用两种不同的方法设计你的多级数据库结构了，采用何种方式完全取决于你个人的判断，但是对于层次多数量大的结构我更喜欢第二种方法。如果查询量较小但是需要频繁添加和更新的数据，则第一种方法更为简便。
  
  另外，如果数据库支持的话 你还可以将 rebuild_tree() 和 腾出空间的操作写成数据库端的触发器函数， 在插入和更新的时候自动执行， 这样可以得到更好的运行效率， 而且你添加新节点的SQL语句会变得更加简单。
  类递归法
  Posted by 访客 on 2004, May 31 - 9:18am.
  我用类 递归法 写了段程序，跟文章中的递归不完全一样
  正准备移植到 xoops 中:
  http://dev.xoops.org/modules/xfmod/project/?ulink
  
  已经出现内存溢出现象
  不过准备继续采用递归法，只是需要继续改进
  
  希望有机会跟各位讨论cms
  » reply to this comment
  还是两种方法之比较
  Posted by 访客 on 2004, March 17 - 8:30pm.
  　　仔细研究了一下这篇文章，觉得受益非浅，但后来又想了想，觉得有一下问题（为了好记忆，毗邻目录模式我称为递归的方法，预排序遍历树算法我称为预排序树的方法）：
  
  1、两种方法比较大的区别是递归是在查询的时候要用到堆栈进行递归，预排序树则是在更新节点时要进行半数（指所插入节点的后半部分）节点的更新。虽然您也说了，如果节点多了，更新又频繁，预排序树效率会降低，采用递归会好些，而如果节点层次较多的话，首先递归会导致堆栈溢出，再者递归本身效率就不高，加上每一层递归都要操作数据库，总体效果也不会理想。我目前的做法是一次性把数据全取出来，然后对数组进行递归操作，会好一些；再进一步改进的话，可以为每行记录增加一个ROOT根节点（目前是只记录相邻的父节点），这样在查找分支树时效率就会比较高了，更新树的时候也是十分便捷的，应该是一种比较好的方式。
  
  2、改进递归的方式，文章中在计算预排序树节点的左右值的时候其实也用到了一种遍历方式，通过数组替代堆栈，手工实现压栈和弹出；这种方法如果引用到递归算法中，在进行递归的时候也用数组替代堆栈的话，也可以提高递归的效率的。
  
  3、并发，如果考虑到并发的情况，尤其是更新树的时候，预排序树大面积更新节点信息的方法需要额外注意采用加锁和事务的机制保证数据一致性。
  
  4、多根节点或者多父节点的情况，在这种情况下，显然就不是一个标准的二叉树或者多叉树了，预排序树算法需要进行比较大的改进才能适应，而递归的方法则应用自如，所以在这种情况下，递归的适应性较强。这是当然的了，因为递归的方法就是链表的一种形式，树、图都可以用链表来表达，当然适应力强了。
  
  5、直观，如果不用程序操作，直接观察数据库中存储的数据的话，显然递归方式下存储的数据比较直观，而预排序树的数据很难直接阅读（针对层次关系来说），这在数据交换中是不是会有影响呢？
  
  　　总体来说，我个人比较喜欢用递归的方法，但一直担心递归对效率的影响，所幸还没有接触过规模较大的分类层次，递归用数组替代堆栈会是一种比较好的改进方法。而预排序树不失为一种解决简单树的高效方法，用习惯了，也应该是非常出色的，尤其是它从叶子节点到根节点的反向查找非常方便。
  
  Fwolf
  www.fwolf.com
  » reply to this comment
  非常高兴看到你的回复
  Posted by shuke on 2004, March 18 - 5:47am.
  非常高兴你这么认真的读完这篇文章。这篇文章其实是原来发表在sitepoint.com上的，我把它翻译了一下，希望给希望初学入门的朋友介绍一些方法，抛砖引玉。你的方法也很好，有机会我会试一下的。（如果你有兴趣的话，何不就上面的例子把你的方法和具体实现的代码也写成教程发出来吧，这样大家就用更加实际的例子来模仿了）如果你对数据库中保存多级结构有兴趣研究的话，这里还有两个连接也很不错可以作为参考：
  介绍了常见的4中方法
  一次查询，数组排序的脚本我想你的脚本肯定比这个强。
  另外我看到你也用drupal，它还有一个高级功能叫分布式用户验证系统，只要在任何一个drupal的站点注册以后就可以登录访问其它的drupal站点了。挺有意思的。
  祝好！
  » reply to this comment
  用循环来建树已经实现了
  Posted by 访客 on 2004, March 25 - 10:10pm.
  你上次提供的资料我已经都看过了，不过老实说，第一篇文章里没有太多新东西，或许是我没看太明白吧，第二个居然是PHP3写的，程序结构没有细看，用到太多的函数交叉。
  正好我在一个系统中用户角色要用到分级，按照数组的思路就把遍历写了下来，没有时间整理，先放到这里你看看吧，数据库用的是ADODB，程序是直接从系统中摘出来的，希望能够描述得清楚，主要是利用了PHP强大的数组操作，用循环来进行递归。注释里是一种相近的方法，只是处理结果的时机不同而已。