Drzewo czerwono-czarne - błąd wykonania przy wstawianiu

0

Witam,
Aktualnie zajmuję się implementacją drzewa-czerwono czarnego w języku c++. Kod pisałem na wzór pseudokodu z Cormena.
Podczas wstawiania program wyrzuca mi błąd wykonania, a dokładniej - "Naruszenie ochrony pamięci", gdyż pracuję na Ubuntu.
Pisałem również BST, więc instrukcja wstawiania powinna być dobra. Błąd MUSI być gdzieś w funkcjach InsertFixUp lub Left/RightRotate.
Jednak nie potrafię go znaleźć samodzielnie.
Czy znalazłby się ktoś, kto pomógłby mi go naprawić?


    void LeftRotate( RBTNode *x )
    {
        RBTNode *y = x->right;

        x->right = y->left;

        if (y->left != NULL) y->left->parent = x;

        if (y != NULL) y->parent = x->parent;

        if (x->parent != NULL) 
        {
            if (x == (x->parent)->left) x->parent->left = y;
            else x->parent->right = y;
        } 
        else 
        {
            Root = y;
        }

        y->left = x;

        if( x != NULL ) x->parent = y;
    }

    void RightRotate( RBTNode *x )
    {
        RBTNode *y = x->left;

        x->left = y->right;

        if (y->right != NULL) y->right->parent = x;

        if (y != NULL) y->parent = x->parent;

        if (x->parent) 
        {
            if (x == x->parent->right) x->parent->right = y;
            else x->parent->left = y;
        } 
        else 
        {
            Root = y;
        }

        y->right = x;

        if (x != NULL) x->parent = y;
    }

    void InsertFixUp(RBTNode *x)
        {
                RBTNode *y = NULL;

                while ( (x != Root) && (x->parent->color == RED) ) 
                {
            if ( x->parent == x->parent->parent->left ) 
                        {
                y = x->parent->parent->right;

                if ( y->color == RED ) 
                                {
                                        x->parent->color = BLACK;
                                        y->color = BLACK;
                                        x->parent->parent->color = RED;
                                        x = x->parent->parent;
                                }

                                else 
                                {
                                        if ( x == x->parent->right ) 
                                        {
                                                   x = x->parent;
                                                   LeftRotate(x);
                                        }

                                        x->parent->color = BLACK;
                                        x->parent->parent->color = RED;
                                        RightRotate(x->parent->parent);
                                }
                        }

                        else 
                        {
                                y = x->parent->parent->left;

                                if ( y->color == RED ) 
                                {
                                        x->parent->color = BLACK;
                                        y->color = BLACK;
                                        x->parent->parent->color = RED;
                                        x = x->parent->parent;
                                 }

                                else 
                                {
                                        if ( x == x->parent->left ) 
                                        {
                                                   x = x->parent;
                                                   RightRotate(x);
                                        }

                                        x->parent->color = BLACK;
                                        x->parent->parent->color = RED;
                                        LeftRotate(x->parent->parent);
                               }
                       }
        }

                Root->color = BLACK;
        }

    void Insert(RBTNode *InsertNode)
    {       
                // wyciąłem część kodu z BST który działa !

        InsertNode->left = NULL;
        InsertNode->right = NULL;

        InsertNode->color = RED;

        InsertFixUp(InsertNode);

    }

Pozdrawiam,
WiedźMAC

0

Zdebugowałem program, jednak wyrzuca mi błąd w dziwnym miejscu.
Dokładniej w funkcji InsertFixUp :

 if ( y->color == RED ) 

Szukałem kilku gotowych algorytmów w internecie i wg. nich moja funkcja jest zaimplementowana poprawnie.
Ma ktoś jakieś pomysły gdzie szukać błędu ?
Pozdrawiam,
WiedźMAC

0

W końcu mi się udało.
Jak wiadomo, w drzewie czerwono-czarnym liście są czarne nie ?
Dlatego stworzyłem globalny obiekt RBTNode *Leaf, kŧórego kolor jest czarny. W każdym miejscu gdzie było NULL wstawiłem Leaf i program pięknie działa.
Dziękuje za pomoc :)
Pozdrawiam,
WiedźMAC

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0