C++红黑树Left-Rotate方法异常：插入1-8后根节点未更新至4

看来你在C++实现红黑树的左旋转逻辑上遇到了棘手的问题——这种平衡树的旋转细节很容易踩坑，尤其是指针引用、节点父子关系维护这块，我来帮你拆解可能的问题点：

一、先聚焦左旋转的核心逻辑是否正确 #

红黑树的左旋转本质是把目标节点的右孩子“提”为新的父节点，同时处理好子树和父节点的关联，你可以对照标准左旋转的步骤检查自己的代码：

标准左旋转（以节点x为例）的关键步骤：

1. 取x的右孩子y；
2. 将y的左子树（如果存在）挂载为x的右子树，同时把该子树的父节点更新为x；
3. 处理y的父节点：如果x是根节点，直接把红黑树的根指针指向y；如果x是其父节点的左/右孩子，把父节点的左/右指针替换为y；
4. 把x设为y的左孩子，更新x的父节点为y。

最容易出错的点通常是：

• 忘记更新根指针：当x是根时，旋转后根必须换成y，否则根节点会停留在原来的x；
• 遗漏y的左子树的父节点更新：如果y有左孩子，这个节点的父指针必须从y改为x，否则会出现悬空的父引用；
• 左右指针写反：把左旋转的逻辑和右旋转搞混，比如错误操作了x的左孩子而非右孩子。

二、检查插入后的平衡调整逻辑 #

红黑树插入后需要通过旋转+变色来维持性质，你需要确认：

• 左旋转函数是否被正确触发：比如插入1-8的过程中，是否在需要旋转的时机（比如出现连续红节点、黑高失衡）调用了左旋转？
• 旋转函数的调用是否正确更新了节点引用：如果你的左旋转函数是void类型，要确保函数内部能修改根指针；如果是返回新节点的设计，要把根指针赋值为旋转后的返回值（比如root = leftRotate(root)）。

三、用更细致的调试输出定位问题 #

你已经加了std::cout调试，可以进一步细化输出内容，把旋转前后的节点关系打印出来，比如在左旋转函数里添加：

void leftRotate(Node* &x) {
    std::cout << "[Left Rotate] Target node: " << x->val << "\n";
    Node* y = x->right;
    std::cout << "[Left Rotate] Taking right child: " << y->val << "\n";

    // 步骤1：处理y的左子树
    x->right = y->left;
    if (y->left != nullptr) {
        y->left->parent = x;
        std::cout << "[Left Rotate] Y's left child (" << y->left->val << ") parent set to " << x->val << "\n";
    }

    // 步骤2：处理y的父节点
    y->parent = x->parent;
    if (x->parent == nullptr) {
        root = y; // 关键：更新根节点
        std::cout << "[Left Rotate] Root updated to: " << root->val << "\n";
    } else if (x == x->parent->left) {
        x->parent->left = y;
        std::cout << "[Left Rotate] X's parent left child set to " << y->val << "\n";
    } else {
        x->parent->right = y;
        std::cout << "[Left Rotate] X's parent right child set to " << y->val << "\n";
    }

    // 步骤3：关联x和y
    y->left = x;
    x->parent = y;
    std::cout << "[Left Rotate] Post-rotate: " << x->val << " is left child of " << y->val << "\n";
}

运行插入1-8的流程，观察输出里的根节点是否在某次旋转后更新为预期值，就能快速定位是旋转逻辑没执行，还是执行后根指针没更新。

四、对比右旋转的实现找差异 #

既然你提到逆序插入（10到1）时右旋转正常，那可以把左旋转和右旋转的代码放在一起对比，看是不是对称逻辑写反了。比如右旋转是操作左孩子，左旋转操作右孩子，检查变量名、指针方向是否完全对称，有没有把left和right搞混的地方。

最后补充个小建议：不要只靠中序遍历判断根节点，直接打印root->val能更直观地确认根节点的实际值，避免遍历逻辑的干扰。

内容的提问来源于stack exchange，提问作者mikeg9