第二类：ZAG （逆时针） 相反操作
____________________________________ AVL树
对于每个节点左右子树高度不相差1的树称为~
平衡因子：对于一个节点，它的左子树减去右子树的高度。
高度为h的AVL树，至少包含 S(h) = fib(h+3)-1个节点
证明：递推
S(h) = S(h - 1) + S(h - 2) + 1
S(h) +１＝[S(h - 1) + 1] + [S(h - 2) + 1] 以上是fabonacci式 接口：
平衡因子：左子树-右子树高度 定义理想平衡以及AVL平衡 由BST派生接口：查找 重写：插入与删除
插入与删除操作：
对于插入，最多有O(logn)个节点发生变化。 而对于删除，最多有O(1)节点发生变化。
如何实现？zig-zag旋转
首先：遇到了插入后平衡因子绝对值大于1的情况。
这时候进行逆时针旋转，找哪一个点呢?
我们知道，插入引起的失衡是通过引起祖先一代一代失衡而使得整树失衡的过程，所以只要根绝在源头，也就是最先失衡的（最低级的）祖先，把它调整为平衡，整个树就又恢复平衡了。
因此需要将它与引起它失衡的子节点交换。 例如此图：P和V交换 具体操作：
用一个临时引用rc指向p，然后将p的左儿子交给g，之后gp交换，p替代g成为祖先。
这种交换成为 zigzig 对应zagzag为顺时针交换。
对于zigzag，也就是之字形交换（还有zagzig）
麻烦一些。
具体方法：先zig旋转
再次zag旋转
也就是说，先平衡小的，再平衡大的。 如果左子树高度太大，便使用zig 如果右子树高度太大，便使用zag平衡。
操作：先插入（BST），然后依次向上查找祖先，找到第一个失衡祖先，进行旋转调整。
删除算法：
依然进行旋转。
此时的情况是，祖孙三代都是左或右孩子比较多。
当旋转过后，如果T2 存在孩子，这时调整后的新树高度不变
但是如果T2 不存在孩子，则调整后子树的高度减少1，可能会造成失衡。 因此这时候可能最多需要做O(logn) 次调整。
当三代节点更多孩子的个数不是朝一个方向排列，也就是按照之字形排列，
那么就需要先转换为一边倒的类型I，在进行节点旋转。但此时高度减少了1.
——————————————————————