CODEWITHSUNDEEP
c++algorithminsertionred-black-tree
Ghostli
Ghostli

Reputation: 423

Red-Black tree fixing insert

I'm creating my own Map structure (needed for class) using RB tree. From what I've learned about insertion we have 3 cases to handle. I'm following this implementation. Still I'm getting a memory violation after inserting the 3rd value ( and any further) while fixing the RB tree structure. How do I handle this case?

Child gets inserted:

Image

So here is my implementation:

struct Node
{
    pair<int,int> key;
    int Value;
    Node *LeftNode;
    Node *RightNode;
    Node *Parent;
    bool color;                 // 0 - black 1 - red
};

class Map
{
    int size;

public:
    Map();
    void insert(pair<int,int>, int);

private:
    void RotateLeft(Node*);
    void RotateRight(Node*);
    void InsertNode(Node*, pair <int,int>, int);
    void RestoreColor(Node*);

    Node* root;
};

void Map::RestoreColor(Node* child)
{
    while( child->Parent!=root && child->Parent->color==1 )
    {
        if(child->Parent == child->Parent->Parent->LeftNode)            
        {
            Node* uncle = child->Parent->Parent->RightNode;

            if(uncle->color == 1)                                       
            {
                child->Parent->color = 0;
                uncle->color = 0;
                child->Parent->Parent->color = 1;
                child = child->Parent->Parent;
            }else
            {
                if(child = child->Parent->RightNode)                    
                {
                    child = child->Parent;
                    RotateLeft(child->Parent);
                }
                child->Parent->color = 0;
                child->Parent->Parent->color= 1;
                RotateRight(child->Parent->Parent);
            }
        }else
        {
            if(child->Parent == child->Parent->Parent->RightNode)
            {
                Node* uncle = child->Parent->Parent->LeftNode;

                if(uncle->color == 1)                                                           {
                    child->Parent->color = 0;
                    uncle->color = 0;
                    child->Parent->Parent->color = 1;
                    child = child->Parent->Parent;
                }else
                {
                    if(child = child->Parent->LeftNode)                 
                    {
                        child = child->Parent;
                        RotateRight(child->Parent);
                    }
                    child->Parent->color = 0;
                    child->Parent->Parent->color= 1;
                    RotateLeft(child->Parent->Parent);
                }
            }
        }
        root->color=0;
    }
};

Violation happens at uncle access, where in this example uncle equals null. How do I change the function?

Upvotes: 1

Views: 1965

Answers (2)

Anurag Arora
Anurag Arora

Reputation: 1

RotateLeft(child->Parent);


RotateRight(child->Parent);

Shouldn't the the above in your code be

RotateLeft(child) and RotateRight(child) respectively.

Upvotes: 0

user1171983
user1171983

Reputation:

You're using an implementation that depends on sentinel nodes as leaf nodes, so that you always have a black node that you can dereference in cases like this. To change it, you'd have to change lines such as 

if(uncle->color == 1)

To

if((uncle != NULL) && (uncle->color == 1))

It will then take the 'else' clause as it should, as in the sentinel version, the colour would always be black in the case where you'd have a null pointer in the non-sentinel version.

Upvotes: 2

Related Questions