替罪羊树——简单粗暴的数据结构

替罪羊树——简单粗暴的数据结构
正题
如果在一棵平衡的二叉搜索树内进行查询等操作，时间就可以稳定在log(n)，但是每一次的插入节点和删除节点，都可能会使得这棵树不平衡，最坏情况就是退化成一条链，显然我们不想要这种树，于是各种维护的方法出现了，大部分的平衡树都是通过旋转来维护平衡的，但替罪羊树就很厉害了，一旦发现不平衡的子树，立马拍扁重建，这就是替罪羊树的核心：暴力重建
lc,rc分别表示i的左右子树
对以p为根的子树重构当且仅当
siz[lc]>siz[p]*alpha
或者
siz[rc]>siz[p]*alpha
alpha(∈[0.5,1])alpha(∈[0.5,1])是自己设定的一个参数，规定了这棵树的平衡程度
当alpha==0.5alpha==0.5时，几乎每次都要重构，树为平衡树，但是重构次数太多
当alpha==1.0alpha==1.0时，不会重构，此时是普通的二叉搜索树，有可能卡成链
重构方法：先对以p为根的子树DFS（中序遍历），将序号存在一个数组里。因为是中序遍历，因此数组内点的值是有序的，可以直接build
重构操作
首先将要重构的子树拍平（遍历一次得到一个数组），然后利用这个数组进行重构。每次的节点为这个区间的中点，然后递归调用去把[l, mid - 1]重构左子树，[mid + 1, r]重构有子树。记得在每层函数返回之前进行子树大小的维护。
首先中序遍历得到一个有序的数组（由于我比较懒，所以用的vector，建议保存节点的地址或下标，不要只保存数据）
找到mid，然后递归生成它的左子树和右子树:
为了体现当l > r时，直接return NULL