左旋转与右旋转的基本操作

在数据结构的学习中，尤其是平衡树（如 AVL 树）中，旋转操作是用来恢复树的平衡的重要手段。旋转包括两种基本类型：左旋转 和 右旋转。它们的作用是通过调整树的结构，保持平衡因子的合理范围，从而确保树的高度不会过高，保证数据结构操作的高效性。

1. 左旋转

左旋转是指围绕某个节点执行旋转操作，将该节点的右子树转到它的位置，同时该节点成为右子树的左子树。左旋转通常在树的右子树比左子树高时执行，目的是将树的右子树提升到该节点的位置，从而降低右子树的高度。

1.1 左旋转的步骤

假设需要旋转的节点为 x，其右子节点为 y。
将 y 的左子树（如果有的话）变为 x 的右子树。
将 x 成为 y 的左子节点。
将 y 变为 x 的父节点。

1.2 左旋转的示意图

假设我们有一个节点 x，它的右子树是 y，右子树 y 可能还有自己的子树：

    x                    y
   / \                 /   \
  a   y    ---->     x      z
     / \             /  \
    b   c           a    b

1.3 左旋转的时间复杂度

左旋转只涉及节点之间的指针调整，因此其时间复杂度是 O(1)。

2. 右旋转

右旋转是左旋转的反操作，它是围绕某个节点执行旋转操作，将该节点的左子树转到它的位置，而该节点成为左子树的右子树。右旋转通常在树的左子树比右子树高时执行，目的是将树的左子树提升到该节点的位置，从而降低左子树的高度。

2.1 右旋转的步骤

假设需要旋转的节点为 y，其左子节点为 x。
将 x 的右子树（如果有的话）变为 y 的左子树。
将 y 成为 x 的右子节点。
将 x 变为 y 的父节点。

2.2 右旋转的示意图

假设我们有一个节点 y，它的左子树是 x，左子树 x 可能还有自己的子树：

      y                  x
     / \                /   \
    x   z    ---->     a     y
   / \                       / \
  a   b                     b   c

2.3 右旋转的时间复杂度

与左旋转类似，右旋转也是只涉及节点之间的指针调整，因此时间复杂度是 O(1)。

3. 左旋转和右旋转的应用

在 AVL 树中，当某个节点的左右子树高度差大于 1（即树失衡）时，就需要使用旋转来恢复树的平衡。左旋转和右旋转就是常见的两种操作。具体的应用场景如下：

左旋转：当右子树比左子树高时，执行左旋转来恢复平衡。
右旋转：当左子树比右子树高时，执行右旋转来恢复平衡。

有时在某些特殊情况下，会需要 双旋转，比如，先执行右旋转再执行左旋转，或者先执行左旋转再执行右旋转。

4. 代码案例：Java 实现左旋转和右旋转

4.1 左旋转

// 定义树的节点
class TreeNode {
    int value;
    TreeNode left, right;
    
    public TreeNode(int value) {
        this.value = value;
        left = right = null;
    }
}

public class AVLTree {
    
    // 左旋转操作
    public TreeNode leftRotate(TreeNode x) {
        TreeNode y = x.right;  // 右子节点
        TreeNode T2 = y.left;  // 右子树的左子树

        // 执行左旋转
        y.left = x;
        x.right = T2;

        // 返回新的根节点
        return y;
    }

    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        
        TreeNode root = new TreeNode(10);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        
        System.out.println("旋转前：");
        System.out.println("根节点值: " + root.value);
        System.out.println("右子节点值: " + root.right.value);
        System.out.println("右子节点的左子节点值: " + root.right.left.value);
        
        root = tree.leftRotate(root);
        
        System.out.println("\n旋转后：");
        System.out.println("新的根节点值: " + root.value);
        System.out.println("新的右子节点值: " + root.right.value);
    }
}

4.2 右旋转

// 定义树的节点
class TreeNode {
    int value;
    TreeNode left, right;
    
    public TreeNode(int value) {
        this.value = value;
        left = right = null;
    }
}

public class AVLTree {
    
    // 右旋转操作
    public TreeNode rightRotate(TreeNode y) {
        TreeNode x = y.left;  // 左子节点
        TreeNode T2 = x.right;  // 左子树的右子树

        // 执行右旋转
        x.right = y;
        y.left = T2;

        // 返回新的根节点
        return x;
    }

    public static void main(String[] args) {
        AVLTree tree = new AVLTree();
        
        TreeNode root = new TreeNode(20);
        root.left = new TreeNode(10);
        root.left.right = new TreeNode(15);
        
        System.out.println("旋转前：");
        System.out.println("根节点值: " + root.value);
        System.out.println("左子节点值: " + root.left.value);
        System.out.println("左子节点的右子节点值: " + root.left.right.value);
        
        root = tree.rightRotate(root);
        
        System.out.println("\n旋转后：");
        System.out.println("新的根节点值: " + root.value);
        System.out.println("新的左子节点值: " + root.left.value);
    }
}