红黑树left_rotation函数异常求助（node**参数下的修复方案）

问题本质 #

你遇到的是二级指针使用时的指针混淆问题：操作节点内部的prev指针时，误修改了传入的*p（也就是外部指针变量本身）。核心原因是没区分开**节点内部的关联指针（prev/next）和指向节点的外部指针（node*）**的操作边界。

具体修复步骤 #

1. 理清旋转逻辑中的节点指代 #

左旋转的核心是将当前节点（记为dad）的右子节点提升为父节点，当前节点转为其左子节点。先明确变量定义，避免左右节点混淆：

void left_rotation(node **p) {
    // 先把二级指针指向的节点取出来，用一级指针操作内部关联
    node *dad = *p;
    node *right_son = dad->next; // 左旋转操作的是右子节点，别搞反

2. 分离节点内部指针操作与二级指针赋值 #

所有节点间的关联修改（prev/next）都通过一级指针完成，只在需要更新外部指针指向时，才操作*p：

// 步骤1：处理右子节点的左子树，挂到原父节点的右位置
    dad->next = right_son->prev;
    if (right_son->prev != NULL) {
        right_son->prev->next = dad;
    }

    // 步骤2：更新右子节点的父节点为原父节点的父节点
    right_son->prev = dad->prev;
    if (dad->prev == NULL) {
        // 原父节点是根，更新全局根指针
        root = right_son;
    } else {
        // 根据原父节点是左/右子节点，更新其父亲的对应指针
        if (dad == dad->prev->prev) { // dad是左子节点
            dad->prev->prev = right_son;
        } else { // dad是右子节点
            dad->prev->next = right_son;
        }
    }

    // 步骤3：原父节点成为右子节点的左子节点
    right_son->prev = dad;
    dad->prev = right_son;

    // 最后才更新传入的二级指针，指向旋转后的新父节点
    *p = right_son;
}

3. 检查self_balance的传参正确性 #

调用left_rotation时，必须传入指向需要旋转的节点指针的地址，而不是节点内部prev/next指针的地址。比如在平衡逻辑中，应该传&current_node而非&current_node->prev。

关键注意事项 #

• node**的作用是让函数能修改外部的指针变量（比如根节点、父节点的子节点指针），只有当需要改变外部指针的指向时才赋值*p，平时操作节点关联用一级指针即可。
• 你之前的变量名left_son可能是逻辑混淆的诱因，左旋转操作的是右子节点，命名要准确避免误导。

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