C++实现二叉搜索树时双孩子节点删除逻辑异常问题排查

你现在的二叉搜索树删除逻辑错误集中在deleteNode函数处理「待删除节点存在左右两个子节点」的分支，具体有两处核心问题：

• 未处理右子树最小节点（min_node）原位置的关联关系：min_node作为右子树的最左节点，本身可能存在右子节点，你直接将min_node从原位置剥离后，其原父节点、自身右子节点的关联指针都没有更新，会导致树结构断链、内存泄漏、后续遍历/查找逻辑异常。
• 未更新min_node右指针以及原节点子节点的父指针：你仅为min_node设置了左指针和父指针，既没有继承原节点的右子树，也没有更新原左右子节点的父指针指向min_node，会导致树结构破坏。

替换deleteNode函数中处理双孩子节点的分支代码即可，同时补充了单孩子场景下缺失的子节点父指针更新逻辑，修改后的完整deleteNode函数如下：

template<class T, class Allocator>
Node<T>* deleteNode(Node<T>* node, Allocator& alloc)
{
    if(node->left == nullptr && node->right == nullptr)
    {
        node->~Node<T>();
        alloc.deallocate(node, 1);
        return nullptr;
    }

    if(node->left == nullptr)
    {
        auto ret = node->right;
        ret->parent = node->parent; // 补充更新子节点的父指针
        node->~Node<T>();
        alloc.deallocate(node, 1);
        return ret;
    }

    if(node->right == nullptr)
    {
        auto ret = node->left;
        ret->parent = node->parent; // 补充更新子节点的父指针
        node->~Node<T>();
        alloc.deallocate(node, 1);
        return ret;
    }

    // 双孩子节点处理逻辑修复
    {
        auto* min_node = &min(*node->right);
        // 第一步：将min_node从原位置移除
        if (min_node->parent != node) { // min_node不是原节点的直接右孩子
            min_node->parent->left = min_node->right;
            if (min_node->right != nullptr) {
                min_node->right->parent = min_node->parent;
            }
            // 继承原节点的右子树
            min_node->right = node->right;
            node->right->parent = min_node;
        }
        // 第二步：继承原节点的左子树
        min_node->left = node->left;
        node->left->parent = min_node;
        // 第三步：更新父指针
        min_node->parent = node->parent;
        // 释放原节点
        node->~Node<T>();
        alloc.deallocate(node, 1);
        return min_node;
    }
}

修复后你可以放开main函数中test.erase_one(8)的注释进行测试，多次重复删除相同值、删除根节点、删除中间节点都不会出现结构异常，符合std::multiset的单元素删除行为。你可以在删除后调用dump函数输出结构验证树的合法性，也可以循环删除所有元素验证没有内存泄漏。

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