替罪羊树
参考文献
导航菜单doi:10.1007/3-540-51542-9_33Scapegoat trees
二叉查找树（BST）笛卡尔树MVP树Top treeTop treeT树B+树B*树Bx树UB树2-3树2-3-4树(a,b)-树Dancing treeDancing treeH树后缀树基数树三叉查找树X-快速前缀树Y-快速前缀树AC自动机指数树融合树区间树PQ树Range treeRange treeSPQR树散列日历散列树Finger treeFinger tree顺序统计树Metric treeMetric treeCover treeCover treeBK树Doubly chained treeDoubly chained treeiDistanceiDistanceLink-cut treeLink-cut treeLog-structured merge-treeLog-structured merge-tree树状数组
树结构
電腦科學自平衡二叉搜索树平攤時間複雜度O二叉搜索树
替罪羊树是電腦科學中，一种基于部分重建的自平衡二叉搜索树。在替罪羊树上，插入或删除节点的平攤最壞時間複雜度是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. （英文）
| |||||||||||||||||||||||||||||||||||||||||||||||
