替罪羊树

引入

替罪羊树 是一种依靠重构操作维持平衡的重量平衡树。替罪羊树会在插入、删除操作时，检测途经的节点，若发现失衡，则将以该节点为根的子树重构。

我们在此实现一个可重的权值平衡树。

重构

过程

首先，如前所述，我们需要判定一个节点是否应重构。为此我们引入一个比例常数 （取值在 ，一般采用 或 ），若某节点的子节点大小占它本身大小的比例超过 ，则重构。

另外由于我们采用惰性删除（删除只使用 wn[k]--），已删除节点过多也影响效率。因此若未被删除的子树大小占总大小的比例低于 ，则亦重构。

实现

重构分为两个步骤——先中序遍历展开存入数组，再二分重建成树。

实现

几种操作的处理方式较为类似，都规定了 到达空结点 与 找到对应结点 的行为，之后按 小于向左、大于向右 的方式向下递归。

插入

插入时，到达空结点则新建节点，找到对应结点则 wn[k]++。递归结束后，途经的节点可重构的要重构。

删除

惰性删除，到达空结点则忽略，找到对应结点则 wn[k]--。递归结束后，可重构节点要重构。

upper_bound

返回权值严格大于某值的最小名次。

到达空结点则返回 1，因为只有该子树左边的数均小于查找数才会递归至此。找到对应结点，则返回该节点所占据的最后一个名次 + 1。

以下是反义函数，相当于采用 std::greater<> 比较，即返回权值严格小于某值的最大名次。查询一个数的排名可以用 MyUprGrt(rt, x) + 1。

at

给定名次，返回该名次上的权值。到达空结点说明无此名次，找到对应结点则返回其权值。

前驱后继

以上两种功能结合即可。