替罪羊樹

替罪羊樹

替罪羊樹是計算機科學中,一種基於部分重建的自平衡二叉搜尋樹。在替罪羊樹上,插入或刪除節點的平攤最壞時間複雜度是O(log n),搜尋節點的最壞時間複雜度是O(log n)。

簡介

在非平衡的二叉搜尋樹中,每次操作以後檢查操作路徑,找到最高的滿足max(size(son_L),size(son_R))>alpha*size(this)的結點,重建整個子樹。這樣就得到了替罪羊樹,而被重建的子樹的原來的根就被稱為替罪羊節點。替罪羊樹替罪羊樹是一棵自平衡二叉搜尋樹,由ArneAndersson提出。替罪羊樹的主要思想就是將不平衡的樹壓成一個序列,然後暴力重構成一顆平衡的樹。

這裡的平衡指的是:對於某個 0.5<=alpha<=1 滿足 size( lson(x) )<=alpha*size(x) 並且 size( rson(x) )<=alpha*size(x),即這個節點的兩棵子樹的 size 都不超過以該節點為根的子樹的 size,那么就稱這個子樹(或節點)是平衡的, alpha 最好不要選 0.5 ,容易T飛,一般選 0.75 就挺好的。

至於複雜度,雖說是重構,但複雜度並不高,壓扁和重建都是遞歸操作,也就是像線段樹一樣的 log 級別,由於平衡的限制,插入,刪除,即查詢等操作也會控制在一個較低的級別,均攤下來替罪羊樹的總複雜度是 O(logn)的。

解釋

一般的平衡樹都依賴於旋轉操作,如 Treap,Splay,SBT 等,它們都需要用到旋轉操作來保持樹的平衡。旋轉操作在統計一些可以快速合併的信息的時候是沒有問題的,但對於更加複雜的信息,就會遇到複雜度的問題。考慮一個簡單的例子,我們想在一個平衡樹的每個節點上維護一個集合,存儲子樹內所有的數。此時一次旋轉操作的代價可能會達到 O(n) ,傳統的旋轉平衡樹就無法發揮作用了。而重量平衡樹則不同,它每次操作影響的最大子樹的大小是最壞或者均攤或者期望的O(log n) 。這樣即使按照上面所說的方式維護,複雜度也是可以接受的。替罪羊樹就是重量平衡樹中比較常用的一種,與其他數據結構相比,它的優點有:

①:思維難度小,和其他平衡樹的思維難度差不多;

②:代碼量少,思路清晰,實現簡單,容易調試;

③:速度不慢;

④:不是旋轉機制;

替罪羊樹:

替罪羊樹是一種依賴於暴力重構操作的平衡樹。我們定義一個平衡樹因子α ,對替罪羊樹的每個節點t ,我們都需要滿足:max(size l,size r)<=α*szie t其中l,r 分別是t 的左右子樹。這個性質稱為平衡性質。它的實現方式也非常簡潔明了,每次我們進行普通 BST 的插入操作後,都要在這條插入的路徑上,尋找最高的(深度最小)不滿足平衡性質的節點,(如果有不滿足平衡性質節點的話)我們將這個節點以及它的子樹內所有節點,暴力重構成一棵完全二叉樹。其餘操作全部與普通 BST 無異。

相關詞條

熱門詞條

聯絡我們