红黑树左旋和右旋的核心逻辑是通过调整局部父子指针关系恢复红黑树性质，且不改变中序遍历顺序；需更新至多3个节点的left、right、parent指针，保持bst性质与子树完整性。
红黑树左旋和右旋的核心逻辑是什么
左旋和右旋不是为了“好看”，而是为了在插入或删除后恢复红黑树的性质（特别是黑高一致和无连续红节点）。旋转本身不改变中序遍历顺序，只调整局部父子关系。关键在于：旋转操作必须保证原树的二叉搜索树性质不变，且只修改至多 3 个节点的指针（parent、left、right），其余节点子树保持完整挂载。
如何手写 rotate_left 和 rotate_right
假设节点结构为：struct Node { Node* left; Node* right; Node* parent; bool color; };。旋转操作必须更新父子双向指针，漏掉 parent 指针是新手最常踩的坑。
以左旋为例（rotate_left）：
-
y = x->right—— y 是 x 的右子，将成为新子树根 -
x->right = y->left，若y->left非空，则更新其parent指向 x -
y->parent = x->parent；若 x 原为根，则 y 成新根；否则将 x 的父节点的对应子指针指向 y -
y->left = x；x->parent = y
右旋是对称过程，只需把所有 left/right、x/y 角色互换即可。注意：旋转前后，x 和 y 的颜色不改变 —— 颜色修复是后续单独步骤。
为什么旋转后还要重新设置 parent 指针
因为红黑树的删除和插入算法（如 insert_fixup）依赖 parent 指针向上回溯。如果只改子指针而忽略父指针，会导致后续修复逻辑访问野指针或进入死循环。常见错误现象：Segmentation fault 在调用 grandparent->color 时触发，实际是 grandparent 为 nullptr 或未初始化。
实操建议：
- 每次修改
left或right，立刻检查并更新被移动节点的parent - 对根节点做旋转时，必须显式更新树的
root成员变量（很多实现漏掉这步） - 可加断言：
assert(x->left == nullptr || x->left->parent == x)，在调试阶段每轮旋转后校验
旋转函数要不要传入引用或返回新根
不需要。旋转操作就地修改指针，不分配新节点，也不改变树根地址（除非原根参与旋转）。函数签名应为 void rotate_left(Node*& root, Node* x) 或更常见的 void rotate_left(Node* x) + 外部维护 root 变量。前者便于封装，后者更贴近 CLRS 教材写法。
性能影响很小：纯指针操作，O(1) 时间；但若频繁旋转（比如极端不平衡插入），说明上层插入策略有问题，该查的是 insert_fixup 分支逻辑，而不是优化旋转本身。
容易被忽略的一点：旋转函数本身不处理颜色，也不判断 nullptr。调用前必须确保 x 非空，且对应子节点（如 x->right）存在 —— 这些前置检查应在调用方完成，而非塞进旋转函数里增加分支负担。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
