php:樹形結(jié)構的算法 3

2024-09-08 23:18:45

字體：大中小

供稿：網(wǎng)友

    那么對于這樣的結(jié)構我們該如何增加，更新和刪除一個節(jié)點呢？增加一個節(jié)點一般有兩種方法：

  保留原有的name 和parent結(jié)構，用老方法向數(shù)據(jù)中添加數(shù)據(jù)，每增加一條數(shù)據(jù)以后使用rebuild_tree函數(shù)對整個結(jié)構重新進行一次編號。
  效率更高的辦法是改變所有位于新節(jié)點右側(cè)的數(shù)值。舉例來說：我們想增加一種新的水果"strawberry"（草莓）它將成為"red"節(jié)點的最后一個子節(jié)點。首先我們需要為它騰出一些空間。"red"的右值應當從6改成8，"yellow 7-10 "的左右值則應當改成 9-12。依次類推我們可以得知，如果要給新的值騰出空間需要給所有左右值大于5的節(jié)點（5 是"red"最后一個子節(jié)點的右值）加上2。所以我們這樣進行數(shù)據(jù)庫操作：

  update tree set rgt=rgt+2 where rgt>5;
  update tree set lft=lft+2 where lft>5;
  這樣就為新插入的值騰出了空間，現(xiàn)在可以在騰出的空間里建立一個新的數(shù)據(jù)節(jié)點了，它的左右值分別是6和7

  insert into tree set lft=6, rgt=7, name='strawberry';

  再做一次查詢看看吧！怎么樣？很快吧。
  好了，現(xiàn)在你可以用兩種不同的方法設計你的多級數(shù)據(jù)庫結(jié)構了，采用何種方式完全取決于你個人的判斷，但是對于層次多數(shù)量大的結(jié)構我更喜歡第二種方法。如果查詢量較小但是需要頻繁添加和更新的數(shù)據(jù)，則第一種方法更為簡便。

  另外，如果數(shù)據(jù)庫支持的話你還可以將 rebuild_tree() 和騰出空間的操作寫成數(shù)據(jù)庫端的觸發(fā)器函數(shù)，在插入和更新的時候自動執(zhí)行，這樣可以得到更好的運行效率，而且你添加新節(jié)點的sql語句會變得更加簡單。
  類遞歸法
  posted by 訪客 on 2004, may 31 - 9:18am.
  我用類遞歸法寫了段程序，跟文章中的遞歸不完全一樣
  正準備移植到 xoops 中:
  http://dev.xoops.org/modules/xfmod/project/?ulink

  已經(jīng)出現(xiàn)內(nèi)存溢出現(xiàn)象
  不過準備繼續(xù)采用遞歸法，只是需要繼續(xù)改進

  希望有機會跟各位討論cms
  » reply to this comment
  還是兩種方法之比較
  posted by 訪客 on 2004, march 17 - 8:30pm.
  　　仔細研究了一下這篇文章，覺得受益非淺，但后來又想了想，覺得有一下問題（為了好記憶，毗鄰目錄模式我稱為遞歸的方法，預排序遍歷樹算法我稱為預排序樹的方法）：

  1、兩種方法比較大的區(qū)別是遞歸是在查詢的時候要用到堆棧進行遞歸，預排序樹則是在更新節(jié)點時要進行半數(shù)（指所插入節(jié)點的后半部分）節(jié)點的更新。雖然您也說了，如果節(jié)點多了，更新又頻繁，預排序樹效率會降低，采用遞歸會好些，而如果節(jié)點層次較多的話，首先遞歸會導致堆棧溢出，再者遞歸本身效率就不高，加上每一層遞歸都要操作數(shù)據(jù)庫，總體效果也不會理想。我目前的做法是一次性把數(shù)據(jù)全取出來，然后對數(shù)組進行遞歸操作，會好一些；再進一步改進的話，可以為每行記錄增加一個root根節(jié)點（目前是只記錄相鄰的父節(jié)點），這樣在查找分支樹時效率就會比較高了，更新樹的時候也是十分便捷的，應該是一種比較好的方式。

  2、改進遞歸的方式，文章中在計算預排序樹節(jié)點的左右值的時候其實也用到了一種遍歷方式，通過數(shù)組替代堆棧，手工實現(xiàn)壓棧和彈出；這種方法如果引用到遞歸算法中，在進行遞歸的時候也用數(shù)組替代堆棧的話，也可以提高遞歸的效率的。

  3、并發(fā)，如果考慮到并發(fā)的情況，尤其是更新樹的時候，預排序樹大面積更新節(jié)點信息的方法需要額外注意采用加鎖和事務的機制保證數(shù)據(jù)一致性。

  4、多根節(jié)點或者多父節(jié)點的情況，在這種情況下，顯然就不是一個標準的二叉樹或者多叉樹了，預排序樹算法需要進行比較大的改進才能適應，而遞歸的方法則應用自如，所以在這種情況下，遞歸的適應性較強。這是當然的了，因為遞歸的方法就是鏈表的一種形式，樹、圖都可以用鏈表來表達，當然適應力強了。

  5、直觀，如果不用程序操作，直接觀察數(shù)據(jù)庫中存儲的數(shù)據(jù)的話，顯然遞歸方式下存儲的數(shù)據(jù)比較直觀，而預排序樹的數(shù)據(jù)很難直接閱讀（針對層次關系來說），這在數(shù)據(jù)交換中是不是會有影響呢？

  　　總體來說，我個人比較喜歡用遞歸的方法，但一直擔心遞歸對效率的影響，所幸還沒有接觸過規(guī)模較大的分類層次，遞歸用數(shù)組替代堆棧會是一種比較好的改進方法。而預排序樹不失為一種解決簡單樹的高效方法，用習慣了，也應該是非常出色的，尤其是它從葉子節(jié)點到根節(jié)點的反向查找非常方便。

  fwolf
  www.fwolf.com
  » reply to this comment
  非常高興看到你的回復
  posted by shuke on 2004, march 18 - 5:47am.
  非常高興你這么認真的讀完這篇文章。這篇文章其實是原來發(fā)表在sitepoint.com上的，我把它翻譯了一下，希望給希望初學入門的朋友介紹一些方法，拋磚引玉。你的方法也很好，有機會我會試一下的。（如果你有興趣的話，何不就上面的例子把你的方法和具體實現(xiàn)的代碼也寫成教程發(fā)出來吧，這樣大家就用更加實際的例子來模仿了）如果你對數(shù)據(jù)庫中保存多級結(jié)構有興趣研究的話，這里還有兩個連接也很不錯可以作為參考：
  介紹了常見的4中方法
  一次查詢，數(shù)組排序的腳本我想你的腳本肯定比這個強。
  另外我看到你也用drupal，它還有一個高級功能叫分布式用戶驗證系統(tǒng)，只要在任何一個drupal的站點注冊以后就可以登錄訪問其它的drupal站點了。挺有意思的。
  祝好！
  » reply to this comment
  用循環(huán)來建樹已經(jīng)實現(xiàn)了
  posted by 訪客 on 2004, march 25 - 10:10pm.
  你上次提供的資料我已經(jīng)都看過了，不過老實說，第一篇文章里沒有太多新東西，或許是我沒看太明白吧，第二個居然是php3寫的，程序結(jié)構沒有細看，用到太多的函數(shù)交叉。
  正好我在一個系統(tǒng)中用戶角色要用到分級，按照數(shù)組的思路就把遍歷寫了下來，沒有時間整理，先放到這里你看看吧，數(shù)據(jù)庫用的是adodb，程序是直接從系統(tǒng)中摘出來的，希望能夠描述得清楚，主要是利用了php強大的數(shù)組操作，用循環(huán)來進行遞歸。注釋里是一種相近的方法，只是處理結(jié)果的時機不同而已。

上一篇：php:樹形結(jié)構的算法 2

下一篇：php:樹形結(jié)構的算法 4