替罪羊樹(英語:Scapegoat tree)是電腦科學中,一種基於部分重建的自平衡二叉搜索樹。在替罪羊樹上,插入或刪除節點的平攤最壞時間複雜度,搜索節點的最壞時間複雜度是

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

在非平衡的二叉搜索樹中,每次操作以後檢查操作路徑,找到最高的滿足的結點,重建整個子樹。這樣就得到了替罪羊樹,而被重建的子樹的原來的根就被稱為替罪羊節點。常數一般選擇為左右。

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

理論

編輯

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

 

 

其中 函數(遞歸地)定義如下

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. (英文)
  1. ^ 1.0 1.1 1.2 1.3 1.4 引用錯誤:沒有為名為galperin_rivest的參考文獻提供內容