c - 插入带有公共(public)哨兵的红黑树

Question

我在 c 中实现了 2 个函数:

1. Client* insertABR(Client* sentinelle, int numeroTel, int prixAppel):这允许我插入到红黑树中，就像我插入到二叉搜索树中一样，无需考虑颜色。(它工作正常)。
2. Client* insert(Client* sentinelle, int numeroTel, int prixAppel):这个函数允许我修复之前的插入。

我的客户端结构如下:

     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;

这棵红黑树的特点是它有一个共同的哨兵，如图所示:enter image description here 树根(拉辛)是哨兵的左子 fils gauche = 左儿子，fils droit = 右儿子。

    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;

    }
    }

我的问题是，当我尝试插入 8、18、10、19、29、15 时，我得到了这个结果:

8(BLACK) 和 19(RED) 的根 10(BLACK) parent。 19 是 29(BLACK) 和 18(BLACK) 的父代。 AND 18 是 15(RED) 的父级。 颜色很好，但树不再平衡，就像错过了旋转但我不知道在哪里添加它。

Answer 1

---

你的问题在这里(以及当 parent 是正确的 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));

它需要是:

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

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

现在，当这两个 Action 需要向后时，您可以更改相反方向情况下 c 指向的位置，并在它们相同(即左 child 的左 child )时不理会它。