手撕红黑树的 左旋 与 右旋

一、为什么需要旋转？

在红黑树中，插入或删除节点可能会破坏其五条性质，比如高度不平衡或连续红节点。

为了恢复红黑性质，我们采用局部旋转来“调整树形结构”，保持平衡。

---

二、旋转本质是“局部变形”

• 左旋和右旋不会破坏中序遍历结果（即元素仍是有序的）
• 旋转只是在三到四个节点之间调整指针结构

---

三、🔄 左旋（Left Rotation）

目的：把某个节点往上提，把右子节点放下来

对节点 x 做左旋，即把 x 的右子节点 y 转换为其父节点，y 的左子树转为 x 的右子树。

✅ 前提：

• 节点 x 有一个右子节点 y

📌 结构变化图：

原始结构：             旋转后结构：x                      y
\                    /
y       -->        x
/                      \
T1                      T1

🔧 伪代码（C++ 风格）：

Node* leftRotate(Node* x) {Node* y = x->right;x->right = y->left;if (y->left) y->left->parent = x;y->parent = x->parent;if (!x->parent) root = y;else if (x == x->parent->left) x->parent->left = y;else x->parent->right = y;y->left = x;x->parent = y;return y;
}

---

四、🔁 右旋（Right Rotation）

目的：把某个节点往上提，把左子节点放下来

对节点 y 做右旋，即把 y 的左子节点 x 转换为其父节点，x 的右子树转为 y 的左子树。

✅ 前提：

• 节点 y 有一个左子节点 x

📌 结构变化图：

原始结构：             旋转后结构：y                    x
/                      \
x         -->           y
\                    /
T1                T1

🔧 伪代码（C++ 风格）：

Node* rightRotate(Node* y) {Node* x = y->left;y->left = x->right;if (x->right) x->right->parent = y;x->parent = y->parent;if (!y->parent) root = x;else if (y == y->parent->left) y->parent->left = x;else y->parent->right = x;x->right = y;y->parent = x;return x;
}

---

五、动手建议

手动画出下面结构并旋转：

         10\20\30

此时你对 10 进行左旋，会得到：

         20/  \10    30

---

六、应用场景提示

• 左旋和右旋是红黑树维护性质的唯一“结构性操作”
• 接下来我们讲：插入时的三种情况 + 旋转修复方式

---

✅ 小测试

1. 红黑树为什么旋转后仍能保持 BST 的性质？
2. 左旋后，原节点的右子节点发生了什么变化？
3. 红黑树旋转是否会破坏红黑性质？