基本介紹
- 中文名：替罪羊樹
- 所屬學科：計算機科學
簡介,解釋,
簡介
在非平衡的二叉搜尋樹中，每次操作以後檢查操作路徑，找到最高的滿足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 無異。
