【C语言】【双重指针】红黑树旋转代码出现玄学bug，求解答

Question

##背景

最近在练习红黑树的插入操作，思路如下：
1. 先找到需要插入的位置，插入新点
2. 进行平衡操作：判断新点的父节点和叔叔节点的颜色，然后左旋或者右旋
3. 旋转函数的传入参数是指针的指针，指向A，旋转操作完成后参数指向B

##出现的问题

• 在函数中新建了一个指针变量pNewRoot指向（*ppRoot）的左节点；
• 在修改pNewRoot->parent的值时，发现（*ppRoot）的值也随之发生了变化；
• 查看&(pNewRoot->parent)时，发现其值与ppRoot相同，而正常情况下不应该相同，具体代码如下： cpp //右旋代码，传入地址指向A，旋转结束后指向B void RB_RightRotate(pRBTree *ppRoot) { pRBNode pRoot = *ppRoot; pRBNode pNewRoot = (*ppRoot)->left; pRBNode *ppNRP = &(pNewRoot->parent); (pRoot)->left = pNewRoot->right; if ((pRoot)->left) { (pRoot)->left->parent = (pRoot); } pNewRoot->right = pRoot; pNewRoot->parent = (pRoot)->parent; if (pNewRoot->parent) { if (pNewRoot->data < pNewRoot->parent->data) { pNewRoot->parent->left = pNewRoot; } else { pNewRoot->parent->right = pNewRoot; } } (pRoot)->parent = pNewRoot; *ppRoot = pNewRoot; }

 单独测试时不会出现以上情况，但是当按照8、4、13、17、20、12、16、10的顺序插入红黑树时，在插入节点10的过程中，有一个步骤是以17为支点右旋，见下图，在此步骤中会出现上述问题，请问bug出在哪里？

 旋转操作有其他的解决办法，但是我想知道这段代码为什么会出问题，谢谢各位！

---

插入、平衡过程的代码如下：

//节点定义
enum COLOR
{
    RED,BLACK
};
typedef int DataType;
typedef struct RBNode {
    DataType data;
    RBNode *left;
    RBNode *right;
    RBNode *parent;
    COLOR color;
}*pRBNode, *pRBTree, RBTree;
//平衡过程
void RB_Balance(pRBTree *ppParent, DataType ChiledData) {
    //父节点是黑色，直接返回
    if ((*ppParent)->color == BLACK) {
        return;
    }
    //父节点是红色
    pRBNode pGrand = (*ppParent)->parent;
    pRBNode pUncle;
    if ((*ppParent)->data < pGrand->data) {
        pUncle = pGrand->right;
    }
    else {
        pUncle = pGrand->left;
    }
    //叔叔节点为空或者黑色
    if (!pUncle || pUncle->color == BLACK) {
        if ((*ppParent)->data < pGrand->data) {
            //左右
            if (ChiledData > (*ppParent)->data) {
                RB_LeftRotate(ppParent);
            }
            //左左
            (*ppParent)->color = BLACK;
            pGrand->color = RED;
            RB_RightRotate(&pGrand);
            return;
        }
        //右左
        if (ChiledData < (*ppParent)->data) {
            RB_RightRotate(ppParent);
        }
        //右右
        (*ppParent)->color = BLACK;
        pGrand->color = RED;
        RB_LeftRotate(&pGrand);
        return;
    }
    //叔叔节点为红色
    (*ppParent)->color = BLACK;
    pUncle->color = BLACK;
    //如果祖父节点是根节点
    if (pGrand->parent == NULL) {
        return;
    }
    pGrand->color = RED;
    RB_Balance(&(pGrand->parent), pGrand->data);
    return;
}
//插入过程
void RB_InsertNode(pRBTree *ppRoot, DataType d) {
    if ((*ppRoot) == NULL) {
        *ppRoot = RB_NewNode(d, NULL, NULL, NULL, BLACK);
        return;
    }
    pRBNode pNewNode = RB_NewNode(d, NULL, NULL, NULL, RED);
    pRBNode pCur = *ppRoot;
    pRBNode pParent = pCur;
    //找到插入点的父节点
    while (pCur) {
        if (pCur->data == d) {
            return;
        }
        pParent = pCur;
        if (d < pCur->data) {
            pCur = pCur->left;
        }
        else {
            pCur = pCur->right;
        }
    }
    //插入
    pNewNode->parent = pParent;
    if (d < pParent->data) {
        pParent->left = pNewNode;
    }
    else {
        pParent->right = pNewNode;
    }
    //平衡
    RB_Balance(&pParent, d);
}

Answer 1

https://www.cnblogs.com/liudw-0215/p/9887951.html