时间戳

首页 > 解决方案 > 为什么这段代码适用于 VS 而不是 gcc/g++？

c++ - 为什么这段代码适用于 VS 而不是 gcc/g++？

问题描述

我正在尝试使用 VS 2019 作为我的 IDE 来实现红黑树。它似乎在 VS 中工作，但是当我尝试使用其他任何东西编译和运行时，每当我的插入函数被多次调用时，它都会导致段错误。（我尝试过在线编译器并将其发送给朋友）我被困住了，因为我不知道从哪里开始尝试修复我的错误。我听说 VS 处理动态内存的方式不同，但我不太确定。

下面是我的旋转、BST 插入和插入功能。

#include <iostream>
#include <vector>

// default constructor
// creates empty tree, root is nullptr

class NodeT
{
public:
    // public variables
    double key;
    double value;
    NodeT* left;
    NodeT* right;
    NodeT* parent;
    bool isBlack;

    // constructors
    NodeT()
    {
        key = 0;
        value = 0;
        left = nullptr;
        right = nullptr;
        parent = nullptr;
        isBlack = false;
    }
    NodeT(double keyset, double valueset, bool isBlackset)
    {
        key = keyset;
        value = valueset;
        left = nullptr;
        right = nullptr;
        parent = nullptr;
        isBlack = isBlackset;
    }
};

class RedBlackTree
{
public:

    // default constructor, sets all to null
    RedBlackTree();

    // insert
    // inserts the first parameter key, and value second parameter into the tree
    // returns true if done, false if there are duplicates, dont insert
    bool insert(double insert_key, double insert_value);

    
public:
    NodeT* root;
    void leftrotate(NodeT* to_rotate);
    void rightrotate(NodeT* to_rotate);
    bool bstinsert(NodeT* insert);

};

RedBlackTree::RedBlackTree()
{
    root = nullptr;
}


void RedBlackTree::leftrotate(NodeT* to_rotate)
{
    NodeT* new_parent = nullptr;
    new_parent = to_rotate->right;
    to_rotate->right = new_parent->left;
    if (new_parent->left != nullptr)
    {
        new_parent->left->parent = to_rotate;
    }
    new_parent->parent = to_rotate->parent;
    if (to_rotate->parent == nullptr)
    {
        root = new_parent;
    }
    else if (to_rotate == to_rotate->parent->left)
    {
        to_rotate->parent->left = new_parent;
    }
    else
    {
        to_rotate->parent->right = new_parent;
    }
    new_parent->left = to_rotate;
    to_rotate->parent = new_parent;
}

void RedBlackTree::rightrotate(NodeT* to_rotate)
{
    NodeT* new_parent = to_rotate->left;
    to_rotate->left = new_parent->right;
    if (new_parent->right != nullptr)
    {
        new_parent->right->parent = to_rotate;
    }
    new_parent->parent = to_rotate->parent;
    if (to_rotate->parent == nullptr)
    {
        root = new_parent;
    }
    else if (to_rotate == to_rotate->parent->right)
    {
        to_rotate->parent->right = new_parent;
    }
    else
    {
        to_rotate->parent->left = new_parent;
    }
    new_parent->right = to_rotate;
    to_rotate->parent = new_parent;
}

bool RedBlackTree::bstinsert(NodeT* insert)
{
    NodeT* parent = root;
    NodeT* search = root;

    if (root == nullptr)
    {
        root = insert;  
    }
    else
    {
        while (search != nullptr)
        {
            parent = search;
            if (insert->key < parent->key)
            {
                search = parent->left;
            }
            else if (insert->key > parent->key)
            {
                search = parent->right;
            }
            else                
            {
                return false;
            }
        }
        if (insert->key < parent->key)
        {
            parent->left = insert;
            insert->parent = parent;
            return true;
        }
        else if(insert->key > parent->key)
        {
            parent->right = insert;
            insert->parent = parent;
            return true;
        }
        else
        {
            return false;
        }
    }
}

bool RedBlackTree::insert(double insert_key, double insert_value)
{
    NodeT* y = nullptr;
    NodeT* x = new NodeT(insert_key, insert_value, false);
    bool dupe = bstinsert(x);
    if (dupe == false)
    {
        return false;
    }
    
    while (x != root && x->parent->isBlack == false)
    {
        if (x->parent == x->parent->parent->left)
        {
            y = x->parent->parent->right;
            if (y == nullptr || y->isBlack == true)
            {
                if (x == x->parent->right)
                {
                    x = x->parent;
                    leftrotate(x);
                }
                x->parent->isBlack = true;
                x->parent->parent->isBlack = false;
                rightrotate(x->parent->parent);
            }
            else if (y->isBlack == false)
            {
                x->parent->isBlack = true;
                y->isBlack = true;
                x->parent->parent->isBlack = false;
                x = x->parent->parent;
            }
        }
        else
        {
            y = x->parent->parent->left;
            if (y == nullptr || y->isBlack == true)
            {
                if (x == x->parent->left)
                {
                    x = x->parent;
                    rightrotate(x);
                }
                x->parent->isBlack = true;
                x->parent->parent->isBlack = false;
                leftrotate(x->parent->parent);
            }
            else if (y->isBlack == false)
            {
                x->parent->isBlack = true;
                y->isBlack = true;
                x->parent->parent->isBlack = false;
                x = x->parent->parent;
            }
        }
    }
    root->isBlack = true;
    return true;
}

在 main 中调用它会导致段错误，除非在 VS 中：

int main()
{
    RedBlackTree test;
    test.insert(47, 1);
    test.insert(32, 2);
}

感谢您抽时间阅读。任何帮助表示赞赏。

标签： c++red-black-tree

解决方案

至少有一个错误会导致未定义的行为：

当RedBlackTree::bstinsert函数应该返回一个bool.

为了验证这是错误，bstinsert可以在函数末尾之前放置一行来验证这是一个错误。

bool RedBlackTree::bstinsert(NodeT* insert)
{
    NodeT* parent = root;
    NodeT* search = root;

    if (root == nullptr)
    {
        root = insert;
    }
    else
    {
        while (search != nullptr)
        {
            parent = search;
            if (insert->key < parent->key)
            {
                search = parent->left;
            }
            else if (insert->key > parent->key)
            {
                search = parent->right;
            }
            else
            {
                return false;
            }
        }
        if (insert->key < parent->key)
        {
            parent->left = insert;
            insert->parent = parent;
            return true;
        }
        else if (insert->key > parent->key)
        {
            parent->right = insert;
            insert->parent = parent;
            return true;
        }
        else
        {
            return false;
        }
    }
    std::cout << "This is undefined behavior\n";  // <-- add this line
}

您将看到std::cout将遇到该行以确认您正在从bstinsert没有返回值的情况下返回。

此外，您使用的编译器 (Visual Studio) 会就此问题向您发出警告。与此类似的东西：

warning C4715: 'RedBlackTree::bstinsert': not all control paths return a value

您不应该忽略此警告。

推荐阅读