nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # scapegoat Tree 替罪羊树，他是一个暴力的bst，与普通bst相比，他记录了子树的大小，用参数alpha来定义平衡，即左右子树的大小都不允许超过根的alpha倍，所以往往aplha是一个0.5到1的数字，当违反了这个性质，就暴力重构，将树构造为完全平衡树。 ## 替罪羊树erase 为节点打上标记scapegoat，代表这个节点已经被删除了，回溯子树大小信息。 ## 替罪羊树insert 使用bst插入的方式来插入，注意特判掉那些被打删除标记的点，就可以了 ## 替罪羊树重构 当我们erase或者insert以后，受影响的节点应该恰好构成了一条从根到目标的链，我们使用maintain来重新调整子树大小的时候，注意标记那些非法(不平衡)的节点，然后当我们maintain到根的时候，我们重构离根最近的不平衡的子树。 ## 替罪羊树代码 替罪羊树代码
