替罪羊樹

替罪羊樹（英語：Scapegoat tree）是電腦科學中，一種基於部分重建的自平衡二叉搜索樹。在替罪羊樹上，插入或刪除節點的平攤最壞時間複雜度是${\text{O}}(\log n)$，搜索節點的最壞時間複雜度是${\text{O}}(\log n)$。

替罪羊樹
類型	樹
發明時間	1989年
發明者	阿爾尼·安德森、伊加爾·加爾佩林、羅納德·李維斯特
用大O符號表示的時間複雜度
算法 平均 最差 空間 $O(n)$ 搜尋 $O(\log n)$ $O(\log n)$ 插入 $O(\log n)$ $O(n)$ 刪除 $O(\log n)$ $O(n)$

在非平衡的二叉搜索樹中，每次操作以後檢查操作路徑，找到最高的滿足$\max(size(son_{L}),size(son_{R}))>\alpha *size(this)$的結點，重建整個子樹。這樣就得到了替罪羊樹，而被重建的子樹的原來的根就被稱為替罪羊節點。常數$\alpha$一般選擇為$0.7$左右。

與大多數平衡樹所採用的緩慢調整的方式不同，替罪羊樹採用了一種進行次數較少但代價較大的重構操作，即選擇一個節點作為「替罪羊」，並將這個節點的子樹直接重構成完全二叉樹。因此，替罪羊樹的最壞時間複雜度為${\text{O}}(n)$

理論

說一個二叉查找樹是平衡的，若且唯若根節點左側與右側的節點各佔一半，而替罪羊樹則放鬆了這一限制，即，只需要滿足

$size(left)\leq \alpha size(node)$

$size(right)\leq \alpha size(node)$

其中$size$函數（遞歸地）定義如下

function size(node)
    if node = nil then
        return 0
    else
        return size(node->left) + size(node->right) + 1
    end if
end function

參考文獻

• Andersson, Arne. Improving partial rebuilding by using simple balance criteria. Proc. Workshop on Algorithms and Data Structures. Springer-Verlag: 393–402. 1989. doi:10.1007/3-540-51542-9_33. （英文）
• Galperin, Igal; Rivest, Ronald L. Scapegoat trees. Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms. 1993: 165–174. （英文）