替罪羊树

替罪羊树（英语：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