CLRS标准红黑树实现插入功能异常，指针相关错误排查求助

代码错误点及修复方案 #

1. 插入函数初始化与空指针错误 #

RBTInsert 存在两处致命基础错误：

• 新节点z仅声明为nullptr，未分配内存就直接访问z->data，属于典型空指针解引用
• 遍历插入位置的指针x初始化为nullptr，导致遍历循环直接跳过，无法在非空树中找到正确插入位置
  修复后插入函数开头逻辑：

template <typename T>
void RBT<T>::RBTInsert(Node<T>* &root, T data)
{
     // 先为新节点分配内存
     Node<T>* z = new Node<T>;
     z->data = data;

     Node<T>* y = nullptr;
     // x初始化为根节点，启动遍历找插入位置
     Node<T>* x = root;

     while (x != nullptr)
     {
        y = x;
        if (z->data < x->data)
            x = x->left;
        else
            x = x->right;
     }
    // 后续插入位置赋值逻辑保持不变
    z->p = y;
    if (y == nullptr)
        root = z;
    else if (z->data < y->data)
        y->left = z;
    else
        y->right = z;

    z->left = nullptr;
    z->right = nullptr;
    z->color = RED;

    RBTFixUp(root,z);
}

2. 旋转函数根节点传值错误 #

RotateLeft、RotateRight的根节点参数为值传递，函数内部修改root = y无法作用到外部实际的根节点，会导致根节点更新失效，后续操作访问旧根引发逻辑混乱甚至死循环。
修复方案：将旋转函数的根节点参数改为指针引用：

// 类内声明修改为
void RotateLeft(Node<T>* &, Node<T>*);
void RotateRight(Node<T>* &, Node<T>*);

// 函数定义头修改为
template <typename T>
void RBT<T>::RotateLeft(Node<T>* &root, Node<T>* x)
template <typename T>
void RBT<T>::RotateRight(Node<T>* &root, Node<T>* x)

3. 红黑树调整逻辑不完整+空指针风险 #

RBTFixUp 存在两处严重问题：

• 直接访问叔叔节点y的color属性，未判断y是否为空：红黑树规定空节点为黑色，当叔叔节点为空时直接访问y->color会触发空指针崩溃
• 仅处理了叔叔节点为红色的情况与节点位置调整的单次旋转，缺少后续的变色和第二次旋转逻辑，红黑性质修复不完整，极易触发死循环
  修复后的完整RBTFixUp逻辑：

template <typename T>
void RBT<T>::RBTFixUp(Node<T>* &root, Node<T>* z)
{
    while (z->p != nullptr && z->p->color == RED)
    {
        if (z->p == z->p->p->left)
        {
            Node<T>* y = z->p->p->right;
            if(y != nullptr && y->color == RED)
            {
                z->p->color = BLACK;
                y->color = BLACK;
                z->p->p->color = RED;
                z = z->p->p;
            }else {
                if (z == z->p->right)
                {
                    z = z->p;
                    RotateLeft(root,z);
                }
                z->p->color = BLACK;
                z->p->p->color = RED;
                RotateRight(root, z->p->p);
            }
        }else
        {
            Node<T>* y = z->p->p->left;
            if(y != nullptr && y->color == RED)
            {
                z->p->color = BLACK;
                y->color = BLACK;
                z->p->p->color = RED;
                z = z->p->p;
            }else {
                if (z == z->p->left)
                {
                    z = z->p;
                    RotateRight(root,z);
                }
                z->p->color = BLACK;
                z->p->p->color = RED;
                RotateLeft(root, z->p->p);
            }
        }
    }
    root->color = BLACK;
}

4. 内存释放函数逻辑错误 #

MakeEmpty 先delete当前节点再递归访问左右子节点，delete后的节点已失效，访问root->left属于野指针访问，且不该使用while循环：
修复后的内存释放逻辑：

template <typename T>
void RBT<T>::MakeEmpty(Node<T>* root)
{
    if (root != nullptr)
    {
        MakeEmpty(root->left);
        MakeEmpty(root->right);
        delete root;
    }
}

5. 基础语法错误 #

Node 结构体定义结束后缺少分号，C++中结构体/类定义结束必须加分号，否则会触发编译错误。

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