AVL特点：

1. 可以是一棵空树
2. 左子树和右子树高度之差（平衡因子）的绝对值不超过1（左右子树的高度差可以为0、1和 -1）
3. 左子树和右子树均为平衡二叉树

右旋

1. 根节点成为左子节点的右子树
2. 左子节点原本的右子树成为根节点的左子树

int rightRotate(int y) {
        int x = tr[y].left, z = tr[x].left;
        int t = tr[x].right;
        tr[x].right = y, tr[y].left = t;
        pushup(y), pushup(x);
        return x;
    }

左旋

1. 根节点成为右儿子点的左子树
2. 右儿子原本的左子树成为根节点的右子树

int leftRotate(int y) {
        int x = tr[y].right, z = tr[x].right;
        int t = tr[x].left;
        tr[x].left = y, tr[y].right = t;
        pushup(y), pushup(x);
        return x;
    }

四种情况

1. LL:右旋
2. RR:左旋
3. LR:左旋左儿子，右旋根节点
4. RL:右旋右儿子，左旋根节点

class AVL {
public:

    const static int N = 50010, INF = 50011;

    struct Node {
        int key, left = 0, right = 0, height;
        void init(int _key) {
            key = _key, left = 0, right = 0, height = 0; // 初始化
        }
    } tr[N];

    int root = 0, idx = 0, size = 0;
    // 带垃圾回收机制
    int nodes[N], tt = -1; 

    AVL() {
    }

    int getHeight(int node) {
        if (!node) return 0;
        return tr[node].height;
    }

    int getBalancedFactor(int node) {
        if (!node) return 0;
        return getHeight(tr[node].left) - getHeight(tr[node].right);
    }

    int newNode() {
        if (tt < 0) nodes[++tt] = ++idx;
        size ++;
        return nodes[tt--];
    }

    void gcNode(int u) {
        nodes[++tt] = u;;
        size --;
    }

    void pushup(int u) {
        tr[u].height  = 1 + max(getHeight(tr[u].left), getHeight(tr[u].right));
    }

    int rightRotate(int y) {
        int x = tr[y].left, z = tr[x].left;
        int t = tr[x].right;
        tr[x].right = y, tr[y].left = t;
        pushup(y), pushup(x);
        return x;
    }

    int leftRotate(int y) {
        int x = tr[y].right, z = tr[x].right;
        int t = tr[x].left;
        tr[x].left = y, tr[y].right = t;
        pushup(y), pushup(x);
        return x;
    }

    bool search(int target) {
        int u = getNode(root, target);
        if (u > 0) return true;
        return false;
    }

    int getNode(int node, int key) {
        if (!node) return 0;
        if (key == tr[node].key) return node;
        else if (key < tr[node].key) return getNode(tr[node].left, key);
        else return getNode(tr[node].right, key);
    }

    void add(int num) {
       root = add(root, num);
    }

    int add(int node, int key) { 
        if (!node) {
            int u = newNode(); 
            tr[u].init(key);
            return u;
        }
        if (key < tr[node].key) 
            tr[node].left = add(tr[node].left, key);
        else if (key >= tr[node].key)
            tr[node].right = add(tr[node].right, key);

        tr[node].height = 1 + max(getHeight(tr[node].left), getHeight(tr[node].right));

        int balanceFactor = getBalancedFactor(node);

        // 维护平衡

        // LL
        if (balanceFactor > 1 && getBalancedFactor(tr[node].left) >= 0) {
            int res = rightRotate(node);
            return res;
        }

        // RR
        if (balanceFactor < -1 && getBalancedFactor(tr[node].right) <= 0) {
            return leftRotate(node);
        }

        // LR
        if (balanceFactor > 1 && getBalancedFactor(tr[node].left) < 0) {
            tr[node].left =  leftRotate(tr[node].left);
            return rightRotate(node);
        }

        // RL
        if (balanceFactor < -1 && getBalancedFactor(tr[node].right) > 0) {
            tr[node].right =  rightRotate(tr[node].right);
            return leftRotate(node);      
        }
        return node;
    }

    bool erase(int num) {
       if (!search(num)) return false;
       else root = remove(root, num);
       //print();
       return true;
    }

    int minimum(int node) {
        while (tr[node].left) node = tr[node].left;
        return node;
    }

    int removeMin(int node) {
       if (!tr[node].left) return tr[node].right;
       tr[node].left = removeMin(tr[node].left);
       return node;
    }

    int remove(int node, int key) {

        if (!node) return 0;

        int ret;
        if (key < tr[node].key) {
            tr[node].left = remove(tr[node].left, key);
            ret = node;
        } else if (key > tr[node].key) {
            tr[node].right = remove(tr[node].right, key);
            ret = node;
        } else {
            // 左子树为空
            if (!tr[node].left) {
                ret = tr[node].right;
                gcNode(node);
            }
                // 右子树为空
            else if (!tr[node].right) {
                ret = tr[node].left;
                gcNode(node);
            } else {
                // 左右子树都不为空
                int successor = minimum(tr[node].right);
                tr[successor].right = removeMin(tr[node].right); // 先计算右子树
                tr[successor].left = tr[node].left; 

                ret = successor;
                gcNode(node);
            }
        }
        // 删除完成后为空的情况
        if (!ret) return 0;

        tr[ret].height = 1 + max(getHeight(tr[ret].left), getHeight(tr[ret].right));

        int balanceFactor = getBalancedFactor(ret);

        // LL
        if (balanceFactor > 1 && getBalancedFactor(tr[ret].left) > 0) {
            return rightRotate(ret);
        }
        // RR
        if (balanceFactor < -1 && getBalancedFactor(tr[ret].right) < 0) {
            return leftRotate(ret);
        }

        // LR
        if (balanceFactor > 1 && getBalancedFactor(tr[ret].left) < 0) {
            int x = leftRotate(ret);
            return rightRotate(x);
        }
        // RL
        if (balanceFactor < -1 && getBalancedFactor(tr[ret].right) > 0) {
            int x = rightRotate(ret);
            return leftRotate(x);
        }
        return ret;
    }
};