数据结构-AVL 左旋和右旋

x.right = y y.left = xxx(原x.right) 插入的元素在不平衡元素的左侧的左侧

对节点y进行向右旋转操作，返回旋转后新的根节点x
            y                             x
           / \                          /   \
          x   T4     向右旋转 (y)        z     y
         / \       - - - - - - - ->    / \   / \
        z   T3                       T1  T2 T3 T4
       / \
     T1   T2
复制代码

实现

private Node rightRotate(Node y){
    Node x = y.left;
    Node T3 = x.right;
    //向右旋转过程
    x.right = y;
    y.left = T3;
    
    // 更新height
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

    return x;
}
复制代码

三、左旋转

插入的元素在不平衡元素的右侧的右侧

对节点y进行向左旋转操作，返回旋转后新的根节点x
        y                             x
      /  \                          /   \
     T1   x      向左旋转 (y)       y     z
         / \   - - - - - - - ->   / \   / \
       T2  z                     T1 T2 T3 T4
          / \
         T3 T4
复制代码

代码实现

private Node leftRotate(Node y) {
    Node x = y.right;
    Node T2 = x.left;

    // 向左旋转过程
    x.left = y;
    y.right = T2;

    // 更新height
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

    return x;
}
复制代码

四、平衡维护

// 向以node为根的二分搜索树中插入元素(key, value)，递归算法
    // 返回插入新节点后二分搜索树的根
private Node add(Node node, K key, V value){

    if(node == null){
        size ++;
        return new Node(key, value);
    }

    if(key.compareTo(node.key) < 0)
        node.left = add(node.left, key, value);
    else if(key.compareTo(node.key) > 0)
        node.right = add(node.right, key, value);
    else // key.compareTo(node.key) == 0
        node.value = value;

    // 更新height
    node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));

    // 计算平衡因子
    int balanceFactor = getBalanceFactor(node);

    // 平衡维护
    if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
        return rightRotate(node);

    if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
        return leftRotate(node);

    return node;
}


复制代码

五、 LL RR

1. LL 插入的元素在不平衡元素的左侧的左侧
2. RR 插入的元素在不平衡元素的右侧的右侧
3. LR 插入的元素在不平衡元素的左侧的右侧
4. RL 插入的元素在不平衡元素的右侧的左侧

//LL 插入的元素在不平衡元素的左侧的左侧
    if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
        return rightRotate(node);
    // RR 插入的元素在不平衡元素的右侧的右侧
    if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
        return leftRotate(node);
复制代码

1. LR -> LL

if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }
复制代码

2. RL -> RR

if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }
复制代码

六、删除元素

private Node remove(Node node, K key){

    if( node == null )
        return null;

    Node retNode;
    if( key.compareTo(node.key) < 0 ){
        node.left = remove(node.left , key);
        retNode = node;
    }
    else if(key.compareTo(node.key) > 0 ){
        node.right = remove(node.right, key);    
        retNode = node;
    }
    else{   // key.compareTo(node.key) == 0

        // 待删除节点左子树为空的情况
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size --;
            retNode = rightNode;
        }

        // 待删除节点右子树为空的情况
        else if(node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size --;
            retNode = leftNode;
        }

        // 待删除节点左右子树均不为空的情况
        else{
            // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的位置
            Node successor = minimum(node.right);
            successor.right = remove(node.right, successor.key);
            successor.left = node.left;
            node.left = node.right = null;
            retNode = successor;
        }
    }

    if(retNode == null)
        return null;

    // 更新height
    retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));

    // 计算平衡因子
    int balanceFactor = getBalanceFactor(retNode);

    // 平衡维护
    // LL
    if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0)
        return rightRotate(retNode);

    // RR
    if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0)
        return leftRotate(retNode);

    // LR
    if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
        retNode.left = leftRotate(retNode.left);
        return rightRotate(retNode);
    }

    // RL
    if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
        retNode.right = rightRotate(retNode.right);
        return leftRotate(retNode);
    }

    return retNode;
}
复制代码