0

我正在实现红黑树，我似乎无法调试调用fixup()函数时发生的分段错误。下面提供了来自 gdb 的回溯。这些功能可以在回溯下方看到。将指针传递给fixup()函数是不正确的还是我需要取消引用这个节点？传递 Node 本身然后创建一个新的 Nodeptr 对象会更好吗？感谢您的时间。

#0  0x0000000000403f32 in RBT::fixup(RBT::Node*) ()
#1  0x0000000000403d7a in RBT::insert(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) ()
#2  0x0000000000402950 in insertNodesFromFile(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) ()
#3  0x0000000000402712 in selectStructure() ()
#4  0x00000000004023df in main ()

class RBT{
        private:
                class Node;
                typedef Node * Nodeptr;

                class Node{

                        public:
                                string key;
                                Nodeptr parent;
                                Nodeptr left;
                                Nodeptr right;
                                char color;

                                Node(Nodeptr const left, Nodeptr const parent, const string key, const char color, Nodeptr const right)
                                        :left(left), parent(parent), key(key), color(color), right(right)
                                {}//end Node

                };

                Nodeptr root;

        public:

                RBT(): root(nullptr) {}

                Nodeptr createNode(Nodeptr const left, Nodeptr const parent, const string key, const char color, Nodeptr const right){
                        return new Node(left, parent, key, color, right);
                }//end createNode()

                void insert(string key){
                        Nodeptr y = nullptr;
                        Nodeptr x = root;

                        Nodeptr z = createNode(nullptr, nullptr, key, 'R', nullptr);
                        cout << "CREATE NODE" << endl;

                        while(x != nullptr){
                                y = x;
                                if(z->key < x->key) {
                                        x = x->left;
                                } else {
                                        x = x->right;
                                }
                        }

                        z->parent = y;
                        if(y == nullptr)         { root = z;     }
                        else if(z->key < y->key) { y->left = z;  }
                        else                     { y->right = z; }

                        z->left = nullptr;
                        z->right = nullptr;
                        z->color = 'R';

                        cout << "BEFORE FIXUP" << endl;
                        fixup(z);

                }

                void fixup(Nodeptr z){

                        while(z->parent->color == 'R'){
                                if(z->parent == z->parent->parent->left){
                                        Nodeptr y = z->parent->parent->right;

                                        if(y->color == 'R'){
                                                z->parent->color = 'B';
                                                y->color = 'B';
                                                z->parent->parent->color = 'R';
                                                z = z->parent->parent;
                                        } else {
                                                if(z == z->parent->right){
                                                        z = z->parent;
                                                        leftRotate(z);
                                                }

                                                z->parent->color = 'B';
                                                z->parent->parent->color = 'R';
                                                rightRotate(z->parent->parent);

                                        }
                                } else{
                                        Nodeptr y = z->parent->parent->left;

                                        if(y->color == 'R'){
                                                z->parent->color = 'B';
                                                y->color = 'B';
                                                z->parent->parent->color = 'R';
                                                z = z->parent->parent;
                                        } else {
                                                if(z == z->parent->left){
                                                        z = z->parent;
                                                        rightRotate(z);
                                                }

                                                z->parent->color = 'B';
                                                z->parent->parent->color = 'R';
                                                leftRotate(z->parent->parent);
                                        }
                                }
                        }
                        root->color = 'B';
                }
4

0 回答 0