替罪羊树(英语: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的参考文献提供内容