替罪羊树

维基百科,自由的百科全书
跳到导航 跳到搜索

替罪羊树是電腦科學中,一种基于部分重建的自平衡二叉搜索树。在替罪羊树上,插入或删除节点的平攤最壞時間複雜度O(log n),搜索节点的最壞時間複雜度是O(log n)。

在非平衡的二叉搜索树中,每次操作以后检查操作路径,找到最高的满足max(size(son_L),size(son_R))>alpha*size(this)的结点,重建整个子树。
这样就得到了替罪羊树,而被重建的子树的原来的根就被称为替罪羊节点。
常数alpha一般选择为0.7左右。
通过势能分析,至少对于只有插入操作的替罪羊树,单操作均摊复杂度为O(log n)。
删除操作可以通过设置“删除”标记完成,复杂度即为查找复杂度O(log n)。

参考文献[编辑]

  • Andersson, Arne. Improving partial rebuilding by using simple balance criteria. Proc. Workshop on Algorithms and Data Structures. Journal of Algorithms (Springer-Verlag). 1989: 393–402. 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. (英文)