Red black trees implementation

Question

I am trying to implement insert operation for red black trees. I have written this class with C++ called RedBlack that contains Insert function as follows:

    void RedBlack::Insert(int data)
    {
        printf("init !!!\n");
        ColoredNode* myIterator = this->root ; // will iterate throw the tree until it reachs the centinel ;
        ColoredNode* IteratorParent = this->centinel ; // will store the parent of myIterator 
        ColoredNode* newNode = new ColoredNode(this->centinel,data,false);  
        
        printf("insert %d ------\n",data);
    
        while(myIterator != this->centinel)
        {
            printf("in While Loop node = %d-----------\n",myIterator->data);
            IteratorParent = myIterator ;
            if(data > myIterator->data)
                myIterator = myIterator->right;
            else
                myIterator = myIterator->left;
        }
    
        newNode->parent = IteratorParent ;
    
        if(IteratorParent == this->centinel)
            this->root = newNode ;
        else if (data >= IteratorParent->data)
            IteratorParent->right = newNode ;
        else
            IteratorParent->left = newNode ;
            
        this->InsertFixUp(newNode);
        myIterator = newNode = IteratorParent = nullptr ;
    }





void RedBlack::InsertFixUp(ColoredNode* node)
{
    /*
    * Here We Have Three Cases :
    *   -> Uncle Is Red ==> parent , Uncle will be Black and GrandParent will be Red 
    *   ->Uncle Is Black here we Have 2 cases :(suppose that Uncle Is right Child of Its Parent)
    *       -> if node Is right => LeftRotation
    *       -> if node Is Left => grandParent rightRotation
    *       and the same approach if Uncle Is left 
    */   

    ColoredNode* parent = nullptr ;
    ColoredNode* grandParent = nullptr ;
    ColoredNode* uncle = nullptr ;

    while(node != this->centinel && node->parent->isRed())
    {
        parent = node->parent ;
        grandParent = parent ->parent ;
        
        if(grandParent -> left == parent )
        {
            uncle = grandParent -> right;
            if(uncle->isRed())      // Case 1 : color both parent and uncle black 
            {
                parent -> black = true;
                uncle  -> black = true;
                grandParent->black = false ;
                node = grandParent ;
                continue ;
            }
            else if(node == parent->right)
            {
                this->LeftRotation(parent);
                node = parent ;
                parent = parent->parent ;
            }
            parent->black = true ;
            //node -> black = false;
            grandParent ->black = false ;
            RightRotation(grandParent);
            
        }
        else                    //Other side 
        {
            uncle = grandParent -> left;
            if(uncle -> isRed())
            {
                parent -> black = true ;
                uncle -> black = true ;
                grandParent -> black = false;
                node = grandParent ;
                continue;
            }
            else if (node == parent->left)
            {
                RightRotation(parent);
                node = parent;
                parent = parent-> parent;
            }
            parent -> black = true ;
            grandParent-> black = false;
            LeftRotation(grandParent);
        }
    }

}

This is the struct represents a node

struct ColoredNode
{
    ColoredNode *parent , *right , *left ;
    int data ;
    bool black ;
    ColoredNode(ColoredNode *node,int data,bool blackness)
    {
        right = left = parent = node ;
        this->data = data ;
        this->black = blackness;
    }

    bool isBlack()
    {
        return black;
    }

    bool isRed()
    {
        return !black;
    }
};

The problem is my insert doesn't work and I guess that "continue" statement yields the problem the program enter InsertFixUp and doesn't get out,

Answer 1

I hate to say it but a RB insert is rough, wait til you get to deletion! Argh!

If I recall my CS correctly, the root node should always be black and a red node should not have a red node as a child. New nodes should be red. Then after detecting the violation, you rotate the tree and re-color to maintain this invariant.

After implementing a RB tree and an AVL tree myself, after a lot of agony, I would highly recommend just starting from an empty tree and desk-checking your algorithms. Keep the algorithms simple at first. Ignore unhandled error cases and just check the it works for simple cases. You can add more cases later once you run a few example trees through it. This can be done without coding at all, and will help you understand how it works. Once that is done, it should prove simpler to write the code. But it does hurt when you're learning a new language simultaneously with learning how an RB tree works.

First thing is to test that your rotation algorithms work because everything else depends on that.