Insertion in a RED BLACK TREE with a common sentinal

Question

I've implemented 2 functions in c :

Client* insertABR(Client* sentinelle, int numeroTel, int prixAppel): that allows me to insert into a RED-BLACK tree as I'm inserting in a binary search tree without considiration of color.(It works fine).
Client* insert(Client* sentinelle, int numeroTel, int prixAppel): this function allow me to fix the previous insertion.

My structure Client is as follows:

     typedef enum {  RED=0, BLACK=1 } Color; 
     struct sClient
    {
    int num_tel;
    int nbr_appel;
    double cout;
    struct sClient *fg; // left
    struct sClient *fd; //right 
    Color col;
    struct sClient *pere; //parent
    };
    typedef struct sClient Client;

The speciality in this RED-BLACK tree is that it has one common sentinal as this image illustrate:enter image description here the root of the tree(Racine) is the left son of sentinal fils gauche = left son, fils droit = right son.

    Client* insert(Client* sentinelle, int numeroTel, int prixAppel){
    Client *s,*c,*y;
    s=sentinelle;
    if(sentinelle == NULL){
                   sentinelle= createNode(0,0,0,1);
                   c= createNode(numeroTel, 1, prixAppel,1);
                   sentinelle->fg=c;
                   c->pere=sentinelle; 
                   c->fg=sentinelle;
                   c->fd=sentinelle;
                   return sentinelle;
                   }
    else{  



        c=insertABR(sentinelle, numeroTel, prixAppel); 

         while(((c->pere != s) && (c->pere->col==0))  ){

           if(grand_pere(c)->fg == c->pere){
                        //grand_pere= grand_father      
                        y= grand_pere(c)->fd;


                        if(y->col ==0){

                        c->pere->col =1;      
                        y->col =1;
                        grand_pere(c)->col =0;
                        c=grand_pere(c); 
                        }
                        else{
                             if(c==c->pere->fd) {
                                                c=c->pere; 
                                                left_rotate(c); 
                                                }
                              c->pere->col =1;
                              grand_pere(c)->col= 0;
                              right_rotate(grand_pere(c));             
                             }
                        }



                        else{
                          y=grand_pere(c)->fg; 
                             if(y->col ==0){
                               c->pere->col =1;
                               y->col =1;
                               grand_pere(c)->col =0;
                               c=grand_pere(c); 
                        } 
                        else{
                             if(c==c->pere->fg) {
                                                c=c->pere; 
                                                right_rotate(c); 
                                                }
                              c->pere->col =1;
                              grand_pere(c)->col= 0;
                              left_rotate(grand_pere(c));                   
                             }                   

                             }


    } 
    sentinelle->fg->col=1;

    return sentinelle;

    }
    }

My problem is when I tried to insert 8, 18, 10, 19,29,15 I got this result:

The root 10(BLACK) parent of 8(BLACK) and 19(RED). 19 is the parent of 29(BLACK) and 18(BLACK). AND 18 is the parent of 15(RED). The colors are fine but the tree isn't balanced any more, It's like a rotation is missed but I don't know where to add it.

SoronelHaetir SoronelHaetir · Accepted Answer · 2018-01-08T19:35:15

Your problem is here (and in the corresponding case for when the parent is the right child):

if(c == c->pere->fd)
                    {
                        c = c->pere;
                        left_rotate(c);
                    }

                    c->pere->col = 1;
                    grand_pere(c)->col = 0;
                    right_rotate(grand_pere(c));

It needs to be:

if(c == c->pere->fd)
                        left_rotate(c);
                    else
                        c = c->pere;

                    c->col = 1;
                    c->pere->col = 0;
                    right_rotate(c)->pere;

Right now you change where c points in the opposite orientation case and leave it alone when they are the same (that is left child of left child) when those two actions need to be backwards.

Insertion in a RED BLACK TREE with a common sentinal

1 Answers