php:樹形結構的算法 3 - php語言 -

php:樹形結構的算法 3

時間:2013-05-29 13:47:30   來源:   評論:加載中...   點擊:加載中...
那么對于這樣的結構我們該如何增加,更新和刪除一個節點呢? 增加一個...
    那么對于這樣的結構我們該如何增加,更新和刪除一個節點呢? 增加一個節點一般有兩種方法:
  
  保留原有的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強大的數組操作,用循環來進行遞歸。注釋里是一種相近的方法,只是處理結果的時機不同而已。


相關熱詞搜索:

 
上一篇:php:樹形結構的算法 2
下一篇:php:樹形結構的算法 4
收藏 將此文推薦給朋友
分享到:
10个数复式三中三多少组公式