查看“︁替罪羊树”︁的源代码

{{multiple issues|
{{expand|time=2014-05-06T03:23:19+00:00}}
{{expert|time=2014-05-06T03:23:19+00:00}}
{{refimprove|time=2014-05-06T03:23:19+00:00}}
}}
{{Infobox data structure
|name=替罪羊树
|type=[[樹 (資料結構)|樹]]
|invented_year=1989年
|invented_by=阿爾尼·安德森、伊加爾·加爾佩林、[[羅納德·李維斯特]]
|space_avg=<math>O(n)</math>
|search_avg=<math>O(\log n)</math>
|search_worst=<math>O(\log n)</math><ref name=galperin_rivest/>{{rp|165}}
|insert_avg=<math>O(\log n)</math><ref name=galperin_rivest/>{{rp|165}}
|insert_worst=<math>O(n)</math><ref name=galperin_rivest/>{{rp|167}}
|delete_avg=<math>O(\log n)</math><ref name=galperin_rivest/>{{rp|165}}
|delete_worst=<math>O(n)</math><ref name=galperin_rivest/>{{rp|167}}
}}
'''替罪羊树'''（{{lang-en|Scapegoat tree}}）是[[電腦科學]]中，一种基于部分重建的[[自平衡二叉查找树|自平衡二叉搜索树]]。在替罪羊树上，插入或删除节点的[[平攤分析|平攤]]最壞[[時間複雜度]]是<math>\text{O}(\log n)</math>，搜索节点的最壞時間複雜度是<math>\text{O}(\log n)</math>。

在非平衡的[[二叉搜索树]]中，每次操作以后检查操作路径，找到最高的满足<math>\max(size(son_L),size(son_R))>\alpha*size(this)</math>的结点，重建整个子树。这样就得到了替罪羊树，而被重建的子树的原来的根就被称为替罪羊节点。常数<math>\alpha</math>一般选择为<math>0.7</math>左右。

与大多数平衡树所采用的缓慢调整的方式不同，替罪羊树采用了一种进行次数较少但代价较大的重构操作，即选择一个节点作为“替罪羊”，并将这个节点的子树直接重构成完全二叉树。因此，替罪羊树的最坏时间复杂度为<math>\text{O}(n)</math>

== 理论 ==
说一个二叉查找树是平衡的，当且仅当根节点左侧与右侧的节点各占一半，而替罪羊树则放松了这一限制，即，只需要满足

<math>
 size(left) \le \alpha size(node)
</math>

<math>
 size(right) \le \alpha size(node)
</math>

其中<math>size</math>函数（递归地）定义如下

 function size(node)
     if node = nil then
         return 0
     else
         return size(node->left) + size(node->right) + 1
     end if
 end function

== 参考文献 ==
*{{Cite conference | title=Improving partial rebuilding by using simple balance criteria | first=Arne | last=Andersson | booktitle=Proc. Workshop on Algorithms and Data Structures | pages=393–402 | year=1989 | publisher=Springer-Verlag | doi=10.1007/3-540-51542-9_33}}{{en}}
* {{Cite journal | first1=Igal | last1=Galperin | first2=Ronald L. | last2=Rivest | title=Scapegoat trees | journal=Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms | pages=165–174  | year=1993 | url=http://portal.acm.org/citation.cfm?id=313676}}{{en}}

{{-}}
{{计算机科学中的树}}
[[Category:树结构]]