替罪羊樹

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

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

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

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

理論

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

${\displaystyle size(left)\leq \alpha size(node)}$

${\displaystyle size(right)\leq \alpha size(node)}$

其中${\displaystyle size}$函數（遞歸地）定義如下

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