本條目存在以下問題 ,請協助
改善本條目 或在
討論頁 針對議題發表看法。
此條目需要
精通或熟悉相关主题的编者 参与及协助编辑。
(2014年5月6日 ) 請邀請 適合的人士改善本条目 。更多的細節與詳情請參见討論頁 。
替罪羊树 类型 樹 发明时间 1989年 发明者 阿爾尼·安德森、伊加爾·加爾佩林、羅納德·李維斯特 用大O符号 表示的时间复杂度 算法
平均
最差 空间
O
(
n
)
{\displaystyle O(n)}
搜索
O
(
log
n
)
{\displaystyle O(\log n)}
O
(
log
n
)
{\displaystyle O(\log n)}
[ 1] :165 插入
O
(
log
n
)
{\displaystyle O(\log n)}
[ 1] :165
O
(
n
)
{\displaystyle O(n)}
[ 1] :167 删除
O
(
log
n
)
{\displaystyle O(\log n)}
[ 1] :165
O
(
n
)
{\displaystyle O(n)}
[ 1] :167
替罪羊树 (英語:Scapegoat tree )是電腦科學 中,一种基于部分重建的自平衡二叉搜索树 。在替罪羊树上,插入或删除节点的平攤 最壞時間複雜度 是
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)}
理论
说一个二叉查找树是平衡的,当且仅当根节点左侧与右侧的节点各占一半,而替罪羊树则放松了这一限制,即,只需要满足
s
i
z
e
(
l
e
f
t
)
≤
α
s
i
z
e
(
n
o
d
e
)
{\displaystyle size(left)\leq \alpha size(node)}
s
i
z
e
(
r
i
g
h
t
)
≤
α
s
i
z
e
(
n
o
d
e
)
{\displaystyle size(right)\leq \alpha size(node)}
其中
s
i
z
e
{\displaystyle size}
函数(递归地)定义如下
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.0 1.1 1.2 1.3 1.4 引用错误:没有为名为galperin_rivest
的参考文献提供内容