替罪羊树是维护 BST 平衡的一种方式。
它的方式为如果一个子树不平衡了，就拆毁重建。
重建的方法为先用中序遍历得到一个序列，然后以这个序列中间的元素为根，这样可以把序列分成左右两段。将这两段分别建树，就可以得到一个平衡的 BST。
但它的时间复杂度很高，不能通过平衡树的模板题。
1. 不平衡率
设 \(\alpha\) 为一个子树的不平衡率。如果一个子树左子树或右子树结点个数的占比大于等于 \(\alpha\)，那么它就是不平衡的。它的取值范围为 \(0.5 \le \alpha \le 1\)。当 \(\alpha=0.5\) 时，这是一棵满二叉树。当 \(\alpha=1\) 时，这是一条链。
设定一个 \(\alpha\) 值，使得所有子树的不平衡率不超过 \(\alpha\)。一般将它设为 \(0.7\) 左右。
2. 代码写法
先用一个栈 \(sta\) 表示可以使用的节点。
对于每个节点，有以下的参数：
权值，左儿子，右儿子，子树结点数，子树占用空间数，是否被删除。
那么便可以实现以下操作：
- 重建
用 \(order\) 表示中序遍历的序列。
对子树进行中序遍历，遍历到一个结点时，如果这个结点没被删除，就加入 \(order\) 末尾，否则加入 \(sta\)。
接下来，每次取 \(order\) 的中间结点作为根结点，对两边的序列继续递归重建。
- 插入结点
在合适的位置插入结点。如果这个结点导致一个子树不平衡了，就将这个子树重建。
- 删除结点
找到这个结点，标记已被删除。如果这个结点导致一个子树不平衡了，就将这个子树重建。
- 查询比 \(k\) 小的数的个数
查询点 \(u\) 时，如果 \(u\) 的权值小于 \(k\)，答案就为左子树大小 \(+\) [\(u\) 没有被删除] \(+\) 查询右子树。否则继续查询左子树。
- 查询排名为 \(k\) 的数
查询点 \(u\) 时，如果 \(u\) 没有被删除且 \(u\) 的左子树大小 \(+\) [\(u\) 没有被删除] 等于 \(k\)，那么 \(u\) 就是答案。否则如果 \(k\) 小于等于 \(u\) 的左子树大小 \(+\) [\(u\) 没有被删除]，就去左子树上找第 \(k\) 小值。否则去右子树上找第 \(k-\) 左子树大小 \(-\) [\(u\) 没有被删除] 小值。
- 比 \(k\) 小的最大的数
答案即为排名为 [比 \(k\) 小的数的个数] 的数。
- 比 \(k\) 大的最小的数
答案即为排名为 [比 \(k+1\) 小的数的个数 \(+1\)] 的数。
本题可以使用替罪羊树。
替罪羊树常用于维护 K-D 树的平衡。
标签：左子,结点,子树,删除,替罪羊,alpha,平衡 From： https://www.cnblogs.com/lrxmg139/p/18012099