红黑树的左旋右旋

红黑树旋转的基本目标：

• 保持红黑树的基本性质（包括红黑性质和二叉搜索树性质）。
• 通过旋转操作，调整树的高度，避免树变成一条线，从而保证树的平衡。

旋转操作通常在插入和删除节点时发生，目的是保持红黑树的平衡和避免违反红黑树的性质（比如父节点和子节点之间的红色关系等）。

旋转的基本概念

1. 左旋（Left Rotation）：是围绕某个节点进行旋转，通常是将当前节点的右子节点提升为父节点，当前节点成为其左子节点。

2. 右旋（Right Rotation）：是围绕某个节点进行旋转，通常是将当前节点的左子节点提升为父节点，当前节点成为其右子节点。

左旋（Left Rotation）的过程

假设我们要围绕节点 x 进行左旋转：

        x
       / \
      a   y
         / \
        b   c

• 旋转的目标是将 y 提升为新的根节点，x 成为 y 的左子节点，b 成为 x 的右子节点，y 的左子树仍然是 b。
• 旋转之后的树结构如下：

        y
       / \
      x   c
     / \
    a   b

左旋的步骤：

1. 将 y 的左子树赋值给 x 的右子树。
2. 将 x 的父节点指向 y，并将 y 的父节点指向 x。
3. 将 y 设为原本 x 的父节点。

左旋通常发生在右子树较高的情况下，或者在调整红黑树平衡时需要用到。

右旋（Right Rotation）的过程

假设我们要围绕节点 y 进行右旋转：

        y
       / \
      x   c
     / \
    a   b

• 旋转的目标是将 x 提升为新的根节点，y 成为 x 的右子节点，b 成为 y 的左子节点，x 的右子树仍然是 b。
• 旋转之后的树结构如下：

        x
       / \
      a   y
         / \
        b   c

右旋的步骤：

1. 将 x 的右子树赋值给 y 的左子树。
2. 将 y 的父节点指向 x，并将 x 的父节点指向 y。
3. 将 x 设为原本 y 的父节点。

右旋通常发生在左子树较高的情况下，或者在调整红黑树平衡时需要用到。

旋转操作与红黑树的平衡

红黑树的插入和删除操作常常会导致树的某些性质被破坏，特别是破坏了树的平衡性。为了重新平衡树，我们使用左旋和右旋来进行局部的结构调整。具体来说，以下是插入和删除操作中常见的旋转方式：

插入时的旋转

1. 右旋：通常发生在当插入一个节点后，发现树的左子树较高时，使用右旋将树结构进行调整。

2. 左旋：通常发生在当插入一个节点后，发现树的右子树较高时，使用左旋将树结构进行调整。

删除时的旋转

删除节点时，尤其是删除红色节点时，可能会导致红黑树的性质被破坏，旋转操作有助于修复这些问题。

示例：左旋和右旋代码实现（Python）

左旋实现（Left Rotation）

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.parent = None

def left_rotate(root, x):
    # 左旋操作
    y = x.right
    x.right = y.left
    if y.left is not None:
        y.left.parent = x
    y.parent = x.parent
    if x.parent is None:
        root = y  # x 是根节点，y 成为新的根节点
    elif x == x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x
    x.parent = y
    return root

右旋实现（Right Rotation）

def right_rotate(root, y):
    # 右旋操作
    x = y.left
    y.left = x.right
    if x.right is not None:
        x.right.parent = y
    x.parent = y.parent
    if y.parent is None:
        root = x  # y 是根节点，x 成为新的根节点
    elif y == y.parent.right:
        y.parent.right = x
    else:
        y.parent.left = x
    x.right = y
    y.parent = x
    return root

总结

• 左旋是将当前节点的右子节点提升为父节点，并让当前节点成为其左子节点。
• 右旋是将当前节点的左子节点提升为父节点，并让当前节点成为其右子节点。
• 旋转操作是红黑树平衡操作的核心，插入和删除操作时常需要旋转来保持树的平衡。

旋转操作在红黑树的调整过程中非常重要，能够有效地维持树的平衡，确保树的高度保持在对数级别，从而保证查找、插入和删除操作的效率。