【算法】平衡二叉搜索树的左旋和右旋

树旋转是一种维护平衡树结构的重要操作，主要用于平衡二叉搜索树（如AVL树和红黑树）。树旋转分为左旋和右旋。

1. 树旋转的定义

左旋 (Left Rotation)

左旋操作将节点及其右子树进行调整，使其右子树的左子节点成为根节点，原根节点成为新根节点的左子节点。

定义：

• 假设一个节点x有右子节点y，进行左旋时，以x为支点，将y提升为根节点，x变成y的左子节点。

示意图：

    x                   y\                 / \y      ==>      x   z/ \             / \T2  z           T1  T2

右旋 (Right Rotation)

右旋操作将节点及其左子树进行调整，使其左子树的右子节点成为根节点，原根节点成为新根节点的右子节点。

定义：

• 假设一个节点y有左子节点x，进行右旋时，以y为支点，将x提升为根节点，y变成x的右子节点。

示意图：

      y               x/               / \x      ==>      T1  y/ \                 / \T1  T2              T2  T3

2. 树旋转的Java代码实现

左旋代码 (Left Rotation)

class TreeNode {int value;TreeNode left;TreeNode right;TreeNode(int value) {this.value = value;this.left = null;this.right = null;}
}public TreeNode leftRotate(TreeNode x) {TreeNode y = x.right;TreeNode T2 = y.left;// Perform rotationy.left = x;x.right = T2;// Return new rootreturn y;
}

右旋代码 (Right Rotation)

public TreeNode rightRotate(TreeNode y) {TreeNode x = y.left;TreeNode T2 = x.right;// Perform rotationx.right = y;y.left = T2;// Return new rootreturn x;
}

3. 树旋转的优缺点

优点

1. 保持平衡： 树旋转是平衡二叉树（如AVL树和红黑树）中保持平衡的核心操作，可以防止树退化成链表，提高查找、插入和删除操作的效率。
2. 高效： 旋转操作的时间复杂度为O(1)，即常数时间内完成。
3. 提高性能： 通过保持树的平衡性，树旋转可以确保在最坏情况下操作的时间复杂度为O(log n)。

缺点

1. 实现复杂： 树旋转的实现和维护相对复杂，需要仔细处理旋转过程中节点的连接和调整。
2. 开销增加： 虽然单次旋转的时间复杂度为O(1)，但在插入或删除节点时，可能需要进行多次旋转，这会增加操作的总开销。
3. 维护难度： 对于平衡二叉树，如AVL树和红黑树，除了旋转操作，还需要维护其他信息（如高度、颜色），增加了代码复杂度。

总结

树旋转是维护平衡树结构的关键操作，通过旋转可以保持树的平衡性，从而提高查找、插入和删除操作的效率。尽管实现和维护有一定的复杂性，但其在提高树结构性能方面的作用非常显著，特别是在需要高效动态操作的场景下。