摘要：
1，替罪羊树的介绍
2，替罪羊树的重构
3，替罪羊树的插入
4，替罪羊树的删除
5，替罪羊树的查询
1，替罪羊树的介绍
替罪羊树(Scapegoat tree)是一种自平衡二叉搜索树，它比我们前面讲的《AVL树》，《笛卡尔树》，《Treap树》，《FHQ-Treap树》，《Splay树》等二叉搜索树要简单的多。
替罪羊树不需要旋转操作，当遇到不平衡子树的时候直接拍扁重构，简单粗暴。
我们先来看一下替罪羊树的节点类，除了常见的val，left和right以外，还有两个属性size和isDelete。根据字段意思可以知道，size表示的是以当前节点为根节点的子树中节点个数，isDelete表示的是当前节点是否被删除。
在替罪羊树中删除一个节点并不是直接删除，而是把它标记为删除状态，这里我们假设不能插入重复的节点。
Java 代码：
// 节点类
class GoatNode {
int val;// 节点值
int size = 1;// 以当前节点为根的子树中节点个数。
// 左子树和右子树
GoatNode left, right;
boolean isDelete = false;// 当前节点是否被删除
GoatNode(int val) {
this.val = val;
}
}
C++ 代码：
// 节点类
struct GoatNode {
int val;// 节点值
int size = 1;// 以当前节点为根的子树中节点个数。
// 左子树和右子树
GoatNode *left = nullptr, *right = nullptr;
bool isDelete = false;// 当前节点是否被删除
GoatNode(int val) : val(val) {}
};
2，替罪羊树的重构
替罪羊树只有在子树不平衡的时候才会重构，也就是左右两个子树中节点相差比较多的时候，说明出现了不平衡，这个时候就会重构。如下图所示，红色节点的子树中出现了不平衡，需要把该子树拍扁重构。
怎么判断子树是否平衡呢？这里我们使用一个平衡因子alpha，如果节点node的一个子树节点个数占比超过alpha，说明出现了不平衡。这里的alpha值在0.5~1之间，其中值越小越平衡，但重构的频率也会越高，值越大越不平衡，所以综合考虑一般取0.75。
