红黑树删除修复中兄弟节点为Nil时的问题排查与解决

我正在用C语言实现红黑树，参考CLRS中的伪代码。执行删除操作的修复过程时，当兄弟节点w为Nil（空节点）时，访问w->left或w->right会触发段错误，但伪代码里没处理这种场景。尤其是代码中if ((w->left->color == RBTREE_BLACK) && (w->right->color == RBTREE_BLACK))这一行会出问题，想知道怎么处理，修正这个错误。

用户原代码：

while (x != t->root && x->color == RBTREE_BLACK) 
{
    if (x == x->parent->left) 
    {
      node_t* w = x->parent->right;

      if (w->color == RBTREE_RED) 
      
      {
        w->color = RBTREE_BLACK;  
        x->parent->color = RBTREE_RED;
        rotate_left(t, x->parent);
        w = x->parent->right; 
      }
      if ((w->left->color == RBTREE_BLACK) && (w->right->color == RBTREE_BLACK))
      
      {
        w->color = RBTREE_RED;
        x = x->parent;
      }
      else {
        if (w->right->color == RBTREE_BLACK) 
        {
          w->left->color = RBTREE_BLACK;
          w->color = RBTREE_RED;
          rotate_right(t, w);
          w = x->parent->right;
        }

        
        w->color = x->parent->color;  
        x->parent->color = RBTREE_BLACK; 
        w->right->color = RBTREE_BLACK;
        rotate_left(t, x->parent); 
        x = t->root;
      }
    }
   else { same as then clause with “right” and “left” exchanged ..}
   x->color = RBTREE_BLACK;
}

问题根源 #

CLRS的红黑树伪代码默认使用哨兵节点替代空指针——所有逻辑上的空节点都指向同一个全局的Nil节点，这个节点颜色固定为黑色，左右子节点指向自身。如果你直接用NULL作为空节点，访问NULL->left这类操作必然触发段错误，而伪代码里没考虑这种情况。

两种解决方法 #

方法一：改用CLRS标准的哨兵节点实现 #

这是最贴合伪代码的方案，避免大量空判断：

1. 定义并初始化全局哨兵节点：

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int key;
    enum { RBTREE_RED, RBTREE_BLACK } color;
    struct node *left, *right, *parent;
} node_t;

// 全局哨兵节点
node_t NIL_NODE;
node_t* NIL = &NIL_NODE;

// 初始化哨兵节点
void init_nil() {
    NIL->color = RBTREE_BLACK;
    NIL->left = NIL;
    NIL->right = NIL;
    NIL->parent = NIL;
}

2. 所有原本赋值为NULL的地方（比如节点初始化、删除后的空指针）都替换成NIL。这样即使w是NIL，访问w->left或w->right都是指向NIL本身，不会触发段错误，且颜色为黑色，完全符合伪代码的判断逻辑。

方法二：保留NULL空节点，增加空判断 #

如果不想改动现有结构，就在访问节点成员前先检查是否为NULL，同时将NULL视为黑色（红黑树逻辑上空节点默认是黑色）。修改后的代码如下：

while (x != t->root && x->color == RBTREE_BLACK) 
{
    if (x == x->parent->left) 
    {
        node_t* w = x->parent->right;

        // 仅当w非空时判断颜色
        if (w != NULL && w->color == RBTREE_RED) 
        {
            w->color = RBTREE_BLACK;  
            x->parent->color = RBTREE_RED;
            rotate_left(t, x->parent);
            w = x->parent->right; 
        }

        // 将NULL节点视为黑色，判断左右子节点颜色
        int left_black = (w == NULL || w->left == NULL || w->left->color == RBTREE_BLACK);
        int right_black = (w == NULL || w->right == NULL || w->right->color == RBTREE_BLACK);

        if (left_black && right_black)
        {
            // w非空时才修改颜色
            if (w != NULL) {
                w->color = RBTREE_RED;
            }
            x = x->parent;
        }
        else {
            // 进入else说明至少一个子节点是红色，w不可能为NULL
            if (w != NULL) {
                int right_child_black = (w->right == NULL || w->right->color == RBTREE_BLACK);
                if (right_child_black) 
                {
                    if (w->left != NULL) {
                        w->left->color = RBTREE_BLACK;
                    }
                    w->color = RBTREE_RED;
                    rotate_right(t, w);
                    w = x->parent->right;
                }

                w->color = x->parent->color;  
                x->parent->color = RBTREE_BLACK; 
                if (w->right != NULL) {
                    w->right->color = RBTREE_BLACK;
                }
                rotate_left(t, x->parent); 
                x = t->root;
            }
        }
    }
    else { 
        // 镜像处理右子树的情况，同样增加空判断
        node_t* w = x->parent->left;

        if (w != NULL && w->color == RBTREE_RED) 
        {
            w->color = RBTREE_BLACK;  
            x->parent->color = RBTREE_RED;
            rotate_right(t, x->parent);
            w = x->parent->left; 
        }

        int right_black = (w == NULL || w->right == NULL || w->right->color == RBTREE_BLACK);
        int left_black = (w == NULL || w->left == NULL || w->left->color == RBTREE_BLACK);

        if (left_black && right_black)
        {
            if (w != NULL) {
                w->color = RBTREE_RED;
            }
            x = x->parent;
        }
        else {
            if (w != NULL) {
                int left_child_black = (w->left == NULL || w->left->color == RBTREE_BLACK);
                if (left_child_black) 
                {
                    if (w->right != NULL) {
                        w->right->color = RBTREE_BLACK;
                    }
                    w->color = RBTREE_RED;
                    rotate_left(t, w);
                    w = x->parent->left;
                }

                w->color = x->parent->color;  
                x->parent->color = RBTREE_BLACK; 
                if (w->left != NULL) {
                    w->left->color = RBTREE_BLACK;
                }
                rotate_right(t, x->parent); 
                x = t->root;
            }
        }
    }
}
x->color = RBTREE_BLACK;

总结 #

推荐使用哨兵节点方案，代码逻辑更简洁，和CLRS伪代码对齐，减少出错概率。如果坚持用NULL，必须在所有访问节点成员的地方增加非空判断，同时遵循红黑树空节点为黑色的规则。

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