Loading AI tools
来自维基百科,自由的百科全书
替罪羊樹(英語:Scapegoat tree)是電腦科學中,一種基於部分重建的自平衡二叉搜索樹。在替罪羊樹上,插入或刪除節點的平攤最壞時間複雜度是,搜索節點的最壞時間複雜度是。
在非平衡的二叉搜索樹中,每次操作以後檢查操作路徑,找到最高的滿足的結點,重建整個子樹。這樣就得到了替罪羊樹,而被重建的子樹的原來的根就被稱為替罪羊節點。常數一般選擇為左右。
與大多數平衡樹所採用的緩慢調整的方式不同,替罪羊樹採用了一種進行次數較少但代價較大的重構操作,即選擇一個節點作為「替罪羊」,並將這個節點的子樹直接重構成完全二元樹。因此,替罪羊樹的最壞時間複雜度為
說一個二元搜尋樹是平衡的,若且唯若根節點左側與右側的節點各占一半,而替罪羊樹則放鬆了這一限制,即,只需要滿足
其中函數(遞歸地)定義如下
function size(node) if node = nil then return 0 else return size(node->left) + size(node->right) + 1 end if end function
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.