RBTree 删除：如果兄弟节点为零（sentinel）怎么办

Question

我正在用c实现红黑树。 我指的是 CLRS 中的伪代码。

伪代码：

我想知道为什么当兄弟为 nil(Null) 时，删除修复中没有错误处理。 目前，在检查兄弟姐妹的孩子时没有错误处理，因此当我运行删除代码时会弹出分段错误。

特别是在这里（完整代码在底部）：

if ((w->左->颜色==RBTREE_BLACK) && (w->右->颜色==RBTREE_BLACK))

所以我想知道如何处理这种情况..当我调试它时，w是nil节点，因此没有像w->left或w->right这样的东西

我错过了什么？请让我改正我的错误

  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;

Answer 1

您是对的，

w->left

和/或

w->right

在标准实现中可能为空。但请注意，所引用的伪代码是在一本书中给出的，其中 nil 节点实际上是具有颜色的nodes。在 CLRS 第 14 章中，他们写道：

如果节点的子节点或父节点不存在，则该节点相应的指针字段包含值NIL。我们将把这些 NIL 视为指向二叉搜索树的外部节点（叶子）的指针，并将普通的、带有键的节点视为树的内部节点。

这可能会令人困惑，因为在他们的定义中，NIL 指针不是真正的空指针，而是对一种哨兵节点的引用，而哨兵节点又称为“叶子”。这个哨兵节点也有颜色：它是黑色的。这也是他们可以写的原因：

每片叶子（

NIL

）都是黑色的。

虽然在实践中它很少像这样实现，但它确实具有这样的优点：你可以安全地执行你所询问的书中的代码：

if w.left.color == BLACK and w.right.color == BLACK

在他们的设置中，确保这个

w

是一个内部节点（在他们的定义中是“内部”），即使该节点有 NIL 子节点，也可以安全地访问该 NIL 节点以读取其颜色。

在您的实现中，您没有哨兵 NIL 节点的概念（我也不会这样做），因此您需要保护您的代码免于取消引用此类空指针。您的代码应该假设节点不存在时为黑色，这样您就可以应用所描述的逻辑。

例如，您可以编写一个辅助函数，以安全的方式获取节点的颜色（支持空指针）：

bool isRed(Node *node) {
    return node != nullptr && node->color == RBTREE_RED;
}

然后将正在考虑的

if

语句写为：

if (!isRed(w->left) && !isRed(w->right))