替罪羊树
替罪羊樹是電腦科學中，一種基於部分重建的自平衡二叉搜索樹。在替罪羊樹上，插入或刪除節點的平攤最壞時間複雜度是
  
    
      
        
          O
        
        (
        log
        ⁡
        n
        )
      
    
    {\displaystyle {\text {O}}(\log n)}
  ，搜索節點的最壞時間複雜度是
  
    
      
        
          O
        
        (
        log
        ⁡
        n
        )
      
    
    {\displaystyle {\text {O}}(\log n)}
  。
在非平衡的二叉搜索樹中，每次操作以後檢查操作路徑，找到最高的滿足
  
    
      
        max
        (
        s
        i
        z
        e
        (
        s
        o
        
          n
          
            L
          
        
        )
        ,
        s
        i
        z
        e
        (
        s
        o
        
          n
          
            R
          
        
        )
        )
        >
        α
        ∗
        s
        i
        z
        e
        (
        t
        h
        i
        s
        )
      
    
    {\displaystyle \max (size (son_{L}),size (son_{R}))>\alpha *size (this)}
  的結點，重建整個子樹。這樣就得到了替罪羊樹，而被重建的子樹的原來的根就被稱為替罪羊節點。常數
  
    
      
        α
      
    
    {\displaystyle \alpha}
  一般選擇為
  
    
      
        0.7
      
    
    {\displaystyle 0.7}
  左右。
與大多數平衡樹所採用的緩慢調整的方式不同，替罪羊樹採用了一種進行次數較少但代價較大的重構操作，即選擇一個節點作為「替罪羊」，並將這個節點的子樹直接重構成完全二元樹。因此，替罪羊樹的最壞時間複雜度為
  
    
      
        
          O
        
        (n)
      
    
    {\displaystyle {\text {O}}(n)}