红黑树使用NULL指针替代NIL叶子节点的删除实现问题

嘿，我之前实现红黑树时也试过用NULL代替NIL叶子节点，确实在删除环节踩过同样的段错误坑——核心问题就是标准伪代码里的NIL是带父指针的实体节点，而咱们的NULL根本没法访问parent。不过不用慌，完全不用重写插入代码，有两种靠谱的解决思路：

方案一：跟踪NULL的「逻辑父节点」，修改删除修复逻辑 #

这个方案更优雅，不需要额外内存，核心是不直接从NULL获取父节点，而是在流程中主动记录每个NULL对应的实际父节点和它的位置（左/右孩子）。

具体调整点： #

1. 删除前记录关键上下文：
   当你找到要删除的节点时，先记录它的父节点，以及它是父节点的左孩子还是右孩子。如果被删除节点的子节点是NULL，那这个NULL的「逻辑父节点」就是被删除节点的父节点，位置也和被删除节点一致。

2. 修改修复函数的参数：
   把原来的修复函数参数从node* x改成node* x, node* x_parent, bool is_left，其中x_parent是x的逻辑父节点，is_left标记x是左还是右孩子。这样在修复循环里，所有需要用到x->getParent()的地方，直接用x_parent就行。

   举个代码改造的例子：

   void deleteFixup(node*& root, node* x, node* x_parent, bool is_left) {
       while ((x != root) && (x == nullptr || x->getCol() == true)) { // NULL默认视为黑色
           if (is_left) {
               node* w = x_parent->getRight();
               if (w != nullptr && w->getCol() == false) {
                   // 情况1：兄弟节点是红色
                   w->setCol(true);
                   x_parent->setCol(false);
                   leftRotate(root, x_parent);
                   w = x_parent->getRight();
               }
               // 后续情况处理...
               // 当需要更新x的位置时，同步更新x_parent和is_left
               x = x_parent;
               x_parent = x->getParent();
               is_left = (x_parent != nullptr && x == x_parent->getLeft());
           } else {
               // 对称的右孩子逻辑
           }
       }
       if (x != nullptr) {
           x->setCol(true);
       }
   }
   

3. 处理颜色判断：
   所有判断节点颜色的地方，要补充x == nullptr的情况——因为NULL相当于黑色NIL，所以直接返回true（假设你的color用true表示黑色）。

方案二：临时用NIL节点替换所有NULL，执行标准逻辑 #

如果不想大改删除修复的代码，可以临时创建一个全局的黑色NIL节点，在删除流程开始前把树里所有的NULL子节点替换成它，执行完标准的删除和修复后，再把NIL替换回NULL。这样几乎不用修改原来的删除代码，完美兼容你的插入逻辑。

具体实现步骤： #

1. 创建全局NIL节点：

   node* createNIL() {
       node* nil = new node();
       nil->setCol(true); // 设置为黑色
       nil->setParent(nil); // 自环，避免访问parent时出错
       nil->setLeft(nil);
       nil->setRight(nil);
       return nil;
   }
   

2. 替换NULL和NIL的辅助函数：

   void replaceNullWithNIL(node* root, node* nil) {
       if (!root) return;
       if (!root->getLeft()) {
           root->setLeft(nil);
       } else {
           replaceNullWithNIL(root->getLeft(), nil);
       }
       if (!root->getRight()) {
           root->setRight(nil);
       } else {
           replaceNullWithNIL(root->getRight(), nil);
       }
   }
   
   void replaceNILWithNull(node* root, node* nil) {
       if (!root || root == nil) return;
       if (root->getLeft() == nil) {
           root->setLeft(nullptr);
       } else {
           replaceNILWithNull(root->getLeft(), nil);
       }
       if (root->getRight() == nil) {
           root->setRight(nullptr);
       } else {
           replaceNILWithNull(root->getRight(), nil);
       }
   }
   

3. 改造删除函数：

   void deleteNode(node*& root, int data) {
       node* nil = createNIL();
       // 先把所有NULL换成NIL，适配标准逻辑
       replaceNullWithNIL(root, nil);
       // 执行你原来的标准删除和修复代码（把原来判断NULL的地方改成判断nil）
       // ...你的删除代码...
       // 再把NIL换回NULL，不影响原来的插入逻辑
       replaceNILWithNull(root, nil);
       delete nil;
   }
   

方案选择建议 #

• 如果你的插入代码已经稳定，不想做太多改动，方案二是最快上手的，几乎不用调整核心逻辑；
• 如果想让代码更高效、更优雅，方案一更适合长期维护，避免了额外的遍历和内存开销。

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