Ошибка сегментации при передаче указателя узла в функцию - PullRequest
Новая
       60

Ошибка сегментации при передаче указателя узла в функцию

0 голосов
/ 22 февраля 2020

Я реализую красно-черные деревья и не могу отладить ошибку сегментации, возникающую при вызове функции fixup(). Обратный след от GDB приведен ниже. Функции можно увидеть ниже следа. Неправильно ли передавать указатель на функцию fixup() или мне нужно отменить ссылку на этот узел? Не лучше ли передать сам узел, а затем создать новый объект 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';
                }
...