当前位置：首页 > web >正文

手撕红黑树的左旋与右旋

web 2025/7/2 2:58:59

一、为什么需要旋转？

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

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

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

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

三、🔄 左旋（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;
}