平衡树和平衡因子

AVL 树是最早的平衡二叉树。
对于AVL树的任意一个节点，左子树和右子树的高度差不能超过1
用某子树左右两子树高度差作为平衡因子的度量
实际存储时，每个节点存储其所在子树的高度，用以辅助求解平衡因子。

平衡树性质验证

中序遍历的序列是从小到大排列的。
每个节点的平衡因子绝对值不超过1

平衡树性质的维护

什么时候维护

当插入和删除的节点时，有可能破坏树的平衡。
当平衡被破坏时候，通过左旋和右旋自底向上的将树重新调整到平衡状态。

如何维护（仔细看其实是两种情况， LL RR）

LL

      y
    /
  x
 /
z

判定方式： balanceFactor > 1 && getBalancedFactor(tr[node].left) >= 0
调整方式： 右旋y

RR

y
  \
    x
      \
       z

判定方式： balanceFactor < -1 && getBalancedFactor(tr[node].right) <= 0
调整方式： 左旋y

LR

      y 
    /
  x
    \
      z

判定方式 : balanceFactor > 1 && getBalancedFactor(tr[node].left) < 0
调整方式： 先左旋x,转化成 LL，后右旋y

RL

y
  \
    x
  /
z   

判定方式 : balanceFactor < -1 && getBalancedFactor(tr[node].right) > 0
调整方式： 先右旋x，转化成RR, 后左旋y

插入 查找 删除

和二叉树相似，插入或者删除后需要调整平衡
允许重复插入相同元素

代码与正确性验证

//类的命名不要介意，只是拿这道题验证实现的对不对。

class Skiplist {
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; 

    Skiplist() {
    }

    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;
    }
};

/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist* obj = new Skiplist();
 * bool param_1 = obj->search(target);
 * obj->add(num);
 * bool param_3 = obj->erase(num);
 */

leetcode 1206 验证通过